喵星球上的点名（后缀自动机+dfs序+莫队）

喵星球上的点名

一道据传言有多种解法的题（不过大多是因为数据太弱过的）。先用AC自动机搞了一上午，无果；看了题解，后缀自动机+莫队？正好是我最喜欢的算法之一+正在学习的算法，就这个了！然后由于广义自动机的 $last$last标记有个地方忘了初始化。。。然后在大物课上调了三节课，洛谷一页都是我，hhh

题意：

有 $N$N个同学，名字包含姓和名；然后老师要点 $M$M次名，某次点名若是某个同学的姓或者名的子串，则这位同学要答到。求：

1. 每次点名会有多少同学答到
2. $M$M次点名后每位同学分别会答到多少次

思路：后缀自动机+ $dfs$dfs序+莫队

1. 由于涉及多字符串，当然是用广义后缀自动机搞呀（也可以在字符串之间插入不涉及的数字，并且用 $map$map存转移边）；同时记得在建后缀自动机时给每个节点表明是属于哪个人的，毕竟后面要分别统计每个人的答到次数；还有虚点的问题，这里的处理其实比较随意，你既可以当做是当前同学的，也可以当做是之前同学的，甚至可以当做一个不会出现的同学的（比如默认为 $0$0），这点是非常有趣的。
2. 询问中需要知道每次点名会有多少人答到，显然可以直接在后缀自动机上跑这个点名的字符串，找到那个节点后，属于这个节点的整棵 $parent$parent $tree$tree子树的同学都是要答到的。
3. 这时我们容易想到处理出 $parent$parent $tree$tree的 $dfs$dfs序，这样属于某个节点的整棵子树在 $dfs$dfs序上都是连续的一段，当我们想要知道里面有多少个不同的同学的姓名时，也就是询问区间不同种类数字个数！就可以直接莫队处理啦（也可以像HH的项链那样用树状数组处理啦）。
4. 至此，第一个问题就轻松解决了，那么第二问呢？第二个问题可以等效为某个节点被多少询问区间所包含！注意到在使用莫队的过程中，每个节点总是在不断地进入，出去。那么，在进入之后，出来之前发生了什么呢？显然这个节点（同学）在不断地贡献答案，也就是他在这段时间内一直被包含！因此，在端点移动过程中，每次有新的未出现的节点进入区间，就记录这个节点的进入时间，当他出去的时候，就统计答案。这样，每个同学被点到的次数就被分成了多段连续的时间，加在一起就是总的次数！
5. 补充：第二问同样可以用树状数组处理：将区间放在树状数组上，每当到达区间左端点时， $bit\left[L\right]+1$bit[L]+1，到达区间右端点时， $bit\left[L\right]-1$bit[L]−1；没当到达某个人的姓名时（两部分），对于每个人的两个字符串，靠左边的统计答案为 $ans=qsum\left(pos1\right)$ans=qsum(pos1)，靠右边的统计为 $ans+=qsum\left(pos2\right)-qsum\left(pos1\right)$ans+=qsum(pos2)−qsum(pos1)；这样的处理就可以知道这个人总共被覆盖多少次啦！
6. 妙哉！！！

代码

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 4e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int N, M;
map<int,int> ch[maxn];
int len[maxn], fa[maxn], belong[maxn], last=1, sz=1;
int head[maxn], to[maxn], nxt[maxn], tot;
int siz[maxn], id[maxn], rk[maxn], dfn, vis[maxn], pre[maxn];
int cur, cntq, ans1[maxn], ans2[maxn], block;

inline void add_edge(int u, int v) {
    ++tot; to[tot]=v; nxt[tot]=head[u]; head[u]=tot;
}

struct Q{
    int l, r, id;
    friend bool operator < (const Q &a, const Q &b) {
        if((a.l-1)/block!=(b.l-1)/block) return a.l<b.l;
        if((a.l-1)/block%2) return a.r>b.r;
        return a.r<b.r;
    }
}q[maxn];

void add(int c, int ID) {
    int p=last, np=last=++sz;
    len[np]=len[p]+1, belong[np]=ID;
    for(; p&&!ch[p].count(c); p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++sz; len[nq]=len[p]+1;
            fa[nq]=fa[q]; fa[np]=fa[q]=nq;
            ch[nq]=ch[q];
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

void dfs(int u) {
    rk[id[u]=++dfn]=u; siz[u]=1;
    for(int i=head[u]; i; i=nxt[i]) {
        dfs(to[i]); siz[u]+=siz[to[i]];
    }
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    N=read(), M=read();
    for(int i=1, L; i<=N; ++i) {
        last=1; L=read(); for(int j=1; j<=L; ++j) add(read(),i);
        last=1; L=read(); for(int j=1; j<=L; ++j) add(read(),i);
    }
    for(int i=2; i<=sz; ++i) add_edge(fa[i],i); dfs(1);
    for(int i=1; i<=M; ++i) {
        int L=read(), now=1;
        for(int j=1; j<=L; ++j) now=ch[now][read()];
        if(now) q[++cntq]=(Q){id[now],id[now]+siz[now]-1,i};
    }
    block=ceil(sqrt(dfn));
    sort(q+1,q+1+cntq);
    int l=1, r=0; //不用把第一个区间单独处理，莫队其实会自动处理好的，真妙！
    for(int i=1; i<=cntq; ++i) {
        while(l<q[i].l) {
            int p=belong[rk[l]];
            vis[p]--;
            if(!vis[p]&&p) cur--, ans2[p]+=i-pre[p];
            l++;
        }
        while(l>q[i].l) {
            --l;
            int p=belong[rk[l]];
            if(!vis[p]&&p) cur++, pre[p]=i;
            vis[p]++;
        }
        while(r<q[i].r) {
            ++r;
            int p=belong[rk[r]];
            if(!vis[p]&&p) cur++, pre[p]=i;
            vis[p]++;
        }
        while(r>q[i].r) {
            int p=belong[rk[r]];
            vis[p]--;
            if(!vis[p]&&p) cur--, ans2[p]+=i-pre[p];
            r--;
        }
        ans1[q[i].id]=cur;
    }
    for(int i=1; i<=N; ++i) if(vis[i]) ans2[i]+=cntq+1-pre[i]; //别忘了有些同学还没有离开区间呀
    for(int i=1; i<=M; ++i) printf("%d\n", ans1[i]);
    for(int i=1; i<=N; ++i) printf("%d%c", ans2[i], " \n"[i==N]);
}