记录编号	216610	评测结果	AAAAAAAAAA
题目名称	[SCOI 2012] 喵星球上的点名	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	4.609 s
提交时间	2015-12-30 08:19:50	内存使用	86.21 MiB

#include<cstdio>
#include<iostream>

#define maxn 200010
#define lson tr[rt].l
#define rson tr[rt].r

using namespace std;

int n,m,s[maxn],st[maxn],sa[maxn],rank[maxn],c[maxn],t[maxn],tt[maxn],len,num;
int las[maxn],bel[maxn],ans[maxn],rot[maxn],mark[maxn*30];

struct Tree{
	int l,r,w,ver;
}tr[maxn*30];

void getsa()
{
	int *x=t,*y=tt,n=len,m=10001;
	for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
	for(int i=1;i<=m;i++) c[i]+=c[i-1];
	for(int i=1;i<=n;i++) sa[c[x[i]]--]=i;
	for(int k=1;k<=n;k<<=1){
		int p=0;
		for(int i=n-k+1;i<=n;i++) y[++p]=i;
		for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;
		for(int i=0;i<=m;i++) c[i]=0;
		for(int i=1;i<=n;i++) c[x[i]]++;
		for(int i=1;i<=m;i++) c[i]+=c[i-1];
		for(int i=p;i>=1;i--) sa[c[x[y[i]]]--]=y[i];
		swap(x,y);
		p=1;x[sa[1]]=1;
		for(int i=2;i<=n;i++) 
			x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;
		m=p;
		if(m>=n) break;
	}
	return;
}

inline void update(int rt){ tr[rt].w=tr[lson].w+tr[rson].w; }

void Modify(int pos,int val,int l,int r,int lrt,int &rt,int ver)
{
	if(tr[rt].ver!=ver){
		rt=++num;
		tr[rt]=tr[lrt];
		tr[rt].ver=ver;
	}
	if(l==r){
		tr[rt].w+=val;return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid){
		Modify(pos,val,l,mid,tr[lrt].l,lson,ver);
	}else{
		Modify(pos,val,mid+1,r,tr[lrt].r,rson,ver);
	}
	update(rt);
	return;
}

int Query(int al,int ar,int l,int r,int rt)
{
	if(tr[rt].w==0) return 0;
	if(al<=l&&r<=ar){
		mark[rt]++;
		return tr[rt].w;
	}
	int mid=(l+r)>>1;
	int ret=0;
	if(mid>=al){
		ret+=Query(al,ar,l,mid,lson);
	}
	if(mid<ar){
		ret+=Query(al,ar,mid+1,r,rson);
	}
	return ret;
}

inline bool cmp1(int l,int len)
{
	for(int i=1;i<=len;i++,l++){
		if(s[l]==st[i]) continue;
		if(s[l]<st[i]) return 1;
		return 0;
	}
	return 1;
}

inline bool cmp2(int l,int len)
{
	for(int i=1;i<=len;i++,l++){
		if(s[l]==st[i]) continue;
		if(s[l]<st[i]) return 0;
		return 1;
	}
	return 1;
}

int findr(int n)
{
	int l=1,r=len,ret=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(cmp1(sa[mid],n)){
			ret=mid;
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	return ret;
}

int findl(int n)
{
	int l=1,r=len,ret=len+1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(cmp2(sa[mid],n)){
			ret=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	return ret;
}

void clearmark(int l,int r,int rt,int ver)
{
	if(tr[rt].ver!=ver||!tr[rt].w) return;
	if(l==r){
		ans[bel[sa[l]]]+=mark[rt];
		mark[rt]=0;
		return;
	}
	int mid=(l+r)>>1;
	mark[lson]+=mark[rt];
	mark[rson]+=mark[rt];
	clearmark(l,mid,lson,ver);
	clearmark(mid+1,r,rson,ver);
	mark[rt]=0;
	return;
}

int main()
{
	freopen("wtfname.in","r",stdin);
	freopen("wtfname.out","w",stdout);
	scanf("%d%d",&n,&m);len++;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=2;j++){
			int _n;scanf("%d",&_n);
			for(int k=1;k<=_n;len++,k++){
				scanf("%d",&s[len]);
				bel[len]=i;
			}
			bel[len]=i;
			s[len++]=10001;
		}
	}
	len--;
	getsa();
	for(int i=1;i<=len;i++){
		if(las[bel[sa[i]]]) Modify(las[bel[sa[i]]],-1,1,len,rot[i-1],rot[i],i);
		Modify(i,1,1,len,rot[i-1],rot[i],i);
		las[bel[sa[i]]]=i;
	}
	for(int i=1;i<=m;i++){
		int _n;
		scanf("%d",&_n);
		for(int i=1;i<=_n;i++) scanf("%d",&st[i]);
		int al=findl(_n),ar=findr(_n);
		if(al>ar){
			puts("0");continue;
		}
		printf("%d\n",Query(al,ar,1,len,rot[ar]));
	}
	for(int i=len;i>0;i--){
		clearmark(1,len,rot[i],i);
	}
	for(int i=1;i<n;i++) printf("%d ",ans[i]);
	printf("%d",ans[n]);
	getchar();getchar();
	return 0;
}