自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 22:56:24，当前版本为作者最后更新于2024-03-25 13:19:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\textbf{P10273}$

• 给定字符串 $s$ 和它的 $m$ 个子串 $s[l_i,r_i]$，对于 $i \in [1,m]$ 回答下面的问题：
  • 是否可以修改 $s$ 中最多一个字符得到串 $t$，使得 $\forall j \in [1,m],[s[l_j,r_j] < s[l_i,r_i]] + [t[l_j,r_j] < t[l_i,r_i]] \ne 2$。也就是说对于每一个 $l_j,r_j$，$s[l_j,r_j] \ge s[l_i,r_i]$ 和 $t[l_j,r_j] \ge t[l_i,r_i]$ 至少要有一个成立。特别的，你可以把某个字符修改为比 $\texttt{a}$ 小或比 $\texttt{z}$ 大的字符。
• $1 \le n,m \le 2 \cdot 10^5$。

参考了官方题解和一些民间题解 /kel

把所有 $s[l_i,r_i]$ 按照字典序从小到大排序，对于某个 $t = s[l_i,r_i]$ 我们只需要考虑字典序严格小于 $t$ 的 $t' = s[l_j,r_j]$ 对 $t$ 的限制。

考虑两种修改思路：把 $t$ 改小和同时把 $t'$ 改大。

• 把 $t$ 改小。我们会贪心的把字符改为最小的。

  显然我们的修改位置 $p \in [l_i,\min(r_i,\operatorname{LCP}(t,t')+l_i)]$。注意到两个后缀的 $\operatorname{LCP}$ 在 $rk$ 上相隔越远越小，我们可以直接取 $t' = s[l_1,r_1]$ 来计算 $\min \{\operatorname{LCP}(t,t')\}$。

  但是这么做存在一个问题。如果 $l_j \ge l_i$，且修改区域 $p \in [l_j,r_j]$，会使得 $t' = [l_j,r_j]$ 的字典序变得更小。也就是说，如果存在 $t' = [l_j,r_j]$ 和 $t$ 相交且 $l_j \ge l_i$，则相交区域不能选择。我们需要判断在由 $\operatorname{LCP}$ 限制下的区间内是否存在和上述区间不交的位置。这一步可以用线段树维护覆盖每个位置的 $l_j$ 的 $\max$，查询时查询合法区间的 $\min$，如果该值 $< l_i$ 则说明存在和上述区间不交的点。

• 把 $t'$ 改大。我们会贪心的把字符改为最大的。

  类似的，我们修改的位置 $p$ 要位于所有 $[l_j,\min(r_j,\operatorname{LCP}(t,t') + l_j)]$ 的交上。令交的区间为 $[L,R]$，考虑分开求解 $L,R$。$L$ 非常好求，显然有 $L = \max \limits_{j < i} \{l_j\}$。$R$ 的求解稍微复杂一些，我们先求出 $r_j$ 的前缀 $\min$ 后就只需要求 $\min \{\operatorname{LCP}(t,t') + l_j\}$ 的值。

  重要性质：设 $n$ 个 $S$ 的子串按字典序排序后为 $s_1,s_2,\ldots,s_n$，有 $\forall 1 \le i < j\le n,\operatorname{LCP}(s_i,s_j) = \min \limits_{k=i+1}^j \{\operatorname{LCP}(s_{k-1},s_k)\}$。

  其证明类似于 SA 求 $\operatorname{LCP}$。

  记 $th_i = \operatorname{LCP}(s[l_{i-1},r_{i-1}],s[l_i,r_i])$，对于 $t$ 和 $t'$ 的 $\operatorname{LCP}$ 有两种情况：$\operatorname{LCP} = th_i$ 或 $\operatorname{LCP} < th_i$，由 $\min$ 的单调性容易发现这两部分情况存在一个分界点 $k$，可以用单调栈找出。对于 $j \ge k$，我们的 $\min \{\operatorname{LCP}(t,t') + l_j\} = \min \{ l_j\} + th_i$，可以 ST 表简单维护。对于 $j < k$，我们发现这是一个完全独立于 $i$ 的子问题，只需要存储下 $i = k$ 时的答案直接使用即可。

  求出 $[L,R]$ 后，与 $[l_i,r_i]$ 不交的部分直接判断区间内是否有 $1$。有交的部分类似上述情况用线段树维护即可。

总时间复杂度 $\mathcal O(n \log n)$。

实现起来细节比较多，注意以下地方：

• 求解 $R$ 时不要忘记对 $r_i$ 取 $\min$。
• 可能存在相同的 $t$，注意不能把和 $t$ 相等的串视作 $t'$。
• 单调栈的边界问题。

注意以下代码中后缀数组是 $\mathcal O(n \log^2 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();
}