首页 > 代码库 > BZOJ 2754 【SCOI2012】 喵星球上的点名
BZOJ 2754 【SCOI2012】 喵星球上的点名
题目链接:喵星球上的点名
首先可以发现姓和名两个串就是逗你玩的。在两个串中间插入一个\(10001\),当成一个串做就可以了。
于是我们的问题转化为了:
有\(n\)个串\(A_1,A_2,\dots,A_n\)和\(m\)个串\(B_1,B_2,\dots,B_m\),要对于每个\(B_i\)求出它被多少个\(A\)串包含,并要对每个\(A_i\)求出它包含了多少个\(B\)串。
我们先把所有串丢到一个\(AC\)自动机里面,然后构出\(fail\)树。我们知道,如果\(S\)串包含了\(A\)串,那么在\(fail\)树上\(A\)串的结尾节点的子树里就会有\(S\)串的节点。所以构出\(dfs\)序之后,要求每个\(B_i\)求出它被多少个\(A\)串包含,就相当于询问区间不同的颜色数。做法同HH的项链。
第二问就是相当于每次给区间内所有元素加\(1\),但是相同的元素只加一次。记位置\(i\)的元素上一次出现的位置为\(pre_i\),那么每次操作\((l,r)\)就相当于给其中满足\(pre_i<l \le i \le r\)的\(i\)位置的元素加\(1\)。我们把所有二元组\(pre_i,i\)和所有询问\(l,r\)都按前一个数为第一关键字,后一个数为第二关键字排序,然后一起从后往前扫。对于每个二元组\(pre_i,i\),找出所有的满足\(pre_i<l\)的\(l,r\),给\(l,r\)区间加\(1\),然后位置\(i\)上的值就是\(i\)位置的元素被统计的次数。用一个树状数组维护即可。
下面贴代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<map> #include<vector> #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) #define maxn 300010 #define pb push_back using namespace std; typedef long long llg; struct data{ int l,r,b; bool operator < (const data &h)const{return l<h.l;} }A[maxn],B[maxn]; int n,m,b[maxn],lb,tt,val[maxn],pr[maxn]; int d[maxn],fr[maxn],fl[maxn],a[maxn],la,c[maxn]; int hd[maxn],nt[maxn],le[maxn],ri[maxn],ans[maxn]; map<short int,int>s[maxn]; map<short int,int>::iterator it; vector<int> q[maxn]; int getint(){ int w=0;bool q=0; char c=getchar(); while((c>‘9‘||c<‘0‘)&&c!=‘-‘) c=getchar(); if(c==‘-‘) c=getchar(),q=1; while(c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } bool cmpr(data x,data y){return x.r<y.r;} int insert(int x){ int u=0; for(int i=1;i<=lb;i++){ if(!s[u][b[i]]) s[u][b[i]]=++tt,val[tt]=b[i]; u=s[u][b[i]]; if(x) q[u].pb(x); } return u; } void getfail(){ int ld=0,rd=0; d[rd++]=0; while(ld!=rd){ int u=d[ld++],j,v; if(u) nt[u]=hd[fl[u]],hd[fl[u]]=u; for(it=s[u].begin();it!=s[u].end();it++){ j=fl[u]; d[rd++]=v=(*it).second; while(!s[j][val[v]] && j) j=fl[j]; if(u!=j) fl[v]=s[j][val[v]]; } } } void dfs(int u){ le[u]=la+1; for(int i=q[u].size()-1;i>=0;i--){ a[++la]=q[u][i]; A[la].r=la; A[la].l=pr[a[la]]; pr[a[la]]=la; } for(int i=hd[u];i;i=nt[i]) dfs(i); ri[u]=la; } void add(int x,int y){while(x<=la) c[x]+=y,x+=x&(-x);} int sum(int x){ int t=0; while(x) t+=c[x],x-=x&(-x); return t; } int main(){ File("a"); n=getint(),m=getint(); for(int i=1,x;i<=n;i++){ lb=0; x=getint(); while(x--) b[++lb]=getint(); b[++lb]=10001; x=getint(); while(x--) b[++lb]=getint(); insert(i); } for(int i=1,x;i<=m;i++){ lb=0; x=getint(); while(x--) b[++lb]=getint(); fr[i]=insert(0); } getfail(); dfs(0); for(int i=1;i<=m;i++) B[i].l=le[fr[i]],B[i].r=ri[fr[i]],B[i].b=i; sort(B+1,B+m+1,cmpr); int bl=1; while(!B[bl].r) bl++; for(int i=1;i<=la;i++) pr[a[i]]=0; for(int i=1,now=0;i<=la;i++){ if(pr[a[i]]) add(pr[a[i]],-1); now+=(!pr[a[i]]); add(i,1); pr[a[i]]=i; while(B[bl].r==i) ans[B[bl].b]=now-sum(B[bl].l-1),bl++; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]),ans[i]=0; for(int i=1;i<=la;i++) c[i]=0; sort(A+1,A+la+1); sort(B+1,B+m+1); for(int i=la,j=m;i;){ if(A[i].l<B[j].l) add(B[j].l,1),add(B[j].r+1,-1),j--; else ans[a[A[i].r]]+=sum(A[i].r),i--; } for(int i=1;i<=n;i++){ printf("%d",ans[i]); if(i<n) putchar(‘ ‘); } return 0; }
BZOJ 2754 【SCOI2012】 喵星球上的点名