LOJ

思路

建出反串的后缀树，发现询问就是问一个区间的点的\(lca\)的深度最大值。

一种做法是dfs的时候从下往上合并\(endpos\)集合，发现插入一个点的时候只需要把与前驱后继的贡献算进去就可以了。

另一种做法是从小到大枚举结尾，把到根的一条链全都打上自己的标记，并且如果原来有标记就更新答案，发现可以用LCT维护。

本质其实差不多。

代码

我又傻傻地把树状数组能做的事搞成了线段树……

#include<bits/stdc++.h>
clock_t t=clock();
namespace my_std{
    using namespace std;
    #define pii pair<int,int>
    #define fir first
    #define sec second
    #define MP make_pair
    #define rep(i,x,y) for (int i=(x);i<=(y);i++)
    #define drep(i,x,y) for (int i=(x);i>=(y);i--)
    #define go(x) for (int i=head[x];i;i=edge[i].nxt)
    #define templ template<typename T>
    #define sz 202020
    typedef long long ll;
    typedef double db;
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
    templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
    templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
    templ inline void read(T& t)
    {
        t=0;char f=0,ch=getchar();double d=0.1;
        while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
        while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
        t=(f?-t:t);
    }
    template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
    char __sr[1<<21],__z[20];int __C=-1,__zz=0;
    inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
    inline void print(register int x)
    {
        if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
        while(__z[++__zz]=x%10+48,x/=10);
        while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
    }
    void file()
    {
        #ifdef NTFOrz
        freopen("a.in","r",stdin);
        #endif
    }
    inline void chktime()
    {
        #ifndef ONLINE_JUDGE
        cout<<(clock()-t)/1000.0<<'\n';
        #endif
    }
    #ifdef mod
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
    ll inv(ll x){return ksm(x,mod-2);}
    #else
    ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
    #endif
//  inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

int n,m;
char s[sz];

namespace SegmentTree
{
    int mx[sz<<2];
    #define ls k<<1
    #define rs k<<1|1
    #define lson ls,l,mid
    #define rson rs,mid+1,r
    void modify(int k,int l,int r,int x,int y)
    {
        if (!x) return;
        chkmax(mx[k],y);
        if (l==r) return;
        int mid=(l+r)>>1;
        if (x<=mid) modify(lson,x,y);
        else modify(rson,x,y);
    }
    int query(int k,int l,int r,int x,int y)
    {
        if (x<=l&&r<=y) return mx[k];
        int mid=(l+r)>>1,ret=0;
        if (x<=mid) chkmax(ret,query(lson,x,y));
        if (y>mid) chkmax(ret,query(rson,x,y));
        return ret;
    }
    #undef ls
    #undef rs
    #undef lson
    #undef rson
}
using namespace SegmentTree;

namespace LCT
{
    int rt[sz],val[sz],fa[sz],ch[sz][2];
    int dep[sz];
    #define ls ch[x][0]
    #define rs ch[x][1]
    void pushup(int x){rt[x]=(ls?rt[ls]:x);}
    int get(int x){return ch[fa[x]][1]==x;}
    int nroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}
    void rotate(int x)
    {
        int y=fa[x],z=fa[y],k=get(x),w=ch[x][!k];
        if (nroot(y)) ch[z][get(y)]=x;ch[x][!k]=y;ch[y][k]=w;
        if (w) fa[w]=y;fa[y]=x;fa[x]=z;
        pushup(y),pushup(x);
    }
    void splay(int x){for (int y;y=fa[x],nroot(x);rotate(x)) if (nroot(y)) rotate(get(x)==get(y)?y:x);}
    void access(int x,int pos)
    {
        int _x=x;
        for (int y=0;x;x=fa[y=x])
        {
            splay(x);
            if (rs) val[rt[rs]]=val[rt[x]];
            rs=y,modify(1,1,n,val[rt[x]],dep[x]);
        }
        splay(_x),val[rt[_x]]=pos;
    }
    #undef ls
    #undef rs
}

namespace SAM
{
    struct hh{int link,len,ch[2];}a[sz];
    int cnt=1,lst=1;
    int add(int c)
    {
        int cur=++cnt,p=lst;lst=cur;
        a[cur].len=a[p].len+1;
        #define v a[p].ch[c]
        while (p&&!v) v=cur,p=a[p].link;
        if (!p) return a[cur].link=1,cur;
        int q=v;
        if (a[q].len==a[p].len+1) return a[cur].link=q,cur;
        int t=++cnt;a[t]=a[q];a[t].len=a[p].len+1;a[q].link=a[cur].link=t;
        while (p&&v==q) v=t,p=a[p].link;
        #undef v
        return cur;
    }
    void work(){rep(i,1,cnt) LCT::fa[i]=a[i].link,LCT::dep[i]=a[i].len,LCT::rt[i]=i;}
}
int pos[sz];

struct hh{int l,r,id;const bool operator < (const hh &x) const {return r<x.r;}}q[sz];
int ans[sz];

int main()
{
    file();
    read(n,m);
    cin>>(s+1);
    rep(i,1,n) pos[i]=SAM::add(s[i]-'0');
    SAM::work();
    int x,y;
    rep(i,1,m) read(x,y),q[i]=(hh){x,y,i};
    sort(q+1,q+m+1);
    int p=1;
    rep(i,1,n)
    {
        LCT::access(pos[i],i);
        while (p<=m&&q[p].r==i) ans[q[p].id]=query(1,1,n,q[p].l,q[p].r),++p;
    }
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}