Description

給定 \(N\) 個姓名串和 \(M\) 個點名串。詢問每個點名串點到了多少姓名和每個姓名串被點到了幾次。\(N\leq 5\cdot 10^4,M\leq 10^5\)。

Sol

卡了我一周90分的題原來是數組開小我就艸了我就

最開始以為是 \(AC\) 自動機裸題但是細想了一下發現并不會，還是老老實實想 \(SA\) 。

首先要把這些串連在一起，然后跑一遍 \(SA\) ，可以先求出每個點名串到底點到了多少姓名串（也就是說在 \(SA\) 上有多少位置和點名串的 \(LCP\) 是點名串自己），發現這個在 \(SA\) 上是一段區間，可以二分左右端點求出。時間復雜度 \(O(n\log n)\)。

然后這兩問分別考慮，第一問就相當于區間數顏色，可以離線+樹狀數組解決。就是按照區間右端點排序，如果當前的值 \(a[i]=x\)，那就在 \(i\) 處 \(+1\)，在 \(x\) 上一次出現的位置 \(las[x]\) 處 \(-1\)。然后統計區間 \([L,R]\) 直接樹狀數組上查就好了。這個算法的核心思路是保證相同數字的貢獻只有 \(1\)，也就是說每個顏色只會在前綴和數組中出現 \(1\) 次。這部分時間復雜度 \(O(n\log n)\)。

第二問就是求每個顏色被幾個不同的區間覆蓋了。這個同樣離線，對于一個區間 \([L,R]\)，我們在掃到 \(L\) 位置的時候在 \(L\) 處 \(+1\)，掃到 \(R+1\) 的時候撤銷 \(L\) 的 \(+1\) 操作。做到 \(i\) 位置的時候，設 \(a[i]=x\)，記錄 \(x\) 上一次出現的位置 \(las[x]\)，那 \(ans[x]\) 就要加上 \((las[x],i]\) 的和。正確性就是如果一個區間覆蓋了某個數，肯定會在左端點之后第一個出現這個數的位置統計上答案。這里的時間復雜度也是 \(O(n\log n)\)。

Code

這道題寫的是真的丑...

把壓行的都改掉了發現還是丑...

