一道很套路的题目
先将所有串拼在一起，两个不同的串之间放一个没有出现在任何串中的字符做分隔，然后SA
那么对于所有点名串能够点到的名字串在SA中对应一段区间
把这些区间拿出来然后莫队统计每一个区间的答案
如何在莫队中统计一个名字在多少个点名串中出现？
当某一个名字第一次出现在区间内的时候，答案加上剩余询问个数；当这个名字第一次不出现在区间内的时候，答案减去剩余询问个数。
#include<bits/stdc++.h>
//This code is written by Itst
using namespace std;
inline int read(){
int a = 0;
char c = getchar();
bool f = 0;
while(!isdigit(c) && c != EOF){
if(c == '-')
f = 1;
c = getchar();
}
if(c == EOF)
exit(0);
while(isdigit(c)){
a = a * 10 + c - 48;
c = getchar();
}
return f ? -a : a;
}
const int MAXN = 5e5 + 9;
int s[MAXN] , rk[MAXN << 1] , pot[MAXN] , tp[MAXN << 1] , sa[MAXN] , h[MAXN];
int N , M , L , maxN = 10001 , T , logg2[MAXN] , ST[21][MAXN];
int lft , cnt , ans1[MAXN] , ans2[MAXN] , times[MAXN] , ind[MAXN];
struct query{
int l , r , ind;
bool operator <(const query a)const{
return l / T == a.l / T ? ((l / T) & 1 ? r > a.r : r < a.r) : l < a.l;
}
}now[MAXN];
void sort(int p){
memset(pot , 0 , sizeof(int) * (maxN + 1));
for(int i = 1 ; i <= L ; ++i)
++pot[rk[i]];
for(int i = 1 ; i <= maxN ; ++i)
pot[i] += pot[i - 1];
for(int i = 1 ; i <= L ; ++i)
sa[++pot[rk[tp[i]] - 1]] = tp[i];
swap(rk , tp);
for(int i = 1 ; i <= L ; ++i)
rk[sa[i]] = rk[sa[i - 1]] + (tp[sa[i]] != tp[sa[i - 1]] || tp[sa[i] + p] != tp[sa[i - 1] + p]);
maxN = rk[sa[L]];
}
void SA(){
for(int i = 1 ; i <= L ; ++i){
rk[i] = s[i];
tp[i] = i;
}
sort(0);
for(int i = 1 ; maxN < L ; i <<= 1){
int cnt = 0;
for(int j = 1 ; j <= i ; ++j)
tp[++cnt] = L - i + j;
for(int j = 1 ; j <= L ; ++j)
if(sa[j] > i)
tp[++cnt] = sa[j] - i;
sort(i);
}
for(int i = 1 ; i <= L ; ++i){
if(rk[i] == 1)
continue;
int t = rk[i];
h[t] = max(0 , h[rk[i - 1]] - 1);
while(s[h[t] + sa[t]] == s[h[t] + sa[t - 1]])
++h[t];
}
}
inline void init_SA(){
N = read();
M = read();
for(int i = 1 ; i <= N ; ++i){
int l = read();
for(int j = 1 ; j <= l ; ++j){
s[++L] = read() + 1;
ind[L] = i;
}
s[++L] = ++maxN;
l = read();
for(int j = 1 ; j <= l ; ++j){
s[++L] = read() + 1;
ind[L] = i;
}
s[++L] = maxN;
}
for(int i = 1 ; i <= M ; ++i){
int l = read();
for(int j = 1 ; j <= l ; ++j){
s[++L] = read() + 1;
ind[L] = j == 1 ? -l : 0;
}
s[++L] = ++maxN;
}
SA();
}
inline void init_ST(){
for(int i = 2 ; i <= L ; ++i){
logg2[i] = logg2[i >> 1] + 1;
ST[0][i] = h[i];
}
for(int i = 1 ; 1 << i <= L ; ++i)
for(int j = 2 ; j + (1 << i) <= L + 1 ; ++j)
ST[i][j] = min(ST[i - 1][j] , ST[i - 1][j + (1 << (i - 1))]);
}
inline int qST(int x , int y){
int t = logg2[y - x + 1];
return min(ST[t][x] , ST[t][y - (1 << t) + 1]);
}
inline void GetQue(int dir){
T = sqrt(L);
++M;
now[M].ind = M;
int L = 1 , R = rk[dir];
while(L < R){
int mid = (L + R) >> 1;
if(qST(mid + 1 , rk[dir]) >= -ind[dir])
R = mid;
else
L = mid + 1;
}
now[M].l = L;
L = rk[dir];
R = L;
while(L < R){
int mid = (L + R + 1) >> 1;
if(qST(rk[dir] + 1 , mid) >= -ind[dir])
L = mid;
else
R = mid - 1;
}
now[M].r = L;
}
inline void init_que(){
init_ST();
M = 0;
for(int i = 1 ; i <= L ; ++i)
if(ind[i] < 0)
GetQue(i);
sort(now + 1 , now + M + 1);
}
inline void add(int x){
if(x <= 0)
return;
if(!times[x]++){
ans2[x] += lft;
++cnt;
}
}
inline void del(int x){
if(x <= 0)
return;
if(!--times[x]){
ans2[x] -= lft;
--cnt;
}
}
inline void work(){
lft = M;
int L = 1 , R = 0;
for(int i = 1 ; i <= M ; ++i , --lft){
while(R < now[i].r)
add(ind[sa[++R]]);
while(L > now[i].l)
add(ind[sa[--L]]);
while(R > now[i].r)
del(ind[sa[R--]]);
while(L < now[i].l)
del(ind[sa[L++]]);
ans1[now[i].ind] = cnt;
}
}
inline void output(){
for(int i = 1 ; i <= M ; ++i)
cout << ans1[i] << '\n';
for(int i = 1 ; i <= N ; ++i)
cout << ans2[i] << ' ';
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
//freopen("out","w",stdout);
#endif
init_SA();
init_que();
work();
output();
return 0;
}