记录编号	216464	评测结果	AAAAAAAAAA
题目名称	[SCOI 2012] 喵星球上的点名	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	1.840 s
提交时间	2015-12-29 09:55:41	内存使用	17.64 MiB

#define MAXN 300010UL

#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

struct Node{
	Node *fail;
	std::map<int,Node*> ch;
	int id;
	std::vector<int> M;
	Node(int _id){
		id=_id;
		fail=NULL;
		return;
	}
}*root;

struct Query{int l,r,num;};
struct Edge{int v,nx;};

Edge edge[MAXN];
Query Ask[MAXN];
int n,m,ec,cnt,dfs_clock,block_cnt,rev_dfn[MAXN],dfn[MAXN],Name[MAXN],headlist[MAXN],ots[MAXN],tail[MAXN],block[MAXN],Ans[MAXN],Rec[MAXN];
int color_tot,color[MAXN],last_app[MAXN];
std::queue<Node*> que;
std::vector<int> seq[MAXN];

inline int in(){
	int x=0,c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	return x;
}

inline void Add_Edge(int u,int v){
	edge[++ec].v=v;
	edge[ec].nx=headlist[u];
	headlist[u]=ec;
	return;
}

inline bool comp(Query a,Query b){
	return block[a.l]==block[b.l]?a.r<b.r:block[a.l]<block[b.l];
}

inline void Add_Trie(int id){
	Node *now=root;
	for(int i=1,t;i<=Name[0];i++){
		t=Name[i];
		if(!now->ch.count(t)) now->M.push_back(t),now->ch[t]=new Node(++cnt);
		now=now->ch[t];
		if(id<=n) seq[now->id].push_back(id);
	}
	if(id>n) tail[id-n]=now->id;
	return;
}

inline void ReadIn(){
	n=in();m=in();
	root=new Node(++cnt);
	for(int i=1,len;i<=n;i++){
		len=in();
		Name[0]=len;
		for(int j=1;j<=len;j++) Name[j]=in()+1;
		Name[len+1]=0;
		Name[0]+=in()+1;
		for(int j=len+2;j<=Name[0];j++) Name[j]=in()+1;
		Add_Trie(i);
	}
	for(int i=1;i<=m;i++){
		Name[0]=in();
		for(int j=1;j<=Name[0];j++) Name[j]=in()+1;
		Add_Trie(i+n);
	}
	return;
}

inline void Build_AC_Automatic(){
	que.push(root);
	while(!que.empty()){
		Node *tmp=que.front();que.pop();
		for(int i=0,t,s=tmp->M.size();i<s;i++){
			Node *p=tmp->fail;
			t=tmp->M[i];
			while(p!=NULL&&(!p->ch.count(t))) p=p->fail;
			if(p==NULL) tmp->ch[t]->fail=root,Add_Edge(1,tmp->ch[t]->id);
			else tmp->ch[t]->fail=p->ch[t],Add_Edge(p->ch[t]->id,tmp->ch[t]->id);
			que.push(tmp->ch[t]);
		}
	}
	return;
}

void dfs(int p){
	dfn[p]=++dfs_clock;
	rev_dfn[dfs_clock]=p;
	for(int i=headlist[p];i;i=edge[i].nx)
		dfs(edge[i].v);
	ots[p]=dfs_clock;
	return;
}

inline void Build_Fail_Tree(){
	dfs(1);
	block_cnt=((int)sqrt(cnt))+1L;
	for(int i=1;i<=cnt;i++) block[i]=i/block_cnt;
	for(int i=1;i<=m;i++){
		Ask[i].l=dfn[tail[i]],Ask[i].r=ots[tail[i]],Ask[i].num=i;
	}
	std::sort(Ask+1,Ask+m+1,comp);
	return;
}

inline void Add(int p,int pid){
	p=rev_dfn[p];
	for(int i=0,c,s=seq[p].size();i<s;i++){
		c=seq[p][i];
		if(color[c]==0) ++color_tot,last_app[c]=pid;
		color[c]++;
	}
	return;
}

inline void Del(int p,int pid){
	p=rev_dfn[p];
	for(int i=0,c,s=seq[p].size();i<s;i++){
		c=seq[p][i];
		if(color[c]==1){
			--color_tot;
			Rec[c]+=pid-last_app[c];
		}
		color[c]--;
	}
	return;
}

inline void Unzip(){
	for(int i=1;i<=300000;i++){
		if(!color[i]) continue;
		Rec[i]+=m-last_app[i]+1;
	}
	return;
}

inline void MoDui(){
	int L=0,R=0;
	for(int i=1;i<=m;i++){
		while(R<Ask[i].r) Add(++R,i);
		while(L>Ask[i].l) Add(--L,i);
		while(R>Ask[i].r) Del(R--,i);
		while(L<Ask[i].l) Del(L++,i);
		Ans[Ask[i].num]=color_tot;
	}
	Unzip();
	return;
}

inline void PrintAns(){
	for(int i=1;i<=m;i++) printf("%d\n",Ans[i]);
	printf("%d",Rec[1]);
	for(int i=2;i<=n;i++) printf(" %d",Rec[i]);
	return;
}

int main(){
	freopen("wtfname.in","r",stdin);
	freopen("wtfname.out","w",stdout);
	ReadIn();
	Build_AC_Automatic();
	Build_Fail_Tree();
	MoDui();
	PrintAns();
	return 0;
}