题解 P4482 【[BJWC2018]Border 的四种求法】

从6月份咕咕咕到现在的一道题 对了申请增强数据，似乎暴力蛤希可以通过现在的数据 不过还是好好写你的samn连吧 # 数据范围是假的,$n,m<=2×10^5$ _____ ### 前置芝士：sam(后缀自动机) ~~蛤？不会后缀自动机？出门左转你站膜板区，包教不包会~~ ### 前置芝士：线段树合并 ~~蛤？不会线段树合并，出门左转度娘，包教不包会~~ ## 本题题解 一句话题意:给你一个字符串求区间的border 那么我们见到这种题考虑在后缀自动机上乱搞几下看看能不能出来 那么当然要对先对这个字符串建一个后缀自动机出来，然后提取这只后缀自动机的parent树看看有没有什么性质 那么我们发现求(l,r)的border相当于找一个i满足限制$i-l+1 \leq lcs(r,i), l<i \leq r$并且让i最大 那么既然有这个lcs(两个前缀的最长公共后缀)这个限制条件的话我们就考虑能不能在后缀自动机上处理这个条件了 先让我们思考一个部分分，串是随机生成的，也就是说parent树的高度是log的 那么我们可以在parent树上暴力跳r这个前缀对应的节点到祖先的路径了，此时我们实际上在做的事情就是枚举lcs(r,i)的值（因为parent树的性质是两个前缀节点的lca的len值就是这两个点lcp的len值）, 那么我们把限制条件简单做个转化就是求子树中点的区间最大值问题(要求i这个节点必须在这个点的子树中,限制条件在lcs值确定的条件下就是一个区间最大值问题)这个东西使用线段树合并维护一下每个节点的right集合的区间最大值即可轻松搞定 那么我们解决了这个部分分之后来考虑parent树树高不是log的情况 其实我们的问题就是此时lcs的值的种类是$O(n)$级别的而不是$O(logn)$级别的 那么我们不妨强行给刚才的暴力套上一个树剖看看能不能做 那么我们发现r对应的前缀节点到根节点的路径会被拆分成若干条重链的**前缀**(前缀这点相当重要，不然这题不能做) 那么对于每一个重链前缀的底部那个点对答案的贡献我们可以套用线段树合并来解决这个问题，此时的复杂度是$O(log^2n)$的 接下来是每条重链前缀对答案的贡献了 那么我们可以顺着这个重链把整棵树拎起来，就像这张图一样  我们重新修改一下限制条件，把$i-l+1 \leq lcs(r,i)$改写成$i-lcs(r,i) < l$ 假设我们令key(i)=i-len(x)其中x是i和当前正在处理的重链的lca 那么我们的问题其实就是求在\[l,r)这个区间当中并且key值小于l的i的最大值 乍一看这东西似乎需要二维数据结构才能处理…… 但其实是不需要的……因为我们发现有个操作叫**线段树上二分**,如果我们在线段树上每个节点维护key(i)的区间最小值的话，此时我们就可以轻松的知道这个区间内是否存在一个合法的i值了，因此我们维护key(i)的区间最小值即可在一个log的时间复杂度内轻松出解了 那么问题来了，我们的线段树内需要存储这个重链前缀的所有轻子树的信息才能正确的出解，如果我们采取暴力dfs的方式来插入这个复杂度是对的吗？ (其实这个复杂度对不对无所谓的，因为无论如何你都可以使用线段树合并来强行插入点,不过这里其实暴力插点复杂度就是对的，并且可以让你少写一个线段树合并) 答案是肯定的，因为我们考虑每个点的被插入次数，显然一个点只会被插入这个点的轻边深度次，那么每个点的轻边深度都是$O(logn)$的自然总的插入次数就是$O(nlogn)$的 那么我们要做的就是先将parent树重链剖分之后离线每一个询问，对于重链底端的点将这log个询问二次离线之后使用线段树合并解决，对于每一个重链前缀的询问我们将着log个询问二次离线之后，采用下面这个算法解决(其实就是链分治，不过有人叫他树上启发式合并,不过这题和传统的树上启发式合并不一样) 假设我们正在处理某一条重链上的所有询问，那么我们先递归的分治和这条重链相关的所有重链，接下来从高到低的枚举重链上每一个点，将这个点的轻子树暴力dfs一遍在插入到维护区间key最小值的线段树中去,然后回答所有和当前重链前缀相关的询问 然后我们就做完了这道题，总的时间复杂度是$O(nlog^2n)$由于数据极其水所以跑的飞快 上代码~ ```C // luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<vector> using namespace std;const int N=2*1e5+10; char mde[N];int ans[N];int n;int m;int siz[2*N];int h[2*N];int top[2*N]; int v[2*N];int x[2*N];int ct;int al[2*N];int len[2*N];int fa[2*N];int ql[N];int qr[N]; inline void add(int u,int V){v[++ct]=V;x[ct]=al[u];al[u]=ct;} struct suffixautomaton//简易后缀自动机模板 { int mp[2*N][30];int ct; inline void ih(){for(int i=1;i<=n;i++)len[i]=i;ct=n+1;} inline void ins(int i,int c) { int p=(i==1)?n+1:i-1;for(;p&&mp[p][c]==0;p=fa[p])mp[p][c]=i; if(p==0){fa[i]=n+1;return;}int q=mp[p][c]; if(len[q]==len[p]+1){fa[i]=q;return;}len[++ct]=len[p]+1; for(int j=1;j<=26;j++)mp[ct][j]=mp[q][j]; for(;p&&mp[p][c]==q;p=fa[p])mp[p][c]=ct; fa[ct]=fa[q];fa[q]=fa[i]=ct;return; } inline void build(){for(int i=1;i<=ct;i++)add(fa[i],i);} }sam; inline int dfs1(int u)//重链剖分 { for(int i=al[u];i;i=x[i]) siz[u]+=dfs1(v[i]),h[u]=(siz[h[u]]<siz[v[i]])?v[i]:h[u];return ++siz[u]; } inline void dfs2(int u) { top[u]=top[u]?top[u]:u;if(h[u])top[h[u]]=top[u],dfs2(h[u]); for(int i=al[u];i;i=x[i])if(v[i]!=h[u])dfs2(v[i]);return; } namespace lt1//线段树合并 { int s[20*N][2];int ct;int va[20*N];int ali[18*N];int nx[18*N];int mct;int tw[18*N]; inline void pb(int p,int tim){tw[++mct]=tim;nx[mct]=ali[p];ali[p]=mct;} inline void ins(int p,int l,int r,int pos) { va[p]=pos;if(r-l==1)return;int mid=(l+r)/2; if(pos<=mid)ins(s[p][0]=++ct,l,mid,pos); else ins(s[p][1]=++ct,mid,r,pos);return; } inline int cmx(int p,int l,int r,int dl,int dr) { if((dl==l&&dr==r)||p==0){return va[p];}int mid=(l+r)/2;int res=0; if(dl<mid)res=max(res,cmx(s[p][0],l,mid,dl,min(dr,mid))); if(mid<dr)res=max(res,cmx(s[p][1],mid,r,max(dl,mid),dr));return res; } inline void mg(int p1,int p2,int l,int r) { if(r-l==1)return;int mid=(l+r)/2; if(s[p1][0]&&s[p2][0])mg(s[p1][0],s[p2][0],l,mid);else if(s[p2][0])s[p1][0]=s[p2][0]; if(s[p1][1]&&s[p2][1])mg(s[p1][1],s[p2][1],mid,r);else if(s[p2][1])s[p1][1]=s[p2][1]; va[p1]=max(va[s[p1][0]],va[s[p1][1]]); } inline void ih(){ct=n;for(int i=1;i<=n;i++)ins(i,0,n,i);} inline int dfs(int u) { int ret=(u<=n)?u:0; for(int i=al[u];i;i=x[i])if(ret)mg(ret,dfs(v[i]),0,n);else ret=dfs(v[i]); for(int i=ali[u],tv=tw[i];i;i=nx[i],tv=tw[i]) { int R=min(ql[tv]+len[u],qr[tv]); if(ql[tv]<R)ans[tv]=max(ans[tv],cmx(ret,0,n,ql[tv]-1,R-1)); }return ret; } } namespace lt2//链分治+线段树上二分 { int s[2*N][2];int ct;int va[2*N];int ali[18*N];int nx[18*N];int mct;int tw[18*N]; inline void pb(int p,int tim){tw[++mct]=tim;nx[mct]=ali[p];ali[p]=mct;} inline void ih(){for(int i=0;i<=2*N-10;i++)va[i]=0x3f3f3f3f;} inline void clr() { for(int i=1;i<=ct;i++)va[i]=0x3f3f3f3f; for(int i=1;i<=ct;i++)s[i][0]=s[i][1]=0;ct=1; } inline void ins(int p,int l,int r,int pos,int val) { va[p]=min(va[p],val);if(r-l==1)return;int mid=(l+r)/2; if(pos<=mid)ins(s[p][0]=s[p][0]?s[p][0]:++ct,l,mid,pos,val); else ins(s[p][1]=s[p][1]?s[p][1]:++ct,mid,r,pos,val); } inline int cmx(int p,int l,int r,int dl,int dr,int lim) { if(va[p]>=lim)return -0x3f3f3f3f;if(r-l==1)return r;int mid=(l+r)/2; if(mid<dr) { int ret=cmx(s[p][1],mid,r,max(dl,mid),dr,lim); if(ret!=-0x3f3f3f3f)return ret; }if(dl<mid)return cmx(s[p][0],l,mid,dl,min(dr,mid),lim);return -0x3f3f3f3f; } inline void subsolve(int u,int le)//暴力dfs插入 {if(u<=n)ins(1,0,n,u,u-le);for(int i=al[u];i;i=x[i])subsolve(v[i],le);} inline void solve(int u)//链分治 { for(int p=u;p;p=h[p]) for(int i=al[p];i;i=x[i])if(v[i]!=h[p])solve(v[i]);clr(); for(int p=u;p;p=h[p]) { for(int i=al[p];i;i=x[i])if(v[i]!=h[p])subsolve(v[i],len[p]); if(p<=n)ins(1,0,n,p,p-len[p]); for(int i=ali[p],tv=tw[i];i;i=nx[i],tv=tw[i]) {ans[tv]=max(ans[tv],cmx(1,0,n,ql[tv]-1,qr[tv]-1,ql[tv]));} } } } inline void stqr(int tim,int l,int r)//暴力跳重链，将询问二次离线 { if(l==r)return;ql[tim]=l;qr[tim]=r; for(int p=r;p;p=fa[top[p]]){lt1::pb(p,tim);lt2::pb(p,tim);} } int main() { scanf("%s",mde+1);for(n=1;mde[n+1]!='\0';n++);sam.ih();lt2::ih(); for(int i=1;i<=n;i++)sam.ins(i,mde[i]-'a'+1);sam.build(); dfs1(n+1);dfs2(n+1);scanf("%d",&m); for(int i=1,l,r;i<=m;i++)scanf("%d%d",&l,&r),stqr(i,l,r); lt1::ih();lt1::dfs(n+1);lt2::solve(n+1); for(int i=1;i<=m;i++)if(ans[i]==0)printf("0\n");else printf("%d\n",ans[i]-ql[i]+1);return 0;//拜拜程序~ } ```