解题：SCOI 2012 喵星球上的点名

初见广义SAM

建立广义SAM，每次把询问走一遍，最终走到节点的子树里的猫老师都被这次点名点到

这样DFS parent树打时间戳记录入栈出栈时间，把问题转化成一个序列问题：给一个若干种颜色构成的序列和一些区间，询问：

1.每个区间里有多少种颜色— —直接莫队

2.每种颜色被多少区间包含— —同样是莫队，当某种颜色消失时从它上次出现开始的区间到现在的区间都包含了它

  1 #include<cmath>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<unordered_map>
  6 using namespace std;
  7 const int N=400005;
  8 struct a
  9 {
 10     int l,r;
 11     int idx,blo;
 12 }q[N];
 13 unordered_map<int,int> trs[N];
 14 int fth[N],len[N],bel[N];
 15 int p[N],noww[N],goal[N];
 16 int ins[N],ots[N],col[N];
 17 int qry[N],bkt[N],las[N],ans1[N],ans2[N];
 18 int n,m,lp,rp,ll,rd,lst,sqr,cnt,tot,dfn,ans;
 19 bool cmp(a x,a y)
 20 {
 21     return x.blo==y.blo?x.r<y.r:x.blo<y.blo;
 22 }
 23 void Link(int f,int t)
 24 {
 25     noww[++cnt]=p[f];
 26     goal[cnt]=t,p[f]=cnt;
 27 }
 28 void Insert(int ch)
 29 {
 30     int nde=lst,newn=++tot; 
 31     lst=newn,len[newn]=len[nde]+1;
 32     while(nde&&!trs[nde][ch])
 33         trs[nde][ch]=newn,nde=fth[nde];
 34     if(!nde)
 35         fth[newn]=1;
 36     else
 37     {
 38         int tran=trs[nde][ch];
 39         if(len[tran]==len[nde]+1)
 40             fth[newn]=tran;
 41         else
 42         {
 43             int rnde=++tot; 
 44             len[rnde]=len[nde]+1,trs[rnde]=trs[tran];
 45             fth[rnde]=fth[tran],fth[tran]=fth[newn]=rnde;
 46             while(nde&&trs[nde][ch]==tran)
 47                 trs[nde][ch]=rnde,nde=fth[nde];
 48         }
 49     }
 50 }
 51 void DFS(int nde)
 52 {
 53     ins[nde]=++dfn,col[dfn]=bel[nde];
 54     for(int i=p[nde];i;i=noww[i])
 55         DFS(goal[i]); ots[nde]=dfn;
 56 }
 57 void Add(int tsk,int typ)
 58 {
 59     if(tsk)
 60         if(++bkt[tsk]==1)
 61             ans++,las[tsk]=typ;
 62 }
 63 void Delete(int tsk,int typ)
 64 {
 65     if(tsk)
 66         if(!(--bkt[tsk]))
 67             ans--,ans2[tsk]+=typ-las[tsk];
 68 }
 69 int main()
 70 {
 71     scanf("%d%d",&n,&m),tot=1;
 72     for(int i=1;i<=n;i++)
 73     {
 74         scanf("%d",&ll),lst=1;
 75         for(int j=1;j<=ll;j++)
 76             scanf("%d",&rd),Insert(rd),bel[lst]=i;
 77         scanf("%d",&ll),lst=1;
 78         for(int j=1;j<=ll;j++)
 79             scanf("%d",&rd),Insert(rd),bel[lst]=i;
 80     }
 81     for(int i=2;i<=tot;i++) Link(fth[i],i); 
 82     DFS(1),sqr=sqrt(tot)+5;
 83     for(int i=1;i<=m;i++)
 84     {
 85         scanf("%d",&ll);
 86         for(int j=1;j<=ll;j++)
 87             scanf("%d",&qry[j]);
 88         int nde=1;
 89         for(int j=1;j<=ll;j++)
 90         {
 91             nde=trs[nde][qry[j]];
 92             if(!nde) break;
 93         }
 94         q[i].l=ins[nde],q[i].r=ots[nde];
 95         q[i].idx=i,q[i].blo=(q[i].l-1)/sqr+1;
 96     }
 97     sort(q+1,q+1+m,cmp),lp=1,rp=0;
 98     for(int i=1;i<=m;i++)
 99     {
100         while(lp<q[i].l) Delete(col[lp++],i);
101         while(lp>q[i].l) Add(col[--lp],i);
102         while(rp<q[i].r) Add(col[++rp],i);
103         while(rp>q[i].r) Delete(col[rp--],i);
104         ans1[q[i].idx]=ans;
105     }
106     for(int i=lp;i<=rp;i++) Delete(col[i],m+1);
107     for(int i=1;i<=m;i++) printf("%d
",ans1[i]);
108     for(int i=1;i<=n;i++) printf("%d ",ans2[i]);
109     return 0;
110 }

View Code