BZOJ 2754 【SCOI2012】喵星球上的点名-白红宇

BZOJ 2754 【SCOI2012】喵星球上的点名

阅读量：4598 次

发布时间：2019-06-09

本文共 2390 字，大约阅读时间需要 7 分钟。

题目链接：

　　首先可以发现姓和名两个串就是逗你玩的。在两个串中间插入一个\(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\)串包含，就相当于询问区间不同的颜色数。做法同。

　　第二问就是相当于每次给区间内所有元素加\(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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)#define maxn 300010#define pb push_backusing namespace std;typedef long long llg;struct data{ int l,r,b; bool operator < (const data &h)const{return l
            
             s[maxn];map
             
              ::iterator it;vector
              
                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
               
                =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

转载于:https://www.cnblogs.com/lcf-2000/p/7027558.html

你可能感兴趣的文章