正題

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

---

題目大意

$n$個名字(每個名字兩個串)，$m$次點名，如果一次點名里是一個名字兩個串中的子串該人就要答到。

對于每次點名求多少個人答到，每個名字求答到多少次。

---

解題思路

先考慮第一問，我們將所有串串在一起(中間加大數)然后跑出$SA$和所有的$LCP$。

然后對于每個點名串起始位置$k$我們尋找一個區間$[l,r]$使得$$LCP(k,i)\ge len(i\in [l,r])$$

這個區間我們求出$height$后用$ST$表+二分可以求出

這樣如果任意一個名字串的在這個區間內就會被點到。因為有名有姓，我們把同一個名字的$SA$染成同一種顏色，這樣問題就變為了在$[l,r]$這個區間內有多少種顏色

而第二問也變為了有多少個區間包含該種顏色，我們直接用樹狀數組做就好了。

時間復雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #define lowbit(x) (x&-x) using namespace std; const int N=5e5+10; struct node{int l,r,id; }q[N]; int n,m,num,Q,s[N]; int col[N],len[N],head[N]; int sa[N],c[N],x[N],y[N]; int rk[N],height[N]; int st[N][20],lg[N]; int pre[N],last[N],qq[N]; int ans1[N],ans2[N]; struct Tree_Array{int t[N];void Change(int x,int val){if(!x) return;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;} }T1,T2; void Init(){scanf("%d%d",&num,&Q);m=1e4;for(int i=1;i<=num;i++){for(int j=0;j<2;j++){int x,c;scanf("%d",&x);while(x--){scanf("%d",&c);s[++n]=c;col[n]=i;}s[++n]=++m;}}for(int i=1;i<=Q;i++){int x;head[n+1]=i;scanf("%d",&len[i]);for(int j=1;j<=len[i];j++){scanf("%d",&x);s[++n]=x;col[n]=-i;}s[++n]=++m;} } void Qsort(){for(int i=1;i<=m;i++)c[i]=0;for(int i=1;i<=n;i++)c[x[i]]++;for(int i=1;i<=m;i++)c[i]+=c[i-1];for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i],y[i]=0;return; } void Get_SA(){for(int i=1;i<=n;i++)x[i]=s[i],y[i]=i;Qsort();for(int w=1;w<=n;w<<=1){int p=0;for(int i=n-w+1;i<=n;i++) y[++p]=i;for(int i=1;i<=n;i++)if(sa[i]>w) y[++p]=sa[i]-w;Qsort();swap(x,y);x[sa[1]]=p=1;for(int i=2;i<=n;i++)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+w]==y[sa[i-1]+w])?p:++p;if(p==n) break;m=p;}return; } void Get_Height(){int k=0;for(int i=1;i<=n;i++)rk[sa[i]]=i;for(int i=1;i<=n;i++){//if(rk[i]==1) continue;if(k) k--;int j=sa[rk[i]-1];while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;height[rk[i]]=k;}return; } void Get_ST(){lg[0]=-1;for(int i=1;i<=n;i++)st[i][0]=height[i],lg[i]=lg[i>>1]+1;for(int j=1;j<19;j++)for(int i=1;i+(1<<j-1)<=n;i++)st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);return; } int LCP(int l,int r){if(l==r) return 1e9+7;if(l>r) swap(l,r);l++;int z=lg[r-l+1];return min(st[l][z],st[r+1-(1<<z)][z]); } bool cmp(node x,node y) {return x.r<y.r;} void Get_Pre(){for(int i=1;i<=n;i++){if(col[sa[i]]>0){pre[i]=last[col[sa[i]]];last[col[sa[i]]]=i;}if(head[i]){int l=1,r=rk[i];while(l<=r){int mid=(l+r)>>1;if(LCP(mid,rk[i])>=len[head[i]]) r=mid-1;else l=mid+1;}q[head[i]].l=l;l=rk[i];r=n;while(l<=r){int mid=(l+r)>>1;if(LCP(rk[i],mid)>=len[head[i]]) l=mid+1;else r=mid-1;}q[head[i]].r=r;q[head[i]].id=head[i];qq[q[head[i]].l]++;}}sort(q+1,q+1+Q,cmp); } void Get_Ans(){int h=1,z=1;for(int i=1;i<=n;i++){T2.Change(i,qq[i]);if(col[sa[i]]>0){T1.Change(pre[i],-1);T1.Change(i,1);ans2[col[sa[i]]]+=T2.Ask(i)-T2.Ask(pre[i]);}while(h<=Q&&q[h].r<=i){ans1[q[h].id]+=T1.Ask(q[h].r)-T1.Ask(q[h].l-1);T2.Change(q[h].l,-1);h++;}}return; } int main() {Init();Get_SA();Get_Height();Get_ST();Get_Pre();Get_Ans();for(int i=1;i<=Q;i++)printf("%d\n",ans1[i]);for(int i=1;i<=num;i++)printf("%d ",ans2[i]); } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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