学步园

题目大意：在喵星球上有一些喵~，每个喵都有一个姓和一个名字。点名的时候如果一个喵中姓或者名中有这个串的话他就会喵。问每次点名有几个喵喵了，和每个喵喵了几次。

思路：好萌的题喵~

AC自动机构造fail树是可以做的，但是和SA乱搞的时间差不多，我就是SA乱搞的w

把所有的串（姓名，询问）用$连接成一个串，然后做后缀数组，height数组。过程中记录一下每一个后缀数属于哪个喵，还有询问在串中的起始位置。在处理询问的时候，可以同过sa，rank数组快速的访问height数组，对于每一个询问向两边拓展，知道height数组小于询问串的长度。记录答案的时候要弄一个时间戳来盼重（真不知道为什么网上那么多用set的，真把常数不当干粮啊。。三倍的时间啊。。

当然这就是个暴力，时间复杂度是非常大的，想卡住也看好卡。想到了卡不住的方法，但是实现起来就比较困难了。将height数组用ST处理一下，然后对于每一个询问就可以向两边二分了，而不是暴力扫。得到了一整个区间之后，用主席树，直接看这个区间中有多少不同的喵。关于第二问就不太好处理了，我还没太想好QAQ

CODE：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 300010
using namespace std;
 
int cats,asks,len;
int s[MAX],from[MAX];
int ask[MAX],length[MAX];
 
int val[MAX],sa[MAX];
int rank[MAX],height[MAX];
 
int ans[MAX],v[MAX],T;
 
inline bool Same(int x,int y,int l)
{
    return val[x] == val[y] &&
    ((x + l >= len && y + l >= len) || (x + l < len && y + l < len && val[x + l] == val[y + l]));
}
 
void GetSuffixArray()
{
    static int _val[MAX],q[MAX],cnt[MAX],lim = 10010;
    for(int i = 0; i < len; ++i) ++cnt[val[i] = s[i]];
    for(int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
    for(int i = len - 1; ~i; --i)   sa[--cnt[val[i]]] = i;
    for(int d = 1;; ++d) {
        int top = 0,l = 1 << (d - 1);
        for(int i = 0; i < len; ++i) if(sa[i] + l >= len) q[top++] = sa[i];
        for(int i = 0; i < len; ++i) if(sa[i] >= l)   q[top++] = sa[i] - l;
         
        for(int i = 0; i < lim; ++i) cnt[i] = 0;
        for(int i = 0; i < len; ++i) ++cnt[val[q[i]]];
        for(int i = 1; i < lim; ++i) cnt[i] += cnt[i - 1];
        for(int i = len - 1; ~i; --i)   sa[--cnt[val[q[i]]]] = q[i];
        lim = 0;
        for(int i = 0,j; i < len; ++lim) {
            for(j = i; j < len - 1 && Same(sa[j],sa[j + 1],l); ++j);
            for(; i <= j; ++i)   _val[sa[i]] = lim;
        }
        for(int i = 0; i < len; ++i) val[i] = _val[i];
        if(lim == len)  break;
    }
    return ;
}
 
void GetHeight()
{
    for(int i = 0; i < len; ++i) rank[sa[i]] = i;
    for(int i = 0,k = 0; i < len; ++i) {
        if(k)   --k;
        int j = sa[rank[i] - 1];
        while(s[i + k] == s[j + k]) ++k;
        height[rank[i]] = k;
    }
}
 
int main()
{
    cin >> cats >> asks;
    len = -1;
    for(int num,i = 1; i <= cats; ++i) {
        scanf("%d",&num);
        for(int j = 1; j <= num; ++j)
            scanf("%d",&s[++len]),from[len] = i;
        s[++len] = 10001;
        scanf("%d",&num);
        for(int j = 1; j <= num; ++j)
            scanf("%d",&s[++len]),from[len] = i;
        s[++len] = 10001;
    }
    for(int i = 1; i <= asks; ++i) {
        scanf("%d",&length[i]);
        ask[i] = len + 1;
        for(int j = 1; j <= length[i]; ++j)
            scanf("%d",&s[++len]);
        s[++len] = 10001;
    }
    ++len;
    GetSuffixArray();
    GetHeight();
    for(int i = 1; i <= asks; ++i) {
        int p = rank[ask[i]],temp = 0;
        ++T;
        while(height[p] >= length[i]) {
            if(from[sa[p - 1]])
                if(v[from[sa[p - 1]]] != T) {
                    v[from[sa[p - 1]]] = T;
                    ++ans[from[sa[p - 1]]];
                    ++temp;
                }
            --p;
            if(!p)  break;
        }
        p = rank[ask[i]];
        while(height[p + 1] >= length[i]) {
            if(from[sa[p + 1]])
                if(v[from[sa[p + 1]]] != T) {
                    v[from[sa[p + 1]]] = T;
                    ++ans[from[sa[p + 1]]];
                    ++temp;
                }
            ++p;
            if(p == len)    break;
        }
        printf("%d\n",temp);
    }
    for(int i = 1; i <= cats; ++i)
        printf("%d%c",ans[i]," \n"[i == cats]);
    return 0;
}