正題

題目鏈接:https://www.luogu.com.cn/problem/P7046

---

題目大意

給出一個長度為 $n$ 的字符串，然后 $m$ 次把它的一個子串加入集合。如果一個字符串在這個集合中作為字符串的后綴出現次數大于 $k$ 那么這個字符串就會被計入貢獻。
每次求計入貢獻的字符串數和最長長度。

$1\le n,m\le 5\times 10^5,0\le k<n$。

---

解題思路

考慮在parents樹上如果能定位到一個節點的字符串那么它的后綴就是它到根的路徑。

但是可能定位不到根，一種暴力的做法是每條邊上建一個線段樹然后暴力改。但是這樣很麻煩可以考慮讓每個詢問一定能定位到一個節點。

我們直接建好樹然后每次把詢問倍增掛到對應的邊上用set儲存，然后再重新建一棵包含每個節點的樹。

那么現在問題就變為了統計子樹權值大于 $k$ 的節點了，因為每個點到根的路徑上滿足條件的邊一定是一段后綴，而每個節點最多統計一次，所以我們直接每次倍增找到最上面的沒有統計的節點用樹狀數組+$dfs$ 序判斷是否合法就好了。

時間復雜度：$O(n\log n)$（默認 $n,m$ 同級）

---

code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<set> #define lowbit(x) (x&-x) using namespace std; const int M=1e6+10,N=2e6+10,T=21; struct node{int to,next; }a[N]; int n,m,k,last,cnt,tot,ans2;long long ans1; int ch[M][26],len[N],fa[N],L[M],R[M],p[M],las[M]; int ls[N],v[N],pos[N],f[N][T],rfn[N],ed[N],dos[M]; set<int> ct[M];vector<int> q[M];char s[M]; set<int>::iterator it; void Insert(int c){int p=last,np=last=++cnt;len[np]=len[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{int q=ch[p][c];if(len[q]==len[p]+1)fa[np]=q;else{int nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;}}return; } void work(int p,int l,int r){int x=pos[r];for(int i=T-1;i>=0;i--)if(len[f[x][i]]>=r-l+1)x=f[x][i];if(ct[x].count(r-l+1))return;ct[x].insert(r-l+1);q[x].push_back(p);return; } void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } bool cmp(int x,int y) {return R[x]-L[x]+1<R[y]-L[y]+1;} bool cMp(int x,int y) {return len[x]<len[y];} void dfs(int x){rfn[x]=++cnt;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;f[y][0]=x;dfs(a[i].to);}ed[x]=cnt;return; } struct TreeBinary{int t[N];void Change(int x,int val){while(x<=n){t[x]+=val;x+=lowbit(x);}return;}int Ask(int x){int ans=0;while(x){ans+=t[x];x-=lowbit(x);}return ans;} }B; int main() {scanf("%d%d%d",&n,&m,&k);scanf("%s",s+1);cnt=last=1;for(int i=1;i<=n;i++)Insert(s[i]-'a'),pos[i]=last;for(int i=1;i<=cnt;i++)f[i][0]=fa[i];for(int j=1;j<T;j++)for(int i=1;i<=cnt;i++)f[i][j]=f[f[i][j-1]][j-1];for(int i=1;i<=m;i++){scanf("%d%d",&L[i],&R[i]);work(i,L[i],R[i]);}for(int i=1;i<=cnt;i++)p[i]=i,ct[i].insert(len[i]);sort(p+1,p+1+cnt,cMp);int pnt=cnt;cnt=1;las[1]=1;for(int i=2;i<=pnt;i++){int x=p[i];sort(q[x].begin(),q[x].end(),cmp);int z=0;las[x]=las[fa[x]];it=ct[x].begin();while(1){++cnt;addl(las[x],cnt);las[x]=cnt;int W=*it;len[cnt]=*it;while(z<q[x].size()&&R[q[x][z]]-L[q[x][z]]+1<=W)dos[q[x][z]]=cnt,z++;it++;if(it==ct[x].end())break;}}n=cnt;cnt=0;dfs(1);v[0]=1;len[0]=-1;for(int j=1;j<T;j++)for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1];for(int i=1;i<=m;i++){int p=dos[i];if(!p){printf("%lld %d\n",ans1,ans2);continue;}B.Change(rfn[p],1);if(v[p]){printf("%lld %d\n",ans1,ans2);continue;}while(!v[p]){int x=p;for(int j=T-1;j>=0;j--)if(!v[f[x][j]])x=f[x][j];int w=B.Ask(ed[x])-B.Ask(rfn[x]-1);if(w>k){v[x]=1;ans1+=len[x]-len[f[x][0]];ans2=max(ans2,len[x]);}else break;}printf("%lld %d\n",ans1,ans2);}return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P7046-「MCOI-03」诗韵【SAM,倍增,树状数组】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。