[SCOI2012]喵星球上的点名

学习了后缀数组啊。。。好久没写blog了啊。。。

以及犯了好多智障错误

传送门

首先，把所有的姓名串中间插上不同的字符建出后缀数组，求出每个排名$i$对应的串$sa[i]$。

如果一个串是某些后缀的前缀，那么这些后缀的排名一定是连续的，也就是在sa数组上是个连续的区间。

那么我们可以对每个询问二分出这个区间。看看这个区间中有多少颜色，莫队解决。

求每个颜色出现次数？可以”在时间轴上差分”。（以下第i个询问表示莫队将询问排序前的顺序）

当莫队在处理第j个询问中发现一个新出现的颜色i时，$num[i]+=cnt-j+1$，cnt是总询问数。

当莫队在处理第j个询问中发现少了一个颜色i时，$num[i]-=cnt-j+1$。

这样做的意义：在询问的时间轴上，如果在一个点i发现一个新颜色，假设这个颜色不会再消失，那么它出现了cnt-i+1也就是i到终点的距离次。如果之后这个颜色在第j个询问时消失了，那么就减去多算的cnt-j+1次。

犯的一些智障错误：

for (int i=1; i<=n; i++) bl[i]=(i/blo)+1;	//就这有91分，本机还测不出来

for (int i=1; i<=maxn; i++) o[i]=0;		// o是基数排序的桶，o[0]安详的存在着

还有ch[n+1]默认是0，然而应该是-1。

