5s 512M

题目描述

给出一个由小写字母组成、长度为 $n$ 的字符串 $S$ 和一个长度为 $n$ 的 $01$ 串 $b$，$b_i=1$ 表示 $S_i$ 是可修改的。

给出 $m$ 个子串 $S_{[l,r]}$，定义一个子串 $str$ 是非偏序的，当且仅当可以通过修改 $S$ 的至多一个位置，使得 $m$ 个子串中原先 $<str$ 的子串都 $\ge str$。

形式化地说，一个二元组 $(l_i,r_i)$ 是非偏序的，当且仅当存在一个字符串 $T$（由 $S$ 修改至多一个字符得到），使得 $\forall\,1 \le j \le m,[S_{[l_j,r_j]}<S_{[l_i,r_i]}]+[T_{[l_j,r_j]}<T_{[l_i,r_i]}]\not=2$。

询问哪些子串是非偏序的。

注意，修改后出现比 a 小或比 z 大的字符是允许的。

输入格式

第一行两个数 $n,m$。

第二行一个字符串 $S$。

第三行一个 $01$ 串 $b$。

接下来 $m$ 行，每行一个二元组 $(l_i,r_i)$。

输出格式

输出为一个长度为 $m$ 的 $01$ 串 $ans$。$ans_i=1$ 表示 $(l_i,r_i)$ 是 非偏序 的，$ans_i=0$ 表示不是。

输入输出样例 #1

输入 #1

10 5
abbaababaa
0111111111
1 5
7 10
1 3
3 7
4 8

输出 #1

01111

说明/提示

样例一解释

为了方便表述，钦定比 a 小的字符为 #，比 z 大的字符为 *。

• $(1,5):$ 无论如何修改，恒有 $S_{[1,3]}<S_{[1,5]},T_{[1,3]}<T_{[1,5]}$。

• $(7,10):$ $T$ 可以为 abbcababaa。

• $(1,3):$ $T$ 可以为 a#baababaa。

• $(3,7):$ $T$ 可以为 ab#aababaa。

• $(4,8):$ $T$ 可以为 abbaababaa。

数据范围与约定

本题采用捆绑测试。

$\text{subtask1(10pt):}$ $1 \le n,m \le 100$。

$\text{subtask2(30pt):}$ $1 \le n,m \le 1000$。

$\text{subtask3(10pt):}$ $b_i=1$。

$\text{subtask4(50pt):}$ 无特殊限制。

对于所有数据，$1\le n,m \le 2\times 10^5,1 \le l_i \le r_i \le n$，输入均为整数和小写字母。

