SCOI2012 喵星球上的点名

wjh15101051's space

卧薪尝胆，厚积薄发。

SCOI2012 喵星球上的点名

Date: Mon Nov 26 22:02:06 CST 2018

In Category: NoCategory

Description：

每个人有姓和名两个字符串，多次询问，每次给出一个字符串，询问有多少人的姓和名包括这个串，以及每个人包括多少个点名串。

$1\leqslant n\leqslant 5\times 10^4,1\leqslant \sum|S|\leqslant 10^5,1\leqslant \Sigma\leqslant 10^4$

Solution：

先把所有名字还有所有询问串连起来求后缀数组，这样每个询问串对应一段区间，问题就变成了区间数颜色，可以用莫队，然后第二问可以再进入某个节点的时候加上还剩的询问，退出时减去还剩的询问即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXL 400010

int s[MAXL],tot = 0;

int id[MAXL];

int pos[MAXL];

#define MAX 20010

int sa[MAXL],rnk[MAXL],height[MAXL],t1[MAXL],t2[MAXL],c[MAXL];

void make_SA(int n,int m)

{

	int p = 0;

	int *x = t1,*y = t2;

	for(int i = 1;i <= m;++i)c[i] = 0;

	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 = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(int k = 1;k <= n;k = k << 1)

	{

		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 = 1;i <= m;++i)c[i] = 0;

		for(int i = 1;i <= n;++i)++c[x[y[i]]];

		for(int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		p = 0;

		swap(x,y);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);

		}

		if(p >= n)break;

		m = p;

	}

	for(int i = 1;i <= n;++i)

	{

		rnk[sa[i]] = i;

	}

	int k = 0;

	for(int i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		int j = sa[rnk[i] - 1];

		while(j + k <= n && s[i + k] == s[j + k])++k;

		height[rnk[i]] = k;

	}

	/*for(int i = 1;i <= n;++i)

	{cout << height[i] << " " << s[sa[i]] << endl;

		//for(int x = sa[i];x <= n;++x)cout << s[x] << " ";cout << " : " << height[i] << endl;

	}cout << endl;*/

	return;

}

int f[MAXL][20];

int my_log2[MAXL];

int query_min(int l,int r)

{

	int len = my_log2[r - l + 1];

	return min(f[l][len],f[r - (1 << len) + 1][len]);

}

int query_lef(int p,int h)

{

	int l = 1,r = p,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(query_min(mid + 1,p) >= h)r = mid;

		else l = mid + 1;

	}

	return l;

}

int query_rig(int p,int h)

{

	int l = p,r = tot,mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(query_min(p + 1,mid) >= h)l = mid;

		else r = mid - 1;

	}

	return l;

}

struct query

{

	int l,r,id,ans;

}q[MAXL];

int blo[MAXL];

bool cmp(query a,query b){return (blo[a.l] == blo[b.l] ? a.r < b.r : blo[a.l] < blo[b.l]);}

bool cmp_id(query a,query b){return a.id < b.id;}

int res[MAXL];

int cnt[MAXL],ans = 0;

void add(int k,int cur)

{

	if(k == 0)return;

	if(cnt[k] == 0)

	{

		res[k] += m - cur + 1;

		++ans;

	}

	++cnt[k];

	return;

}

void rem(int k,int cur)

{

	if(k == 0)return;

	--cnt[k];

	if(cnt[k] == 0)

	{

		--ans;

		res[k] -= m - cur + 1;

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int l;

	int maxn = MAX;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&l);

		for(int x = 1;x <= l;++x){id[++tot] = i;scanf("%d",&s[tot]);}

		s[++tot] = ++maxn;

		scanf("%d",&l);

		for(int x = 1;x <= l;++x){id[++tot] = i;scanf("%d",&s[tot]);}

		s[++tot] = ++maxn;

	}

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&l);

		pos[i] = tot + 1;

		for(int x = 1;x <= l;++x){++tot;scanf("%d",&s[tot]);}

		s[++tot] = ++maxn;

	}

	for(int i = 1;i <= tot;++i)++s[i];

	//for(int i = 1;i <= tot;++i)cout << s[i] << " ";cout << endl;

	make_SA(tot,MAXL);

	for(int i = 1;i <= tot;++i)f[i][0] = height[i];

	for(int k = 1;k <= 19;++k)

		for(int i = 1;i <= tot - (1 << k) + 1;++i)

			f[i][k] = min(f[i][k - 1],f[i + (1 << (k - 1))][k - 1]);

	for(int i = 2;i <= tot;++i)my_log2[i] = my_log2[i >> 1] + 1;

	int block = sqrt(tot);

	for(int i = 1;i <= tot;++i)blo[i] = (i - 1) / block + 1;

	for(int i = 1;i <= m;++i)

	{

		int lenth = (i == m ? tot : pos[i + 1] - 1) - pos[i];

		q[i].l = query_lef(rnk[pos[i]],lenth);

		q[i].r = query_rig(rnk[pos[i]],lenth);

		q[i].id = i;

	}

	sort(q + 1,q + 1 + m,cmp);

	for(int i = 1,l = 1,r = 0;i <= m;++i)

	{

		while(r < q[i].r)add(id[sa[++r]],i);

		while(l > q[i].l)add(id[sa[--l]],i);

		while(r > q[i].r)rem(id[sa[r--]],i);

		while(l < q[i].l)rem(id[sa[l++]],i);

		q[i].ans = ans;

	}

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)printf("%d\n",q[i].ans);

	for(int i = 1;i <= n;++i)printf("%d ",res[i]);

	puts(""); 

	return 0;

}

In tag: 字符串-后缀数组数据结构-莫队

wjh15101051