以及很多没脸放出来的错误。。。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define SIZE 210012
#define re register
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int init(){
    re char c=gc();re int a=0,w=1;
    while((c<'0'||c>'9')&&c-'-')c=gc();
    if(c=='-')w=-w,c=gc();
    while(c>='0'&&c<='9')a=(a<<3)+(a<<1)+(c^48),c=gc();
    return a*w;
}
inline void pc(re char c,re int p=0){
    static char buf[100000],*p1=buf;
    if(p){fwrite(buf,1,p1-buf,stdout);return ;}
    *p1++=c;
    if(p1==buf+100000)fwrite(buf,1,100000,stdout),p1=buf;
}
void print(re int x){
    if(x>9)print(x/10);
    pc(x%10+'0');
}
inline char getc(){
    char c=gc();
    while(!isupper(c)) c=gc();
    return c;
}
struct node{
    int l,r,h;
}q[SIZE];
struct suffix{
    int a,b,h;
}a[SIZE],tmp[SIZE];
int bl[SIZE],sa[SIZE],o[SIZE],n,m,t,ch[SIZE],blo,num[50001];
int c[SIZE],maxn,sum,ans[100010],cnt,b[50001],rk[SIZE];
inline bool cmp(node c,node d){
    if (bl[c.l]!=bl[d.r]) return c.l<d.l;
    if (bl[c.l]&1) return c.r<d.r;
    return c.r>d.r;
}
inline void jsort(){
    for (int i=0; i<=maxn; i++) o[i]=0;
    for (int i=1; i<=n; i++) o[a[i].b]++;
    for (int i=1; i<=maxn; i++) o[i]+=o[i-1];
    for (int i=1; i<=n; i++) tmp[o[a[i].b]--]=a[i];
    for (int i=1; i<=n; i++) a[i]=tmp[i];
    for (int i=0; i<=maxn; i++) o[i]=0;
    for (int i=1; i<=n; i++) o[a[i].a]++;
    for (int i=1; i<=maxn; i++) o[i]+=o[i-1];
    for (int i=n; i>=1; i--) tmp[o[a[i].a]--]=a[i];
    for (int i=1; i<=n; i++) a[i]=tmp[i];
}
inline void add(int x,int y){if (!o[c[sa[x]]]) sum++,num[c[sa[x]]]+=cnt-y+1;o[c[sa[x]]]++;}
inline void del(int x,int y){o[c[sa[x]]]--;if (!o[c[sa[x]]]) sum--,num[c[sa[x]]]-=cnt-y+1;}
int main(){
    // freopen("0a.in","r",stdin);
    // freopen("0a.out","w",stdout);
    int x,y;
    t=init(),m=init();
    for (int i=1; i<=t; i++){
        x=init(); ch[++n]=1e4+i*2-1;
        for (int j=1; j<=x; j++) ch[++n]=init();
        x=init(); ch[++n]=1e4+i*2;
        for (int j=1; j<=x; j++) ch[++n]=init();
        b[i]=n;
    }//ch[++n]=1e4+t*2+1;
    ch[n+1]=-1;
    for (int i=1; i<=t; i++)
        for (int j=b[i-1]+1; j<=b[i]; j++)
            c[j]=i,a[j].a=ch[j],a[j].h=j;
    maxn=1e4+2*t;
    jsort(); a[0].a=-1;
    for (int i=1; i<=n; i++){
        rk[a[i].h]=rk[a[i-1].h];
        if (a[i].a!=a[i-1].a||a[i].b!=a[i-1].b) rk[a[i].h]++;
    }
    maxn=rk[a[n].h];
    for (int i=1; i<=n; i++) a[i].a=rk[i],a[i].h=i,rk[i]=a[i].b=0;
    for (int w=1; w<=n; w<<=1){
        for (int i=1; i+w<=n; i++) a[i].b=a[i+w].a;
        jsort();
        for (int i=1; i<=n; i++){
            rk[a[i].h]=rk[a[i-1].h];
            if (a[i].a!=a[i-1].a||a[i].b!=a[i-1].b) rk[a[i].h]++;
        }
        maxn=rk[a[n].h];
        for (int i=1; i<=n; i++) a[i].a=rk[i],a[i].h=i,rk[i]=a[i].b=0;
        if (maxn==n) break;
    }
    for (int i=1; i<=n; i++) sa[a[i].a]=i,rk[i]=a[i].a,a[i].a=0;
    // puts("sa:"); for (int i=1; i<=n; i++) printf("%d ",sa[i]); puts("");
    // puts("ch:"); for (int i=1; i<=n; i++) printf("%d ",ch[i]); puts("");
    // puts("rk:"); for (int i=1; i<=n; i++) printf("%d ",rk[i]); puts("");
    int l,r,mid,ls,rs;
    for (int i=1; i<=m; i++){
        y=init(); ls=1,rs=n;
        for (int j=1; j<=y; j++){
            x=init();
            l=ls,r=rs;
            while (l<=r){
                mid=(l+r)>>1;
                if (ch[sa[mid]+j-1]<x) l=mid+1;
                else r=mid-1;
            }
            ls=l; r=rs;
            while (l<=r){
                mid=(l+r)>>1;
                if (ch[sa[mid]+j-1]>x) r=mid-1;
                else l=mid+1;
            }
            rs=r;
        }
        if (ls<=rs) q[++cnt].l=ls,q[cnt].r=rs,q[cnt].h=i;
        // printf("%d %d\n",ls,rs);
    }
    blo=sqrt(n); memset(o,0,sizeof(o));
    for (int i=1; i<=n; i++) bl[i]=(i-1)/blo+1;
    sort(q+1,q+cnt+1,cmp); l=1,r=0;
    for (int i=1; i<=m; i++){
        while (l<q[i].l) del(l,i),l++;
        while (l>q[i].l) l--,add(l,i);
        while (r<q[i].r) r++,add(r,i);
        while (r>q[i].r) del(r,i),r--;
        ans[q[i].h]=sum;
    }
    for (int i=1; i<=m; i++) print(ans[i]),pc('\n');
    for (int i=1; i<=t; i++){
        print(num[i]),pc(' ');
        // if (i==t) puts(""); else printf(" ");
    }
    pc(' ',1);
    return 0;
}