题目概述

有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。

解题报告

SAM+LCT什么的好大啊，所以我们来乱搞吧QAQ。

把串倒过来，那么就是求后缀的最长公共前缀，这是后缀数组Height数组经典问题，如果询问 $[L,R]$ 满足 $x\in\{rank_i|L\le i\le R\}$ 且 $x-1\in\{rank_i|L\le i\le R\}$ 那么 $Height_x$ 就可以修正这个询问。因此把询问离线之后，通过合并Height数组（大的Height可以合并到相邻的小的Height），我们就可以得到一个 $O(nm)$ 算法。

考虑从大到小枚举Height数组，这样我们就可以做到每个询问只修正一次，但是对于 $x$ 要怎么快速找到合法的询问？吃我bitset啦！

我们先处理出 $S_i$ 表示符合 $i$ 的询问集合（差分），然后每次通过bitset的&操作就可以快速得到满足条件且还没有被修正过的询问集合，这样复杂度就变成了 $O({nm\over\omega})$ 。

还有个黑科技，由于 $m=10^5$ 的时候会MLE，所以我们……做两次 $m=5\cdot10^4$ QAQ！

示例程序

#include<cstdio>
#include<bitset>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn=100000,maxm=50000,maxt=784;

int n,Q,SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5],h[maxn+5];
char s[maxn+5];int ID[maxn+5],Lg[23333],ans[maxm+5],fat[maxn+5];
#define pw(i) ((ULL)1<<(i))
struct Bitset{
    ULL s[maxt];inline void Clear() {for (int i=0;i<maxt;i++) s[i]=0;}
    inline void Set(int i) {s[i/64]|=pw(i%64);}
    inline void Unset(int i) {Set(i);s[i/64]^=pw(i%64);}
    inline void operator &= (const Bitset &a){
        for (int i=0;i<maxt;i+=4) s[i]&=a.s[i],s[i+1]&=a.s[i+1],s[i+2]&=a.s[i+2],s[i+3]&=a.s[i+3];
    }
    inline void operator |= (const Bitset &a){
        for (int i=0;i<maxt;i+=4) s[i]|=a.s[i],s[i+1]|=a.s[i+1],s[i+2]|=a.s[i+2],s[i+3]|=a.s[i+3];
    }
    inline void operator ^= (const Bitset &a){
        for (int i=0;i<maxt;i+=4) s[i]^=a.s[i],s[i+1]^=a.s[i+1],s[i+2]^=a.s[i+2],s[i+3]^=a.s[i+3];
    }
    inline int Next(int x){
        int A=x/64,B=x%64;ULL now;if (B<63&&(now=s[A]&~(pw(B+1)-1))) return A*64+Lg[(now&-now)%23333];
        for (int i=A+1;i<maxt;i++) if (s[i]) return i*64+Lg[(s[i]&-s[i])%23333];return 2e9;
    }
}q[maxn+5];

inline void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i];
}
inline void Make(char *s,int n){
    int m=255;for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i;Sort(n,m);
    for (int p=0,k=1;p<n;k<<=1,m=p){
        p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;rk[SA[i++]]=p) p+=t[SA[i-1]]<t[SA[i]]||t[SA[i-1]+k]<t[SA[i]+k];
    }for (int i=1,k=0;i<=n;h[rk[i++]]=k) {int j=SA[rk[i]-1];if (k) k--;while (s[i+k]==s[j+k]) k++;}
    for (int i=0;i<64;i++) Lg[pw(i)%23333]=i;
}
inline bool cmp(const int &a,const int &b) {return h[a]>h[b];}
int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);}
#include<cstdlib>
inline void Solve(int Q){
    Bitset now,vis;vis.Clear();for (int i=1;i<=n;i++) q[i].Clear();
    for (int i=1;i<=Q;i++){
        int l,r,L,R;scanf("%d%d",&l,&r);L=n-r+1;R=n-l+1;
        q[rk[L]].Set(i);if (R<n) q[rk[R+1]].Set(i);vis.Set(i);
    }for (int i=1;i<=n;i++) q[rk[i]]^=q[rk[i-1]],fat[i]=i;
    for (int i=1;i<n;i++){
        int x=getfa(ID[i]),y=getfa(ID[i]-1);now=q[x];now&=q[y];now&=vis;q[y]|=q[x];fat[x]=y;
        for (int j=now.Next(0);j<=Q;j=now.Next(j)) vis.Unset(j),ans[j]=h[ID[i]];
    }for (int i=1;i<=Q;i++) printf("%d\n",ans[i]);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&Q);scanf("%s",s+1);for (int i=1;i<=(n>>1);i++) swap(s[i],s[n-i+1]);Make(s,n);
    for (int i=1;i<n;i++) ID[i]=i+1;sort(ID+1,ID+n,cmp);Solve(Q>>1);Solve(Q-(Q>>1));return 0;
}