/**
 *    author: sunkuangzheng
 *    created: 25.03.2024 09:12:19
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5;
using namespace std;
int T,n,m,pre[N],rk[N],sa[N],ok[N],h[N],st[20][N],mp[N],ans[N],th[N],sta[N],res[N],tp,ts[20][N],sm[N]; string s,t;
void SA(){
    for(int i = 1;i <= n;i ++) sa[i] = i,rk[i] = s[i];
    for(int j = 1;j <= n;j *= 2){
        for(int i = 1;i <= n;i ++) ok[i] = rk[i]; int p = 0;
        sort(sa+1,sa+n+1,[&](int x,int y){return rk[x] < rk[y] || rk[x] == rk[y] && rk[x + j] < rk[y + j];});
        auto cmp = [&](int x,int y){return ok[x] == ok[y] && ok[x + j] == ok[y + j];};
        for(int i = 1;i <= n;i ++) rk[sa[i]] = (cmp(sa[i],sa[i-1]) ? p : ++p); if(p == n) break;
    }for(int i = 1,k = 0;i <= n;h[rk[i ++]] = k) for(k --,k = max(k,0);s[i + k] == s[sa[rk[i] - 1] + k];k ++);
    for(int i = 1;i <= n;i ++) st[0][i] = h[i];
    for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
        st[j][i] = min(st[j-1][i],st[j-1][i+(1<<j-1)]);
}int lcp_pos(int i,int j){
    if(i == j) return n - i + 1;
    if(i = rk[i],j = rk[j],i > j) swap(i,j);
    int k = __lg(j - i);
    return min(st[k][i+1],st[k][j-(1<<k)+1]);
}struct str{int l,r,id;}a[N];
struct seg{
    int t[N*4],tg[N*4],t2[N*4],tg2[N*4];
    void cg(int s,int k,int op){
        op ? (tg[s] = max(tg[s],k),t[s] = max(t[s],k)) : 
        (tg2[s] = min(tg2[s],k),t2[s] = min(t2[s],k));}
    void pd(int s){cg(s*2,tg[s],1),cg(s*2+1,tg[s],1),cg(s*2,tg2[s],0),cg(s*2+1,tg2[s],0),tg2[s] = 1e9,tg[s] = 0;}
    void upd(int s,int l,int r,int ql,int qr,int k,int op){
        if(ql <= l && r <= qr) return cg(s,k,op);
        int mid = (l + r) / 2; pd(s);
        if(ql <= mid) upd(s*2,l,mid,ql,qr,k,op); if(qr > mid) upd(s*2+1,mid+1,r,ql,qr,k,op);
        t[s] = min(t[s*2],t[s*2+1]),t2[s] = max(t2[s*2],t2[s*2+1]);
    }int qry(int s,int l,int r,int ql,int qr,int op){
        if(ql > qr) return -1e9;
        if(ql <= l && r <= qr) return (op ? t[s] : t2[s]);
        int mid = (l + r) / 2,ans = (op ? 1e9 : -1e9); pd(s);
        if(ql <= mid) ans = qry(s*2,l,mid,ql,qr,op);
        if(qr > mid) ans = (op ? min(ans,qry(s*2+1,mid+1,r,ql,qr,op)) : max(ans,qry(s*2+1,mid+1,r,ql,qr,op)));
        return ans;
    }void init(){for(int i = 1;i <= 4*n;i ++) t[i] = tg[i] = 0,t2[i] = tg2[i] = 1e9;}
}sg;
int lcp_sub(str i,str j){return min({lcp_pos(i.l,j.l),i.r - i.l + 1,j.r - j.l + 1});}
bool cmp(str i,str j){
    if(lcp_pos(i.l,j.l) >= min(i.r - i.l + 1,j.r - j.l + 1)) return (i.r - i.l + 1 < j.r - j.l + 1);
    return rk[i.l] < rk[j.l];
}void los(){
    cin >> n >> m >> s >> t,s = " " + s,t = " " + t;
    fill(mp+1,mp+n+1,1e9),SA();
    for(int i = 1;i <= m;i ++) cin >> a[i].l >> a[i].r,a[i].id = i,mp[a[i].l] = min(mp[a[i].l],a[i].r);
    sort(a+1,a+m+1,cmp),sg.init();
    for(int i = 1;i <= n;i ++) sm[i] = sm[i-1] + (t[i] == '1');
    pre[0] = 1e9;
    for(int i = 1;i <= m;i ++) ts[0][i] = a[i].l,pre[i] = min(pre[i-1],a[i].r);
    for(int j = 1;j <= __lg(m);j ++) for(int i = 1;i + (1 << j) - 1 <= m;i ++) 
        ts[j][i] = min(ts[j-1][i],ts[j-1][i+(1<<j-1)]);
    auto qmin = [&](int l,int r){   
        l = max(l,1); if(l > r) return (int)1e9;
        int k = __lg(r - l + 1); 
        return min(ts[k][l],ts[k][r-(1<<k)+1]);
    };
    for(int i = 1;i <= n;i ++) if(t[i] == '0') sg.upd(1,1,n,i,i,1e9,1),sg.upd(1,1,n,i,i,-1e9,0); 
    int j = 1,ql = 0,qr = 1e9,fg = 0; res[0] = 1e9;
    auto ins = [&](int i,int k){
        while(tp && th[sta[tp]] >= th[i]) tp --;
        int j = sta[tp]; sta[++tp] = i;
        return res[i] = min({res[j],pre[k],qmin(j,k) + th[i]});
    };
    for(int i = 1;i <= m;i ++){
        th[i] = (i == 1 ? 0 : lcp_sub(a[i],a[i-1]));
        // cerr << s.substr(a[i].l,a[i].r - a[i].l + 1) << "\n";
        while(j < i && cmp(a[j],a[i]))
            sg.upd(1,1,n,a[j].l,a[j].r,a[j].l,1),sg.upd(1,1,n,a[j].l,a[j].r,a[j].l,0),ql = max(ql,a[j ++].l);
        qr = min(qr,ins(i,j-1));
        if(mp[a[i].l] != a[i].r) ans[a[i].id] = 0;
        else{
            // debug(a[i].id,ql,qr);
            if(j == 1) {ans[a[i].id] = 1; continue;}
            int len = min({lcp_pos(a[1].l,a[i].l),a[1].r - a[1].l,a[i].r - a[i].l}) + 1;
            ans[a[i].id] |= sg.qry(1,1,n,a[i].l,a[i].l + len - 1,1) < a[i].l;
            if(ql <= qr){
                auto sum = [&](int l,int r){return (l <= r ? sm[r] - sm[l - 1] : 0);};
                ans[a[i].id] |= (sum(ql,min(qr,a[i].l-1)) || sum(max(a[i].r+1,ql),min(n,qr)) || sg.qry(1,1,n,max(ql,a[i].l),min(qr,a[i].r),0) > a[i].l);
            }
        }
    }for(int i = 1;i <= m;i ++) cout << ans[i];
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}

```echarts