ZJOI2017 字符串

题目链接：https://loj.ac/p/2572

题目大意：

一个长度为 $n$ ，字符集大小为 $10^9$ 的字符串，要求完成 $m$ 次操作。

两种操作：

区间 $+d$ ，$d$ 可以为负。
求区间的字典序最小的后缀。

做法

太唐了，都已经知道了 Significant Suffixes 都还不会，感觉自从高三回归课内搞了一年后，我信息学的许多基本功都下降了好多，悲。

首先，一个显然的事情，我们得先处理子串比较的问题，这个显然可以二分+线段树+Hash 解决，时间复杂度：$O(n\log^2{n})$ 。（修改复杂度：$O(n\log{n})$）

其次，我们可以在线段树上维护每个区间的 Significant Suffixes 的集合，但是问题是怎么求 Significant Suffixes？

其实压根没有必要保证集合里面都是 Significant Suffixes，只需要保证 Significant Suffixes 一定在集合里面就行了，同时保证集合大小在 $O(\log)$ 即可。（当确定一个东西是什么十分困难时，不妨尝试确定一个东西不是什么）

根据 Significant Suffixes 的相关证明以及线段树的性质，不难发现，线段树上合并节点时，左节点只会贡献一个可能是 Significant Suffixes 的后缀。

而找到这个后缀的方法就是：在左节点的集合中找一种奇怪字典序最小的后缀，这种字典序最小是认为空字符大于所有字符，即如果 $A$ 是 $B$ 的真前缀且 $A$，则 $B<A$ 。

但是可以发现，一次修改的时间复杂度高达：$O(\log^4)$ ，但如果你足够聪慧，你可以发现，Hash 修改的时间开销很小，但是查询的时间开销很大，所以我们希望牺牲一下修改复杂度，从而降低查询复杂度，不难想到分块，分块+Hash 修改复杂度 $O(\sqrt{n})$ ，查询复杂度 $O(1)$ ，这样修改的最终复杂度就能优化到：$O(\log^3{n}+\sqrt{n})$ 。

那查询咋整，如果和修改一样合并节点，就没法保证左右节点长度几乎相等的性质，那个做法就不能用了，虽然也能补救，就是从右往左合并，如果左边的长度大于右边的长度+1，那么就把左边那个节点变成这个节点的左儿子和又儿子再进行合并，显然这样的时间复杂度是 $O(\log^3)$ 的，但是比较麻烦，有没有简单点的方法。

变换思路，不合并了，反正就 $O(\log)$ 个节点，则集合的并的大小也就 $O(\log^2)$ 大小，直接比较大小就行了，时间复杂度：$O(\log^3)$ 。

所以，最终复杂度就出来：$O(n\log^2{n}+m(\sqrt{n}+\log^3{n}))$

空间复杂度：$O(n\log{n})$

