题解：P10273 大娱乐至上

sunkuangzheng · 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} 大的字符。

参考了官方题解和一些民间题解 /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();
}