我学AC自动机的时候就看到了这题，想用AC自动机结果被学长码风劝退……

学后缀数组时又看到了这题……那就写写后缀数组做法吧 结果码风貌似比当年劝退我的学长还毒瘤啊

对所有的模式串+询问串，不同串之间用不同分隔符隔开，然后建后缀数组

第一问，显然所有包含询问串的后缀们的排名是一段连续的区间。于是就可以用ST表处理每两个后缀间的最长公共前缀，然后二分左端点和右端点。于是就变成了一个模板得不能再模板的，数一个区间中出现了多少个不同的数的莫队

第二问，考虑差分：每次询问时，如果一个串第一次出现，加上这个询问之后的询问个数，如果这个串将被删除，减掉这个询问之后的询问个数

代码：

#include 
    
     #define M 420005#define rep(i,x,y) for(i=(x);i<=(y);++i)using namespace std;int id[M],bg[M],n,m,sz=11000,ll[M];namespace SA{    int tp[M],tax[M],rnk[M],sa[M],height[M],len=0;    int f[M][20],name[M];    void init(){        int i,j,x,y;        scanf("%d%d",&n,&m);        rep(i,1,n){                     rep(j,0,1){                scanf("%d",&x);                while(x--){                    scanf("%d",&y);y++;                    name[++len]=y,id[len]=i;                    }                name[++len]=++sz;                if(!j) id[len]=i;            }        }        rep(i,1,m){            scanf("%d",&x);            ll[i]=x,bg[i]=len+1;            while(x--){                scanf("%d",&y);y++;                name[++len]=y;            }            name[++len]=++sz;               }sz++;    }    void Qsort(){        int i;        rep(i,0,sz) tax[i]=0;        rep(i,1,len) tax[rnk[i]]++;        rep(i,1,sz) tax[i]+=tax[i-1];        for(i=len;i>=1;--i) sa[tax[rnk[tp[i]]]--]=tp[i];    }    inline bool cmp(int x,int y,int w){ return tp[x]==tp[y]&&tp[x+w]==tp[y+w]; }        void SufSort(){        int i,x;        rep(i,1,len) rnk[i]=name[i],tp[i]=i;        Qsort();        for(x=1;x<=len;x<<=1){            int num=0;            rep(i,len-x+1,len) tp[++num]=i;            rep(i,1,len) if(sa[i]>x) tp[++num]=sa[i]-x;            Qsort();memcpy(tp,rnk,sizeof(tp));            rnk[sa[1]]=1;            rep(i,2,len) rnk[sa[i]]=rnk[sa[i-1]]+(!cmp(sa[i],sa[i-1],x));              if(rnk[sa[len]]==len) return;            sz=rnk[sa[len]];        }    }    void GetHeight(){        int i,j,k=0;        memset(f,0x3f,sizeof(f));        for(i=1;i<=len;++i){            if(k) k--;            int j=sa[rnk[i]-1];            while(name[i+k]==name[j+k]) k++;            height[rnk[i]]=f[rnk[i]][0]=k;        }        for(i=1;(1<
     
      <=len;++i)            for(j=1;j<=len;++j)                f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);    }    int lcp(int x,int y){        int l=x+1,r=y,w=log2(r-l+1);        return min(f[l][w],f[r-(1<
      
       a.r:r
       
        
         >1;            if(SA::lcp(mid,x)>=y) ans=mid,r=mid-1;            else l=mid+1;        }         return ans;    }    int getr(int x,int y){        int l=x+1,r=SA::len,ans=x;        while(l<=r){            int mid=l+r>>1;            if(SA::lcp(x,mid)>=y) ans=mid,l=mid+1;            else r=mid-1;        }         return ans;    }       void init(){        int i,n=SA::len,block=sqrt(n);        rep(i,1,n) bl[i]=(i-1)/block+1;        rep(i,1,m){            int L=getl(SA::rnk[bg[i]],ll[i]),R=getr(SA::rnk[bg[i]],ll[i]);            if(L<=R)q[++cnt]=(ques){L,R,i};//          printf("%d : %d %d\n",i,L,R);        }    }    inline void add(int x,int y){        if(++t[id[SA::sa[x]]]==1 && id[SA::sa[x]])            tot++,ans2[id[SA::sa[x]]]+=m-y+1;    }    inline void del(int x,int y){        if(--t[id[SA::sa[x]]]==0 && id[SA::sa[x]])            tot--,ans2[id[SA::sa[x]]]-=m-y+1;    }    void solve(){        sort(q+1,q+cnt+1);        memset(t,0,sizeof(t));        int i,L=1,R=0;        rep(i,1,cnt){            while(R
         
          q[i].l) add(--L,i); while(R>q[i].r) del(R--,i); while(L