什么时候我能自己独立做出来一道这么牛逼的字符串题啊。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PLI;
const LL mod=2000000239;
const LL A=2000000137;
const int N=2e5+5;
const int NN=4e5+5;
const int B=950;
int n,q;
void getz(int &x){
    x=0;int f=1;char c=getchar();
    while(c>'9' || c<'0')c=='-'?f=-1:1,c=getchar();
    while(c<='9' && c>='0')x=(x<<3)+(x<<1)+c-'0',c=getchar();
    x=x*f;
}
LL mt(LL x){return x>=mod?x-mod:(x<0?x+mod:x);}
struct Hash{
    LL fb[N],ff[N];
    void init(){
        fb[0]=1;fb[1]=A;
        for(int i=2;i<=n;i++)fb[i]=fb[i-1]*A%mod;
        ff[0]=1;for(int i=1;i<=n;i++)ff[i]=mt(ff[i-1]+fb[i]);
    }
}has;
PLI operator+(PLI x,PLI y){
    return {(x.first*has.fb[y.second]+y.first)%mod,x.second+y.second};
}
int bel[N],lazy[N],ll[N],rr[N],val[N];
PLI fl[N];
void maintain(int x){
    for(int i=ll[x];i<=rr[x];i++){
        if(i==ll[x])fl[i]=PLI{val[i],1};
        else fl[i]=fl[i-1]+PLI{val[i],1};
    }
}
void change(int x,int l,int r,int d){
    for(int i=ll[x];i<=rr[x];i++){
        val[i]+=lazy[x];
        if(i>=l && i<=r)val[i]+=d;
    }
    lazy[x]=0;
    maintain(x);
}
void change(int l,int r,int d){
    if(bel[l]==bel[r])change(bel[l],l,r,d);
    else{
        change(bel[l],l,r,d);
        change(bel[r],l,r,d);
        for(int i=bel[l]+1;i<bel[r];i++)lazy[i]+=d;
    }
}
PLI queryhash_nl(int l,int r){
    if(l==ll[bel[l]])return fl[r];
    else return {mt(fl[r].first-fl[l-1].first*has.fb[ r-l+1 ]%mod),r-l+1};
}
PLI hashplus(PLI x,LL d){return {mt(x.first+has.ff[x.second-1]*d%mod),x.second};}/*x+dval*/
PLI queryhash_l(int l,int r){return hashplus(queryhash_nl(l,r),lazy[bel[l]]);}
PLI queryhas(int l,int r){
    PLI ans={0ll,0};
    for(int i=bel[l];i<=bel[r];i++){
        ans=ans+queryhash_l(max(l,ll[i]),min(rr[i],r));
    }
    return ans;
}
bool cmp(int x,int y,int lim,int typ=0){//return x<y
    int l=1,r=lim-max(x,y)+1,mid,ans=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(queryhas(x,x+mid-1)!=queryhas(y,y+mid-1))r=mid-1;
        else l=mid+1,ans=mid;
    }
    if(ans==lim-max(x,y)+1)return typ?x<y:x>y;
    else return val[x+ans]+lazy[bel[x+ans]]<val[y+ans]+lazy[bel[y+ans]];
}
struct Segment{
    int lc,rc;
    vector<int> sign;
}tr[NN];int cnt;
void updata(int x,int r){
    // tr[x].sign.clear();
    tr[x].sign=tr[tr[x].rc].sign;
    int ans=0;
    for(auto y:tr[tr[x].lc].sign){
        if(!ans || cmp(y,ans,r,1))ans=y;
    }
    tr[x].sign.push_back(ans);
}
int bt(int l,int r){
    int x=++cnt;
    if(l==r)tr[x].sign.push_back(l);
    else{
        int mid=(l+r)>>1;
        tr[x].lc=bt(l,mid);
        tr[x].rc=bt(mid+1,r);
        updata(x,r);
    }
    return x;
}
void change(int x,int l,int r,int ll,int rr){
    if(ll>rr || rr<l || ll>r || (l>=ll && r<=rr))return ;
    int mid=(l+r)>>1;
    change(tr[x].lc,l,mid,ll,rr);
    change(tr[x].rc,mid+1,r,ll,rr);
    updata(x,r);
}
int zans;
void query(int x,int l,int r,int ll,int rr){
    if(ll>rr || rr<l || ll>r)return ;
    if(l>=ll && r<=rr){
        for(auto y:tr[x].sign){
            if(!zans || cmp(y,zans,rr))zans=y;
        }
        return ;
    }
    int mid=(l+r)>>1;
    query(tr[x].lc,l,mid,ll,rr);
    query(tr[x].rc,mid+1,r,ll,rr);
}
int main(){
    getz(n);getz(q);
    has.init();
    for(int i=1;i<=n;i++){
        getz(val[i]);
        val[i]+=1000000001;
    }
    for(int i=1;i<=n;i++){
        bel[i]=i/B+1;
        if(!ll[bel[i]])ll[bel[i]]=i;
        rr[bel[i]]=i;
    }
    for(int i=1;i<=bel[n];i++)maintain(i);
    bt(1,n);
    for(int i=1;i<=q;i++){
        int typ;getz(typ);
        if(typ==1){
            int l,r,d;getz(l);getz(r);getz(d);
            change(l,r,d);
            change(1,1,n,l,r);
        }
        else{
            int l,r;getz(l);getz(r);
            zans=0;
            query(1,1,n,l,r);
            printf("%d\n",zans);
        }
    }
    return 0;
}

这个题目有点卡常，这里说一下我是怎么卡常的：

模数等量改成常数，同时将一些取模改成判断和加减的组合。
调调块长，在 $2\sqrt{n}$ 左右会快很多。
加快读。