NKOJ 2564 （SCOI 2012）喵星球上的点名（后缀数组+树状数组）

发表于 |
字数统计: 1,758字 | 阅读时长 ≈ 8min

P2564【SCOI2012】喵星球上的点名

问题描述

a180285幸运地被选做了地球到喵星球的留学生。他发现喵星人在上课前的点名现象非常有趣。

假设课堂上有N个喵星人，每个喵星人的名字由姓和名构成。喵星球上的老师会选择M个串来点名，每次读出一个串的时候，如果这个串是一个喵星人的姓或名的子串，那么这个喵星人就必须答到。

然而，由于喵星人的字码过于古怪，以至于不能用ASCII码来表示。为了方便描述，a180285决定用数串来表示喵星人的名字。

现在你能帮助a180285统计每次点名的时候有多少喵星人答到，以及M次点名结束后每个喵星人答到多少次吗？

输入格式

现在定义喵星球上的字符串给定方法：
先给出一个正整数L，表示字符串的长度，接下来L个整数表示字符串的每个字符。
输入的第一行是两个整数N和M。
接下来有N行，每行包含第i 个喵星人的姓和名两个串。姓和名都是标准的喵星球上的字符串。
接下来有M行，每行包含一个喵星球上的字符串，表示老师点名的串。

输出格式

对于每个老师点名的串输出有多少个喵星人应该答到。
然后在最后一行输出每个喵星人被点到多少次。

样例输入

2 3
6 8 25 0 24 14 8 6 18 0 10 20 24 0
7 14 17 8 7 0 17 0 5 8 25 0 24 0
4 8 25 0 24
4 7 0 17 0
4 17 0 8 25

样例输出

2
1
0
1 2

数据范围

对于30%的数据，保证：
1<=N,M<=1000，喵星人的名字总长不超过4000，点名串的总长不超过2000。
对于100%的数据，保证：
1<=N<=20000，1<=M<=50000，喵星人的名字总长和点名串的总长分别不超过100000，保证喵星人的字符串中作为字符存在的数不超过10000。

分开考虑两种询问，考虑第一问，先对所有的名和姓连起来，中间插入字符构建后缀数组，记录每一个位置属于那个人。

那么对于一次询问，由于SA数组有序，可以直接二分查找找到询问串在SA数组中的位置，显然如果该询问是一些人的子串，那么在SA数组中这些对应后缀必然是一个连续的区间，那么问题变成询问一个区间中有多少种不同的值，离线后缀数组处理即可。
处理时将询问按照对应区间左右端点排序，记录下SA数组中每一个值下一个相同值出现的位置，然后将每个值的第一次出现的位置加到树状数组中，每次删除一个值后，将对应的下一个值加进来即可。每个询问对应的答案就是将小于左端点的位置处理完了后，右端点的前缀和。

考虑询问二，每个人答到多少次，问题等价于求每种值被多少个区间覆盖，那么同样将询问排序，每次将左端点小于当前讨论到的位置的区间左端点加一，右端点减一。那么当前点的前缀和就是这个点被覆盖次数。但是这样显然要算重，那么需要减去讨论到上一个相同值的点时，这个点的前缀和。记录一下就好。

具体可以参见代码。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define N 200005
using namespace std;
struct node{int L,R,id,ans;}Q[N];
int n,m,A[N],B[N],SA[N],C[N],Rank[N],H[N],L;
int wa[N],wb[N],T[N];
int LA[N],NE[N],cnt[N],G[N];
bool cmp(int a,int b)
{
	int i;
	for(i=0;A[a+i]==C[b+i];i++);
	return A[a+i]<C[b+i];
}
bool ccmp(node a,node b)
{
	if(a.L==b.L)return a.R<b.R;
	return a.L<b.L;
}
bool cccmp(node a,node b)
{return a.id<b.id;}
bool equ(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void GSA(int *r,int *sa,int a,int b)
{
	int i,j,p,*x=wa,*y=wb,*t;
	for(i=0;i<b;i++)T[i]=0;
	for(i=0;i<a;i++)T[x[i]=r[i]]++;
	for(i=1;i<b;i++)T[i]+=T[i-1];
	for(i=a-1;i>=0;i--)sa[--T[x[i]]]=i;
	for(p=1,j=1;p<a;j<<=1,b=p)
	{
		for(p=0,i=a-j;i<a;i++)y[p++]=i;
		for(i=0;i<a;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<b;i++)T[i]=0;
		for(i=0;i<a;i++)T[x[y[i]]]++;
		for(i=1;i<b;i++)T[i]+=T[i-1];
		for(i=a-1;i>=0;i--)sa[--T[x[y[i]]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<a;i++)
		x[sa[i]]=equ(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void GH(int *r,int *sa,int a)
{
	int i,j,k=0;
	for(i=1;i<=a;i++)Rank[sa[i]]=i;
	for(i=0;i<a;H[Rank[i++]]=k)
	for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);
}
void MD(int x,int d)
{for(int i=x;i<=L;i+=(i&-i))G[i]+=d;}
int GS(int x)
{
	int i,sum=0;
	for(i=x;i;i-=(i&-i))sum+=G[i];
	return sum;
}
int main()
{
	int i,j,k,x,y,p;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&k);for(j=1;j<=k;j++)scanf("%d",&A[L]),A[L]++,B[L++]=i;A[L++]=10000+i;
		scanf("%d",&k);for(j=1;j<=k;j++)scanf("%d",&A[L]),A[L]++,B[L++]=i;A[L++]=10000+i;
	}
	A[L]=0;GSA(A,SA,L+1,100005);GH(A,SA,L);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&k);Q[i].id=i;
		for(j=0;j<k;j++)scanf("%d",&C[j]),C[j]++;
		C[k]=-1;Q[i].L=lower_bound(SA+1,SA+L+1,0,cmp)-SA;
		C[k]=100005;Q[i].R=lower_bound(SA+1,SA+L+1,0,cmp)-SA;
	}
	for(i=1;i<=L;i++)C[i]=B[SA[i]];
	for(i=L;i>=1;i--)
	{
		NE[i]=LA[C[i]]?LA[C[i]]:L+1;
		LA[C[i]]=i;
	}
	sort(Q+1,Q+m+1,ccmp);j=1;
	for(i=1;i<=n;i++)MD(LA[i],1);
	for(i=1;i<=m;i++)
	{
		while(Q[i].L>j)
		{
			if(C[j]==0){j++;continue;}
			MD(j,-1);MD(NE[j],1);j++;
		}
		Q[i].ans=GS(Q[i].R-1);
	}
	
	memset(LA,0,sizeof(LA));
	memset(G,0,sizeof(G));j=1;
	for(i=1;i<=L;i++)
	{
		if(C[i]==0)continue;
		while(j<=m&&Q[j].L<=i)MD(Q[j].L,1),MD(Q[j].R,-1),j++;
		cnt[C[i]]+=GS(i)-LA[C[i]];
		LA[C[i]]=GS(NE[i]);
	}
	sort(Q+1,Q+m+1,cccmp);
	for(i=1;i<=m;i++)printf("%d\n",Q[i].ans);
	for(i=1;i<=n;i++)printf("%d ",cnt[i]);
}