BZOJ 2821 作诗 （分块）

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

作诗

问题描述

神犇SJY虐完HEOI之后给傻×LYD出了一题：
SHY是T国的公主，平时的一大爱好是作诗。
由于时间紧迫，SHY作完诗之后还要虐OI，于是SHY找来一篇长度为N的文章，阅读M次，每次只阅读其中连续的一段[l,r]，从这一段中选出一些汉字构成诗。因为SHY喜欢对偶，所以SHY规定最后选出的每个汉字都必须在[l,r]里出现了正偶数次。而且SHY认为选出的汉字的种类数（两个一样的汉字称为同一种）越多越好（为了拿到更多的素材！）。于是SHY请LYD安排选法。
LYD这种傻×当然不会了，于是向你请教……
问题简述：N个数，M组询问，每次问[l,r]中有多少个数出现正偶数次。

输入格式

输入第一行三个整数n、c以及m。表示文章字数、汉字的种类数、要选择M次。
第二行有n个整数，每个数Ai在[1, c]间，代表一个编码为Ai的汉字。
接下来m行每行两个整数l和r，设上一个询问的答案为ans(第一个询问时ans=0)，令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交换L和R，则本次询问为[L,R]。

输出格式

输出共m行，每行一个整数，第i个数表示SHY第i次能选出的汉字的最多种类数。

样例输入

5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

样例输出

2
0
0
0
1

提示

1<=n,c,m<=10^5

强制在线，用分块处理。

首先，如果$L$，$R$在同一块，那么暴力枚举每一个位置，算出答案。然后考虑不在同一块时。

注意到为了算出答案，需要知道每种颜色出现的次数，但是每个位置去算肯定会超时，注意到询问可以分成三个部分，$L$所在的块，$R$所在的块，和他们中间的块，那么如果知道了中间所有块中，出现了正偶数次的数有多少个，同时知道了$L$,$R$所在块中出现的颜色在整个询问区间中出现的次数，那么就可以算出答案。

首先处理中间块的出现了正偶数次的数有多少。显然需要预处理。
那么令$F[i][j]$表示从第$i$块到第$j$块的答案，那么这个可以在$O(n\sqrt{n}$内处理出来，具体实现可以参考代码。

然后考虑如何知道$L$,$R$所在块中的数字在整个区间中出现的次数，同样分成两部分来考虑，一部分是中间块的出现次数，另一部分是$L$，$R$所在块的出现次数。后者每次暴力枚举即可，考虑前者，考虑前缀和。
那么令$G[i][j]$表示$[1,i]$块中数字$j$出现的次数，那么同样可以$O(n\sqrt{n})$处理出来，处理方法见代码。

于是就可以处理不在同一块的情况了，先令$Sum$为中间块的答案，每次只需要看$L$,$R$所在块中出现的数字在中间块中出现的次数和在全区间出现次数的关系对$Sum$进行修改即可。

代码：

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
#include<stdio.h>
#include<cmath>
#include<cstring>
#define M 100005
using namespace std;
int n,c,m,S,N,ans,A[M],F[333][333],G[333][M],cnt[M],T[M],Q[M],ID[M];
int GS(int x,int y,int t)
{
	int l=ID[x];
	int r=ID[y];
	int sum=0,p,q,i,j;
	if(l==r)
	{
		for(i=x;i<=y;i++)
		{
			if(T[A[i]]!=t)cnt[A[i]]=0,T[A[i]]=t;
		    if(!(cnt[A[i]]&1)&&cnt[A[i]])sum--;
		    cnt[A[i]]++;
		    if(!(cnt[A[i]]&1))sum++;
		}
		return sum;
	}
	if(l+1<=r-1)sum=F[l+1][r-1];
	for(i=x;i<=l*S&&i<=n;i++)
	{
		if(T[A[i]]!=t)cnt[A[i]]=0,T[A[i]]=t;
		p=cnt[A[i]];
		if(l+1<=r-1)p+=G[r-1][A[i]]-G[l][A[i]];
		if(p&&(!(p&1)))sum--;
		cnt[A[i]]++;p++;
		if(p&&(!(p&1)))sum++;
	}
	for(i=y;i>(r-1)*S;i--)
	{
		if(T[A[i]]!=t)cnt[A[i]]=0,T[A[i]]=t;
		p=cnt[A[i]];
		if(l+1<=r-1)p+=G[r-1][A[i]]-G[l][A[i]];
		if(p&&(!(p&1)))sum--;
		cnt[A[i]]++;p++;
		if(p&&(!(p&1)))sum++;
	}
	return sum;
}
int main()
{
	int i,j,k,p,x,y;
	scanf("%d%d%d",&n,&c,&m);
	for(i=1;i<=n;i++)scanf("%d",&A[i]);
	S=sqrt(n);N=(n-1)/S+1;
	for(i=1;i<=n;i++)ID[i]=(i-1)/S+1;//预处理块的id
	
	for(i=1;i<=N;i++)
	for(j=(i-1)*S+1;j<=n;j++)//预处理F[i][j]
	{
		p=ID[j];
		if(j%S==1)F[i][p]=F[i][p-1];
		if(Q[A[j]]!=i)Q[A[j]]=i,cnt[A[j]]=0;
		if(!(cnt[A[j]]&1)&&cnt[A[j]])F[i][p]--;
		cnt[A[j]]++;
		if(!(cnt[A[j]]&1))F[i][p]++;
	}
	
	memset(cnt,0,sizeof(cnt));
	for(i=1;i<=n;i++)//预处理G[i][j]
	{
		cnt[A[i]]++;
		if(i%S==0||i==n)
		{
			p=ID[i];
			for(k=1;k<=c;k++)G[p][k]=cnt[k];
		}
	}
	
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		x=(x+ans)%n+1;
		y=(y+ans)%n+1;
		if(x>y)x^=y^=x^=y;
		ans=GS(x,y,i);
		printf("%d\n",ans);
	}
}