YbtOJ 535「后缀数组」相似子串

/*
超！还卡哈希！
*/
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
    Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
    Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
    Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,base=13,base2=17,P=998244353;
int n,q,a[N],rk[N],p[N],F[N][25],H[N][11],lg[N],v[N],pw[N],hsh[N],hsh2[N],pw2[N];
char s[N];vector<int> G[N];
#define pb push_back

struct ST{
    int dp[600010][51];
    void get(int *s,int n){
        for(int i=1;i<=n;i++){
            dp[i][0]=s[i];
        }
        for(int j=1;j<=(log(n)/log(2))+1;j++){
            for(int i=1;i<=n-(1<<j)+1;i++){
                dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int ask(int x,int y){
        int p=(log(y-x+1)/log(2));
        int Min=min(dp[x][p],dp[y-(1<<p)+1][p]);
        return Min;
    }   
}st;
struct SA {
    int rnk[N],sa[N],tme[N],sec[N],height[N],n,sigma;
    void Sort() {
        for(int i=0; i<=sigma; i++)tme[i]=0;
        for(int i=1; i<=n; i++)tme[rnk[i]]++;
        for(int i=1; i<=sigma; i++)tme[i]+=tme[i-1];
        for(int i=n; i>=1; i--)sa[tme[rnk[sec[i]]]--]=sec[i];
        memset(sec,0,sizeof(sec));
    }
    void GetSa(int *s) {
        for(int i=1; i<=n; i++)rnk[i]=s[i],sec[i]=i;
        Sort();
        for(int w=1,p=0; w<=n&&p<n; w<<=1,sigma=p) {
            p=0;
            for(int i=n-w+1; i<=n; i++)sec[++p]=i;
            for(int i=1; i<=n; i++)if(sa[i]>w)sec[++p]=sa[i]-w;
            Sort();
            swap(sec,rnk);
            rnk[sa[1]]=p=1;
            for(int i=2; i<=n; i++) {
                rnk[sa[i]]=(sec[sa[i-1]]==sec[sa[i]]&&sec[sa[i-1]+w]==sec[sa[i]+w])?  p:++p;
            }
        }
    }
    void GetHeight(int *s) {
        int k=0;
        for(int i=1; i<=n; i++) {
            if(k)k--;
            int j=sa[rnk[i]-1];
            while(s[i+k]==s[j+k])k++;
            height[rnk[i]]=k;
        }
    }
    int getLcp(int l,int r){
        if(l>r){
            int t=r;
            r=l;
            l=t;
        }
        int x=min(rnk[l],rnk[r]);
        int y=max(rnk[l],rnk[r]);
        //cout<<x+1<<" "<<y<<endl;
        return st.ask(x+1,y);
    }
    int init(int *s,int len) {
        sigma=N-5;
        n=len;
        GetSa(s);
        GetHeight(s);
        st.get(height,n);
        return n;
    }
}sa;
/*————————————————
版权声明：本文为CSDN博主「YuckXi」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/tomyking2005/article/details/90105343
————————————————*/

I int Q(CI l,CI r){if(l>r) return 2e9;RI k=lg[r-l+1];return min(F[l][k],F[r-(1<<k)+1][k]);}
I int GetL(CI x,CI L){RI l=1,r=x,mid,X=x;W(l<=r) Q((mid=l+r>>1)+1,x)>=L?X=mid,r=mid-1:l=mid+1;return X;}
I int GetR(CI x,CI L){RI l=x,r=n,mid,X=x;W(l<=r) Q(x+1,mid=l+r>>1)>=L?X=mid,l=mid+1:r=mid-1;return X;}
I bool chk(RI x,RI y,CI mid){return (hsh[x]-1LL*hsh[x+mid]*pw[mid]%P+P)%P==(hsh[y]-1LL*hsh[y+mid]*pw[mid]%P+P)%P&&(hsh2[x]-1LL*hsh2[x+mid]*pw2[mid]%P+P)%P==(hsh2[y]-1LL*hsh2[y+mid]*pw2[mid]%P+P)%P;}
I int LCP(CI x,CI y){if(!x!ya[x]^a[y]) return 0;RI l=0,r=n-max(x,y)+1,mid,X=1;W(l<=r) chk(x,y,mid=l+r>>1)?X=mid,l=mid+1:r=mid-1;return X;}
I int Get(CI x,CI y){RI i=0,xi,yi,tx,ty,t,A=0;for(xi=x,yi=y;xi<=n&&yi<=n;++A,i++,xi=tx+1,yi=ty+1) if(tx=i<G[x].size()?G[x][i]:n+1,ty=i<G[y].size()?G[y][i]:n+1,t=sa.getLcp(xi,yi),t<min(tx-xi,ty-yi)) return A+t;else if(A+=min(tx-xi,ty-yi),(ty-yi)^(tx-xi)tx>nty>n) return A;return A;}
I bool cmp(CI x,CI y){RI i,t=Get(x,y),tx=x+t<=n?a[x+t]:-1,ty=y+t<=n?a[y+t]:-1;for(auto i:G[x]) i==x+t&&(tx=0);for(auto i:G[y]) i==y+t&&(ty=0);return tx<ty;}
I int Qry(RI x,CI L){return GetR(p[x],L)-GetL(p[x],L)+1;}
int main(){
    freopen("similar.in","r",stdin),freopen("similar.out","w",stdout);
    RI i,j,x,y,lst=0;for(read(n,q),scanf("%s",s+1),pw[0]=pw2[0]=i=1;i<=n;i++) a[i]=v[s[i]-'0']?i-v[s[i]-'0']:0,v[s[i]-'0']=i,pw[i]=1LL*pw[i-1]*base%P,pw2[i]=1LL*pw2[i-1]*base2%P;
    for(i=n;i;i--) hsh[i]=(1LL*hsh[i+1]*base%P+a[i])%P,hsh2[i]=(1LL*hsh2[i+1]*base2%P+a[i])%P;for(i=n;i;i--){for(j=0;j<=9;j++) H[i][j]=H[i+1][j];H[i][s[i]-'0']=i;for(j=0;j<=9;j++) H[i][j]&&(G[i].pb(H[i][j]),0);sort(G[i].begin(),G[i].end());}

    sa.init(a,n);

    for(i=1;i<=n;i++) rk[i]=i;for(stable_sort(rk+1,rk+n+1,cmp),i=1;i<=n;i++) p[rk[i]]=i;
    for(lg[0]=-1,i=1;i<=n;i++) lg[i]=lg[i>>1]+1,F[i][0]=Get(rk[i-1],rk[i]);for(j=1;(1<<j)<=n;j++) for(i=2;i+(1<<j)-1<=n;i++) F[i][j]=min(F[i][j-1],F[i+(1<<j-1)][j-1]);
    W(q--) read(x,y),x^=lst,y^=lst,writeln(lst=Qry(x,y-x+1));return 0;
}