题目描述
给一个小写字母字符串 S ，q 次询问每次给出 l,r ，求 s[l..r] 的 Border 。
Border: 对于给定的串 s ，最大的 i 使得 s[1..i] = s[|s|-i+1..|s|], |s| 为 s 的长度。
题解
这题的描述很短，给人一种很可做的假象。
暴力1：每次对区间lr做一次KMP，求出border数组，复杂度nq。
暴力2：构建后缀自动机，用线段树合并维护出right集合考虑到两个串的最长后缀为他们在parent树上的LCA的len，所以我们可以在parent树上跳father，相当于枚举LCA，那么如果有匹配的点，则一定满足：
i-len[LCA]+1<=l => i=len[LCA]<l => i<l+len[LCA] i>=l&&i<r （i为我们要求的点，l为询问的左端点，LCA为i和r的LCA）
所以我们只需要在线段树上查子树内查询满足上述条件的最大的i就可以了，复杂度最好qlogn，最差qn。
这两种暴力好像差不多。。
我们观察到第二种暴力它的瓶颈在于枚举LCA，但查询只需要一个log，我们可以想一些办法把复杂度均摊一下。
链分治
这就是这道题的重头戏，它用到了一个重要的性质，我们将一棵树重链剖分之后，从根到任意一点的路径上，轻重链切换的次数是不超过log的。
然后我们就可以用它搞一些事情。
比如说这道题，我们可以把询问拆成log个挂在它到根的路径上，每条链挂一个，对于当前链，挂在原来的点上，对于上面的链，挂在链的最底端。
其实我们也是相当于在枚举lca，对于挂上去的点，我们可以直接用上面暴力2的方法统计答案，复杂度是log的，那么对于其他点，我们如何统计答案呢？
我们可以发现一个性质，就是对于最底端这个点向上的其他链上的点作为LCA时，答案只会出现在这个点除了重儿子以外的子树内以及自己，因为重链底下的子树我们刚才已经处理过了。
所以我们的做法就是，对于每一条重链，自顶至底处理，然后我们把式子移个项
i-len[LCA]<l
我们把这个点的所有非重儿子所在子树中的点的i-len[LCA]全部加进以i为下标的线段树中，然后一直往下合并，那么每到一个点，它就保存了它到重链顶端所有LCA的信息，然后我们直接询问挂在这个点的询问就可以了。
但每次暴力加的复杂度对吗？
树上启发式合并(DSU on tree)
这个操作的原理和上面的一模一样，都是利用了轻重链log的性质。
主要思想就是，维护重链，轻链暴力，考虑一个点会被暴力做多少次，它到根的路径上轻重链切换的时候才会产生一次，根据上面的结论，这是log的。
于是我们在nlog2的时间内做完了这道题。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#define N 400002
#define inf 2e9
using namespace std;
vector<int>vec[N];
char s[N];
int last,cnt,n,tot,head[N],topp,ls[N*],rs[N*],tr[N*],T[N<<],len[N],id[N],ch[N][],fa[N],f[N];
int L[N*],R[N*],size[N],top[N],son[N],ans[N],q,rt[N],_id[N],mi[N*];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct edge{int n,to;}e[N<<];
struct node{int l,r;}qu[N];
inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot;}
inline int newnode(){
int x=++topp;tr[x]=inf;ls[x]=rs[x]=;
return x;
}
void ins(int &cnt,int l,int r,int x){
if(!cnt)cnt=++topp,mi[cnt]=inf;mi[cnt]=min(mi[cnt],x);
if(l==r)return;
int mid=(l+r)>>;
if(mid>=x)ins(L[cnt],l,mid,x);
else ins(R[cnt],mid+,r,x);
}
int merge(int cnt,int pre,int l,int r){
if(!cnt||!pre)return cnt^pre;
int p=++topp;mi[p]=min(mi[cnt],mi[pre]);
if(l==r)return p;
int mid=(l+r)>>;
L[p]=merge(L[cnt],L[pre],l,mid);
R[p]=merge(R[cnt],R[pre],mid+,r);
return p;
}
int prequery(int cnt,int l,int r,int ql,int qr,int x){
if(mi[cnt]>=x)return ;
if(l==r)return (l>=ql&&l<=qr)?l:;
int mid=(l+r)>>;
if(mid<qr&&mi[R[cnt]]<x){
int num=prequery(R[cnt],mid+,r,ql,qr,x);
if(num)return num;
}
else if(mid>=ql&&mi[L[cnt]]<x)return prequery(L[cnt],l,mid,ql,qr,x);
return ;
}
inline void insert(int x,int tag){
int p=last,np=++cnt;last=np;len[np]=len[p]+;
ins(T[np],,n,tag);id[tag]=np;_id[np]=tag;
for(;p&&!ch[p][x];p=fa[p])ch[p][x]=np;
if(!p)fa[np]=;
else{
int q=ch[p][x];
if(len[p]+==len[q])fa[np]=q;
else{
int nq=++cnt;len[nq]=len[p]+;
memcpy(ch[nq],ch[q],sizeof(ch[nq]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;ch[p][x]==q;p=fa[p])ch[p][x]=nq;
}
}
}
void ins2(int &cnt,int l,int r,int x,int y){
if(!cnt)cnt=newnode();tr[cnt]=min(tr[cnt],y);
if(l==r)return;
int mid=(l+r)>>;
if(mid>=x)ins2(ls[cnt],l,mid,x,y);
else ins2(rs[cnt],mid+,r,x,y);
}
int merge2(int cnt,int pre,int l,int r){
if(!cnt||!pre)return cnt^pre;
int mid=(l+r)>>;tr[cnt]=min(tr[cnt],tr[pre]);
if(l==r)return cnt;
ls[cnt]=merge2(ls[cnt],ls[pre],l,mid);
rs[cnt]=merge2(rs[cnt],rs[pre],mid+,r);
return cnt;
}
int query(int cnt,int l,int r,int L,int R,int x){ ///!!!
if(l==r)return (l>=L&&l<=R)?l:;
if(tr[cnt]>=x)return ;
int mid=(l+r)>>;
if(mid<R&&tr[rs[cnt]]<x){
int num=query(rs[cnt],mid+,r,L,R,x);
if(num)return num;
}
if(tr[ls[cnt]]<x&&mid>=L)return query(ls[cnt],l,mid,L,R,x);
return ;
}
void dfs1(int u){
size[u]=;
for(int i=head[u];i;i=e[i].n){
int v=e[i].to;
f[v]=u;dfs1(v);
size[u]+=size[v];
if(size[v]>size[son[u]])son[u]=v;
}
}
void dfs2(int u){
if(!top[u])top[u]=u;if(son[u])top[son[u]]=top[u],dfs2(son[u]);
for(int i=head[u];i;i=e[i].n){
if(e[i].to!=son[u])dfs2(e[i].to);
T[u]=merge(T[u],T[e[i].to],,n);
}
}
void prework(int cnt,int l,int r,int top){
if(l==r){ins2(rt[top],,n,l,l-len[top]);return;}
int mid=(l+r)>>;
if(L[cnt])prework(L[cnt],l,mid,top);
if(R[cnt])prework(R[cnt],mid+,r,top);
}
void solve(int u){
for(int i=head[u];i;i=e[i].n)solve(e[i].to);
if(top[u]==u){
int x=u;
while(x){
for(int i=head[x];i;i=e[i].n){
int v=e[i].to;if(v==son[x])continue;
prework(T[v],,n,x);
}
for(int i=;i<vec[x].size();++i){
int l=qu[vec[x][i]].l,r=qu[vec[x][i]].r;
ans[vec[x][i]]=max(ans[vec[x][i]],query(rt[x],,n,l,r-,l));
}
if(son[x])rt[son[x]]=merge2(rt[son[x]],rt[x],,n);
x=son[x];
}
}
}
int main(){
tr[]=mi[]=inf;
scanf("%s",s+);n=strlen(s+);
cnt=last=;
for(int i=;i<=n;++i)insert(s[i]-'a',i);
for(int i=;i<=cnt;++i)add(fa[i],i);
dfs1();dfs2();
q=rd();topp=;//合并完后的第一类线段树不会新增节点了，所以把它清空。
for(int i=;i<=q;++i){
qu[i].l=rd();qu[i].r=rd();int x=id[qu[i].r];
while(x){
vec[x].push_back(i);
ans[i]=max(ans[i],prequery(T[x],,n,qu[i].l,qu[i].r-,qu[i].l+len[x]));//!!!
x=f[top[x]];
}
}
for(int i=;i<=n;++i)ins2(rt[id[i]],,n,i,);
solve();
for(int i=;i<=q;++i)printf("%d\n",ans[i]?ans[i]-qu[i].l+:);
return ;
}