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

$\text{SAM}$ 好题！前排膜拜出题人。 #### 前置芝士：SAM、树上倍增、线段树上二分 看到题目中韵脚的定义是最长公共后缀长度，而且 $N\le 5\times 10^5$ 只需 $\text{2.33s}$，可以猜测是一道正宗的 $\text{SAM}$ 题。 对字符串建出 $\text{SAM}$，用树上倍增将串挂在 $\text{SAM}$ 的对应位置。若直接在线做，要支持维护链并的数据结构，~~总之我不会~~，所以考虑反着做，算每个节点的贡献。因为只有插入操作没有删除操作，所以一个节点的贡献最多只有 $|P|+1$ 种，$|P|$ 为挂在这个结点串的个数。算出这些贡献对应的时间轴区间，就可以在答案序列差分一下，最后统一算。 那么问题就转化成算一个节点不同贡献的时间轴区间。 由于赛中没打，赛后想了两天，想到了一种比较好写的方法。 $\text{SAM}$ 上一个节点对应的长度区间是 $(len_{fa_p},len_p]$。设挂在这个节点的长度序列为 $l_0=len_{fa_p},l_1,l_1,...,l_{|P|},l_{|P|+1}=len_p$，我们算 $l_{i}-l_{i-1}(1\le i\le |P|+1)$ 的贡献。 使这段有贡献的最小的 $T$ 要满足从这个时刻开始，这个节点上 $\ge l_i$ 的串的个数+这个节点在 $\text{parent}$ 树上子树（不包括此节点）的串的个数 $>K$。前者可以在这个节点从大到小枚举，线段树上单点修改；后者可以线段树合并或者 $\text{dfs}$ 序上主席树。直接二分+验证显然会 $\text{TLE}$，那么可以在线段树上二分。时间 $\mathcal{O}((n+m)\log n)$。 ~~自己感觉写的还是挺简洁的~~ 注意，空串要特判。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; #define fi first #define se second const int maxn=1000005; const int inf=0x3f3f3f3f; int n,m,k,ch[maxn][26],fa[maxn],len[maxn],pos[maxn],f[maxn][21],last=1,cnt=1; char s[maxn]; ll ans[maxn][2]; vector<int> g[maxn]; vector<pii> p[maxn]; inline void insert(int c,int id) { int p=last,q=++cnt; len[q]=len[p]+1,last=pos[id]=q; for(;p && !ch[p][c];p=fa[p]) ch[p][c]=q; if(!p) fa[q]=1; else { int r=ch[p][c]; if(len[r]==len[p]+1) fa[q]=r; else { int s=++cnt; len[s]=len[p]+1; memcpy(ch[s],ch[r],sizeof(ch[r])); fa[s]=fa[r],fa[r]=fa[q]=s; for(;p && ch[p][c]==r;p=fa[p]) ch[p][c]=s; } } } inline void jump(int l,int r,int id) { int L=r-l+1,x=pos[r]; for(int i=20;i>=0;i--) if(f[x][i] && len[f[x][i]]>=L) x=f[x][i]; p[x].push_back(pii(L,id)); } int rt[maxn],ls[maxn*24],rs[maxn*24],sum[maxn*24],S[maxn<<2],sz; void modify(int rt,int l,int r,int u,int v) { S[rt]+=v; if(l==r) return; int mid=(l+r)>>1; if(u<=mid) modify(rt<<1,l,mid,u,v); else modify(rt<<1|1,mid+1,r,u,v); } void update(int &rt,int l,int r,int u,int v) { if(!rt) rt=++sz,ls[rt]=rs[rt]=sum[rt]=0; sum[rt]+=v; if(l==r) return; int mid=(l+r)>>1; if(u<=mid) update(ls[rt],l,mid,u,v); else update(rs[rt],mid+1,r,u,v); } int merge(int x,int y) { if(!x || !y) return x|y; ls[x]=merge(ls[x],ls[y]); rs[x]=merge(rs[x],rs[y]); sum[x]=sum[ls[x]]+sum[rs[x]]; return x; } int query(int u,int v,int l,int r,int k) { if(l==r) return sum[u]+S[v]<=k?l:0; int mid=(l+r)>>1,siz=sum[ls[u]]+S[v<<1]; if(k<siz) return query(ls[u],v<<1,l,mid,k); else return max(mid,query(rs[u],v<<1|1,mid+1,r,k-siz)); } void dfs(int x) { for(auto y:g[x]) dfs(y),rt[x]=merge(rt[x],rt[y]); sort(p[x].begin(),p[x].end()); int sz=(int)p[x].size(); for(int i=sz-1;i>0;i--) if(p[x][i].fi!=p[x][i-1].fi) { if(p[x][i].se>0 && p[x][i].se<=m) modify(1,1,m,p[x][i].se,1); if(sum[rt[x]]+S[1]>k) { int T=query(rt[x],1,1,m,k)+1; if(T<=m) ans[T][0]=max(ans[T][0],(ll)p[x][i].fi),ans[T][1]+=p[x][i].fi-p[x][i-1].fi; } } for(int i=sz-1;i>0;i--) if(p[x][i].fi!=p[x][i-1].fi && p[x][i].se>0 && p[x][i].se<=m) modify(1,1,m,p[x][i].se,-1),update(rt[x],1,m,p[x][i].se,1); } int main() { scanf("%d%d%d%s",&n,&m,&k,s+1); for(int i=1;i<=n;i++) insert(s[i]-'a',i); for(int i=2;i<=cnt;i++) g[fa[i]].push_back(i); for(int i=1;i<=cnt;i++) f[i][0]=fa[i]; for(int j=1;j<=20;j++) for(int i=1;i<=cnt;i++) f[i][j]=f[f[i][j-1]][j-1]; for(int i=2;i<=cnt;i++) p[i].push_back(pii(len[fa[i]],0)); int l,r; for(int i=1;i<=m;i++) scanf("%d%d",&l,&r),jump(l,r,i); for(int i=2;i<=cnt;i++) p[i].push_back(pii(len[i],inf)); dfs(1),ans[k+1][1]++; for(int i=1;i<=m;i++) ans[i][0]=max(ans[i][0],ans[i-1][0]),ans[i][1]+=ans[i-1][1],printf("%lld %lld\n",ans[i][1],ans[i][0]); return 0; } ```