#include<bits/stdc++.h> using std::min; using std::max; using std::swap; using std::vector; typedef double db; typedef long long ll; #define pb(A) push_back(A) #define pii std::pair<int,int> #define all(A) A.begin(),A.end() #define mp(A,B) std::make_pair(A,B) const int N=1e6+5; const int M=1e4+5; // wtf????? // 把m開大就過了？？？？？？？ // 卡了老子一周的狗題？？？？ int ans[N],ans2[N],st[N][20],fs[N],len[N]; int s[N],tot,sa[N],rk[N],height[N],lg[N],f[N]; int n,m,num,x[N],y[N],c[N],belong[N][2],las[N];//belong=2 refers to questionstruct Ques{int l,r,idx;friend bool operator<(Ques a,Ques b){return a.r<b.r;} }ques[N];struct qu{int type,x;qu(){}qu(int a,int b){type=a,x=b;} };std::vector<qu> v[N];void add(int *f,int x,int y){while(x<=tot) f[x]+=y,x+=x&-x; }int query(int *f,int x){int now=0;while(x) now+=f[x],x-=x&-x;return now; }void getsa(int m=100001){for(int i=1;i<=tot;i++) c[x[i]=s[i]]++;for(int i=1;i<=m;i++) c[i]+=c[i-1];for(int i=tot;i;i--) sa[c[x[i]]--]=i;for(int k=1;num=0,k<=tot;k<<=1){for(int i=tot-k+1;i<=tot;i++) y[++num]=i;for(int i=1;i<=tot;i++) if(sa[i]>k) y[++num]=sa[i]-k;for(int i=0;i<=m;i++) c[i]=0;for(int i=1;i<=tot;i++) c[x[i]]++;for(int i=1;i<=m;i++) c[i]+=c[i-1];for(int i=tot;i;i--) sa[c[x[y[i]]]--]=y[i];swap(x,y),x[sa[1]]=num=1;for(int i=2;i<=tot;i++) x[sa[i]]=y[sa[i]]==y[sa[i-1]] and y[sa[i]+k]==y[sa[i-1]+k]?num:++num;if(num==tot) return;m=num;} }void getheight(int k=0){for(int i=1;i<=tot;i++) rk[sa[i]]=i;for(int i=1;i<=tot;i++){if(rk[i]==1) continue;if(k) k--;int j=sa[rk[i]-1];while(i+k<=tot and j+k<=tot and s[i+k]==s[j+k]) k++;height[rk[i]]=k;} }void getst(){for(int i=2;i<=tot;i++) lg[i]=lg[i-1]+((1<<lg[i-1]+1)==i);for(int i=1;i<=tot;i++) st[i][0]=height[i];for(int k=1;k<=lg[tot];k++)for(int i=1;i+(1<<k)-1<=tot;i++)st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]); }int getint(){int X=0,w=0;char ch=getchar();while(!isdigit(ch))w|=ch=='-',ch=getchar();while( isdigit(ch))X=X*10+ch-48,ch=getchar();if(w) return -X;return X; }int query(int x,int y){if(x==y) return tot-sa[x]+1;if(x>y) swap(x,y);x++;int k=lg[y-x+1];return min(st[x][k],st[y-(1<<k)+1][k]); }signed main(){n=getint(),m=getint();int cnt=10001;for(int i=1;i<=n;i++){if(i!=1) s[++tot]=++cnt;int lenn=getint();for(int j=1;j<=lenn;j++) s[++tot]=getint()+1,belong[tot][0]=1,belong[tot][1]=i;s[++tot]=++cnt;lenn=getint();for(int j=1;j<=lenn;j++) s[++tot]=getint()+1,belong[tot][0]=1,belong[tot][1]=i;}for(int i=1;i<=m;i++){s[++tot]=++cnt;len[i]=getint();fs[i]=tot+1;for(int j=1;j<=len[i];j++) s[++tot]=getint()+1,belong[tot][0]=2,belong[tot][1]=i;} getsa(),getheight(),getst();for(int i=1;i<=m;i++){//rk[fs[i]]int l=1,r=rk[fs[i]],now=0;while(l<=r){int mid=l+r>>1;if(query(mid,rk[fs[i]])>=len[i]) now=mid,r=mid-1;else l=mid+1;} ques[i].l=now;l=rk[fs[i]],r=tot,now=0;while(l<=r){int mid=l+r>>1;if(query(rk[fs[i]],mid)>=len[i]) now=mid,l=mid+1;else r=mid-1;} ques[i].r=now;ques[i].idx=i;} std::sort(ques+1,ques+1+m);int ptr=1;for(int i=1;i<=tot;i++){if(belong[sa[i]][0]==1 and las[belong[sa[i]][1]]) add(f,las[belong[sa[i]][1]],-1);if(belong[sa[i]][0]==1) add(f,i,1),las[belong[sa[i]][1]]=i;while(ptr<=m and ques[ptr].r==i){ans[ques[ptr].idx]=query(f,ques[ptr].r)-query(f,ques[ptr].l-1);ptr++;}} for(int i=1;i<=m;i++) printf("%d\n",ans[i]);memset(f,0,sizeof f);memset(las,0,sizeof las);for(int i=1;i<=m;i++) v[ques[i].l].pb(qu(1,ques[i].l)),v[ques[i].r].pb(qu(-1,ques[i].l));for(int i=1;i<=tot;i++){for(auto x:v[i])if(x.type==1)add(f,x.x,x.type);if(belong[sa[i]][0]==1) ans2[belong[sa[i]][1]]+=query(f,i)-query(f,las[belong[sa[i]][1]]);if(belong[sa[i]][0]==1) las[belong[sa[i]][1]]=i;for(auto x:v[i])if(x.type==-1)add(f,x.x,x.type);} for(int i=1;i<=n;i++) printf("%d%c",ans2[i],i==n?'\n':' ');return 0; }

轉載于:https://www.cnblogs.com/YoungNeal/p/10166505.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[SCOI2012] 喵星球上的点名的全部內容，希望文章能夠幫你解決所遇到的問題。

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