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

万弘

2020-09-25 16:50:31

Solution

$ Q $ 次询问子串的最长 Border. $ |S|,Q\le 2\times 10^5 $ 求 $ [l,r] $ 的 border 等价于选一个最大的 $ i\in [l,r) $ ,使 $ \text{LCS}([1,i],[1,r])\ge i-l+1 $ 。比较难以处理的是,这个条件没有单调性。 考虑前缀的 $ \text{LCS} $ 在前缀树(也是 SAM 的 parent 树)上就是 LCA 表示的状态的长度。那么一种naive的做法就是先线段树合并处理 endpos 集合,然后枚举前缀树上的每个祖先 $ u $ ,在 $ u $ 的 endpos 集合中找一个在 $ [l,\min(r-1,l+len(u)-1)] $ 中且最大的位置。 理论最坏是平方。~~但是能过~~ 常用套路树上倍增在这里也没法用,因为从下到上 endpos 集合增大,但 $ len $ 值减小,同样不单调。 将问题转化一步,记表示 $ [1,r] $ 的节点为 $ u $ .等价于从**整个前缀树中选一个前缀节点** $ v $ (记其表示 $ [1,i] $ ),要求 $ len(\text{LCA}(u,v))\ge i-l+1 (\ i-len(\text{LCA}(u,v))<l)$且 $ i $ 尽量大。 用链分治来搞这件事。考虑先划分轻重链,一个点到根的路径划分为至多 $ \log_2 n $ 段(且每一段都是一条重链的子段)。 对于每一段,记其中最深的点(就是进去那个点)为 $ S $ ,链顶端为 $ top $ .则贡献为: - 从 $ S $ 的子树中取一个点 - 从重链上 $S$ 上面的点中选一个点 - 从重链上 $S$ 上面的点的轻子树中选一个点 容易发现,各条重链的贡献可能有重叠的部分,但一定没有遗漏,具体处理如下: 对于第一种情况,我们同样用线段树合并。每个询问的代价是 $ \mathcal O(\log^2 n) $ . 所有重链长度之和为 $ \mathcal O(n) $ ,所有轻子树大小之和是 $ \mathcal O(n\log n) $ ,所以后两种贡献总共涉及 $ \mathcal O(n\log n) $ 个点,这很好(因此我们的链分治才是有意义的,并且第一种情况必须用线段树合并做,否则这里的点数就爆炸了)。 维护一棵线段树,第 $i$ 个叶子存 $ i-len(LCA(u,S)) $ 的值($u$是表示 $[1,i]$ 的点)。将“重链上 $S$ 上面的点及其轻子树”中的前缀点全部在线段树上修改。对于 $S$ 上的每个询问,在线段树上找一个最大的 $i$ 满足 $i<r,i-len(LCA(u,S))<l$ 。这可以用线段树上二分做到。 将询问离线,放到每个段最深的点(进去的点)上,统一处理所有询问即可。 总时间复杂度 $ \mathcal O((n+Q)\log^2 n) $ ,空间复杂度 $ \mathcal O((n+Q)\log n) $ 一些细节:处理完一条重链后要撤销其在线段树上的修改。 另外,似乎网上的好几份代码都在我造的几组$|S|=10,Q=50$,字符集为$\{a,b\}$的数据下挂掉了。好像是他们的线段树上二分写的不太对(比如区间为空时) ```cpp const int INF=1e9; #define MAXN 400011 int n,root[MAXN],cnt=0; struct Endp { struct node{int lson,rson;}t[MAXN<<6|1]; #define rt t[num] void insert(int& num,un pos,un l=1,un r=n) { if(!num)num=++cnt; if(l==r)return; un mid=(l+r)>>1; if(pos<=mid)insert(rt.lson,pos,l,mid); else insert(rt.rson,pos,mid+1,r); } int Query(int num,int upp,un l=1,un r=n) { if(!num||upp<1)return 0; if(l==r)return l; un mid=(l+r)>>1; int res=0; if(upp>mid)res=Query(rt.rson,upp,mid+1,r); if(res)return res; return Query(rt.lson,upp,l,mid); } int merge(int x,int y,un l=1,un r=n) { if(!x||!y)return x|y; if(l==r)return x; int num=++cnt;un mid=(l+r)>>1; rt.lson=merge(t[x].lson,t[y].lson,l,mid); rt.rson=merge(t[x].rson,t[y].rson,mid+1,r); return num; } void debug(un l,un r,un num) { if(l==r){printf("%d ",l);return;} un mid=(l+r)>>1; if(rt.lson)debug(l,mid,rt.lson); if(rt.rson)debug(mid+1,r,rt.rson); } }endp; struct Segment_Tree { int t[MAXN<<2|1]; void build(un l=1,un r=n,un num=1) { rt=INF; if(l==r)return; else build(l,(l+r)>>1,num<<1),build(((l+r)>>1)+1,r,num<<1|1); } void modify(un pos,int val,un l=1,un r=n,un num=1) { if(l==r){rt=val;return;} un mid=(l+r)>>1; if(pos<=mid)modify(pos,val,l,mid,num<<1); else modify(pos,val,mid+1,r,num<<1|1); rt=min(t[num<<1],t[num<<1|1]); } int Query(int upp,int lim,un l=1,un r=n,un num=1) { if(rt>=lim)return 0; if(l==r)return rt<lim?l:0; un mid=(l+r)>>1; int res=0; if(upp>mid)res=Query(upp,lim,mid+1,r,num<<1|1); if(res)return res; return Query(upp,lim,l,mid,num<<1); } }sgt; struct SAM { int t[MAXN][26],pre[MAXN],len[MAXN],End[MAXN]; int last,tot; SAM(){last=tot=1;} #define from(u) for(int i=head[u],v=e[i].v;i;i=e[i].nxt,v=e[i].v) void extend(int w,int dex) { int pos=last,cur=++tot; len[cur]=len[pos]+1,last=cur,End[cur]=dex; while(pos&&!t[pos][w])t[pos][w]=cur,pos=pre[pos]; if(!pos){pre[cur]=1;return;} int nxt=t[pos][w]; if(len[nxt]==len[pos]+1)pre[cur]=nxt; else { int tmp=++tot; len[tmp]=len[pos]+1,memcpy(t[tmp],t[nxt],sizeof t[nxt]); pre[tmp]=pre[nxt],pre[cur]=pre[nxt]=tmp; while(pos&&t[pos][w]==nxt)t[pos][w]=tmp,pos=pre[pos]; } } struct one{int l,r,dex;}; std::vector<one>q[MAXN]; int ans[MAXN]; struct edge{int v,nxt;}e[MAXN<<1|1]; int cnt,head[MAXN]; void adde(int u,int v){e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;} int size[MAXN],dep[MAXN],mson[MAXN],top[MAXN]; void dfs1(int u) { size[u]=1; if(End[u])endp.insert(root[u],End[u]); from(u) { dep[v]=dep[u]+1,dfs1(v); size[u]+=size[v]; if(size[v]>size[mson[u]])mson[u]=v; root[u]=endp.merge(root[u],root[v]); } } void dfs2(int u,int now_top) { top[u]=now_top; if(mson[u])dfs2(mson[u],now_top); from(u) if(v!=mson[u])dfs2(v,v); } void build() { for(int i=2;i<=tot;++i)adde(pre[i],i); dfs1(1),dfs2(1,1); } void push(int u,int k) { if(End[u])sgt.modify(End[u],End[u]-k); from(u)push(v,k); } void back(int u) { if(End[u])sgt.modify(End[u],INF); from(u)back(v); } void solve(int S) { for(int u=S;u;u=mson[u]) { if(End[u])sgt.modify(End[u],End[u]-len[u]); from(u) if(v!=mson[u])push(v,len[u]); // printf("consider %d,len=%d\n",u,len[u]); for(auto x:q[u]) { int res=endp.Query(root[u],min(x.r-1,x.l+len[u]-1)); if(res>=x.l)umax(ans[x.dex],res-x.l+1); res=sgt.Query(x.r-1,x.l); if(res>=x.l)umax(ans[x.dex],res-x.l+1); } } for(int u=S;u;u=mson[u]) { if(End[u])sgt.modify(End[u],INF); from(u) if(v!=mson[u])back(v); } for(int u=S;u;u=mson[u]) from(u) if(v!=mson[u])solve(v); } }sam; int ed[MAXN]; char s[MAXN]; int main() { scanf("%s",s+1); n=strlen(s+1); for(int i=1;i<=n;++i)sam.extend(s[i]-'a',i),ed[i]=sam.last; sam.build(); // endp.debug(1,n,root[ed[2]]); // puts("?"); // printf("Res=%d\n",endp.Query(root[1],1)); int query=read(); for(int i=1;i<=query;++i) { int l=read(),r=read(); if(l==r){sam.ans[i]=0;continue;} int pos=ed[r]; while(pos)sam.q[pos].push_back({l,r,i}),pos=sam.pre[sam.top[pos]]; } sgt.build(); sam.solve(1); for(int i=1;i<=query;++i)printf("%d\n",sam.ans[i]); return 0; } ```