题解 P7046 【「MCOI-03」诗韵】

万弘

2020-11-03 19:46:25

Solution

在[我的博客](https://oierwanhong.cc/2020/11/03/Luogu%20P7046%20%E3%80%8CMCOI-03%E3%80%8D%E8%AF%97%E9%9F%B5/)中查看 给一个串 $ T $ ,和一个大小为 $ m $ 的子串集合 $ \{T[l_i,r_i]|1\le i\le m\} $ ,记为 $ S $ .和一个定值 $ K $ . 定义 $ \text{CS}(A) $ 表示 $ A $ 中所有串的 CS(公共后缀)的集合。 求 $ |{\bigcup_{A\subset S,|A|>K}}\ \text{CS(A)}| $ 和 $ \max_{A\subset S,|A|>K}\max(\text{CS(A)}) $ . $ |T|\le 5\times 10^5,m\le 5\times 10^5,0\le K\le m. $ 可能形式化之后反而不太清楚了,可以去看看原题面。 这里介绍一种重工业做法。 先建 T 的 SAM。对于每个 $ T[l_i,r_i] $ 我们找到其在SAM上的对应节点(最浅的满足 $ maxlen\ge r_i-l_i+1 $ 的点)。如果这个串的长度恰好等于该点的 $ maxlen $ ,那么其贡献就是该点到根的路径上所有点出现次数+1;否则对这个点来说,长度 $ \le r_i-l_i+1 $ 的串出现次数+1,然后祖先的出现次数+1.一个点表示的不同串的出现次数不同很难搞,干脆直接给这个子串新建一个点,放在原本的点和原本的父亲中间,就能保证每个点表示的所有串出现次数都相同(这样加点后我们仍然保留了parent 树最重要的性质,即祖先表示的串都是当前串的后缀) 那么现在我们就要支持三种操作: 0. 在一条链上找到一个最浅的点满足 $ maxlen\ge r-l+1 $ .同时可能要在这个点和其父亲中加入一个点 1. 链上所有点出现次数+1 2. 询问整棵树上所有满足出现次数 $ >k $ 的子串的数量和最大长度。 ~~什么毒瘤~~ 对于操作0,由于要动态加点,倍增没法维护,那就用 LCT 维护,并令 splay 上每个点维护一下子树中最大len值,找一个最浅的满足 $ maxlen\ge r-l+1 $ 的点就先`access`然后在 splay 上二分找。 此外可以发现我们先做完所有0操作再去做1和2不会对答案产生任何影响,即对于操作1,2,树是静态的。 但还是不太可做,强行做可能会出现树剖然后树套树的诡异东西。转而考虑离线,对加点后的 SAM 上每个点求其出现次数 $ >k $ 的最早时间。这东西我们可以整体二分,然后链加变成单点修改询问子树和,就可以在dfs序上建树状数组维护了。 令加点后的 parent 树点数为 $ n $ ,则复杂度分析如下: 0操作的总复杂度是 $ \mathcal O(m\log n) $ ,log 是 LCT 的 log。LCT 只要用有根树 LCT,所以常数也不太大。 1和2操作的总复杂度 $ \mathcal O((n+m)\log^ 2n) $ .由于树状数组常数爆小,所以能过。 ```cpp /**********/ #define MAXN 2000011 int n,m,k,dfn[MAXN],edn[MAXN],cur; namespace BIT { int t[MAXN]; #define lowb (i&-i) void modify(int i,int k) { while(i<=cur)t[i]+=k,i+=lowb; } int Qsum(int i) { int res=0; while(i)res+=t[i],i-=lowb; return res; } int Qsum(int l,int r){ return Qsum(r)-Qsum(l-1);} } namespace SAM { int t[MAXN/2][26],pre[MAXN],len[MAXN]; int last=1,tot=1; void extend(int w) { int pos=last,cur=++tot; len[cur]=len[pos]+1,last=cur; 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 LCT { int fa[MAXN],son[MAXN][2],mx[MAXN]; void init(){for(int i=2;i<=SAM::tot;++i)fa[i]=SAM::pre[i];} bool not_root(int x){return son[fa[x]][0]==x||son[fa[x]][1]==x;} void pushup(int x){mx[x]=max(SAM::len[x],max(mx[son[x][0]],mx[son[x][1]]));} void rotate(int x) { int y=fa[x],z=fa[y],k=(son[y][1]==x); if(not_root(y))son[z][son[z][1]==y]=x; fa[x]=z; son[y][k]=son[x][!k],fa[son[x][!k]]=y; son[x][!k]=y,fa[y]=x; pushup(y); } void splay(int x) { while(not_root(x)) { int y=fa[x]; if(not_root(y))rotate((son[y][1]==x)==(son[fa[y]][1]==y)?y:x); rotate(x); } pushup(x); } void access(int x) { for(int y=0;x;y=x,x=fa[x]) splay(x),son[x][1]=y; } void link(int x,int y){access(x),splay(x),fa[x]=y;} void cutfa(int x){access(x),splay(x), fa[son[x][0]]=0,son[x][0]=0,pushup(x);} int find(int x,int len) { access(x),splay(x); while(1) { if(mx[son[x][0]]>=len)x=son[x][0]; if(SAM::len[x]>=len)break; x=son[x][1]; } return splay(x),x; } }lct; struct edge{int v,nxt;}e[MAXN<<1|1]; int cnt=0,last[MAXN]; void adde(int u,int v){e[++cnt].v=v,e[cnt].nxt=last[u],last[u]=cnt;} void dfs(int u) { dfn[u]=++cur; for(int i=last[u];i;i=e[i].nxt) { int v=e[i].v; if(v!=SAM::pre[u])dfs(v); } edn[u]=cur; } int ed[MAXN]; char ss[MAXN]; struct one{int u,r;}a[MAXN],la[MAXN],ra[MAXN]; int res[MAXN],node[MAXN]; ll c[MAXN],mx[MAXN]; void solve(int begin,int end,int dep,int l,int r) { if(begin>end)return; if(l==r) { for(int i=begin;i<=end;++i)res[a[i].u]=l; return; } int mid=(l+r)>>1,itl=0,itr=0; for(int i=l;i<=mid;++i) if(node[i])BIT::modify(dfn[node[i]],1); for(int i=begin;i<=end;++i) { int c=BIT::Qsum(dfn[a[i].u],edn[a[i].u]); if(a[i].r<=c)la[++itl]=a[i]; else a[i].r-=c,ra[++itr]=a[i]; } for(int i=l;i<=mid;++i) if(node[i])BIT::modify(dfn[node[i]],-1); for(int i=1;i<=itl;++i)a[begin+i-1]=la[i]; for(int i=1;i<=itr;++i)a[begin+itl+i-1]=ra[i]; solve(begin,begin+itl-1,dep+1,l,mid),solve(begin+itl,end,dep+1,mid+1,r); } bool vis[MAXN]; int main() { n=read(),m=read(),k=read(); scanf("%s",ss+1); for(int i=1;i<=n;++i)SAM::extend(ss[i]-'a'),ed[i]=SAM::last; lct.init(); for(int i=1;i<=m;++i) { int l=read(),r=read(); int p=lct.find(ed[r],r-l+1); if(SAM::len[p]==r-l+1)node[i]=vis[p]?0:p; else{SAM::len[++SAM::tot]=r-l+1,SAM::pre[SAM::tot]=SAM::pre[p],SAM::pre[p]=SAM::tot,lct.cutfa(p),lct.link(SAM::tot,SAM::pre[SAM::tot]),lct.link(p,SAM::tot);node[i]=SAM::tot;} vis[node[i]]=1; } for(int i=1;i<=SAM::tot;++i)a[i]=one{i,k+1},adde(SAM::pre[i],i); dfs(1); SAM::len[0]=-1; solve(1,SAM::tot,0,1,m+1); for(int i=1;i<=SAM::tot;++i)c[res[i]]+=SAM::len[i]-SAM::len[SAM::pre[i]],umax(mx[res[i]],SAM::len[i]); for(int i=1;i<=m;++i)c[i]+=c[i-1],umax(mx[i],mx[i-1]),printf("%lld %lld\n",c[i],mx[i]); return 0; } ```