「BZOJ2821」作诗(Poetize)

Description

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

Input

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

Output

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

Sample Input

1
2
3
4
5
6
7
5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

1
2
3
4
5
2
0
0
0
1

HINT

对于100%100\%的数据,1n,c,m1051\leq n,c,m\leq 10^5

Solution

分块。
定义fi,jf_{i,j}表示第[1,i][1,i]块,数字jj出现的个数。
ansi,jans_{i,j}表示第ii块到第jj块的答案。
预处理他们,ansans数组处理的时候不能枚举ii,然后枚举j[i,n]j\in[i,n],这无法处理。
而是要从LiL_i开始从后处理,遇到右端点就统计答案。

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
107
108
109
110
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

int n, c, m;
const int N = 1e5 + 6;
const int B = 320;
int a[N];
int L[N], R[N], tot, b[N];
int f[B][N];
int ans[B][B], tmp[N];

int query(int l, int r) {
if(b[l] == b[r]) {
int res = 0;
for(int i = l; i <= r; ++i) {
++tmp[a[i]];
if(!(tmp[a[i]] & 1)) ++res;
else if(tmp[a[i]] > 1) --res;
}
for(int i = l; i <= r; ++i) tmp[a[i]] =0;
return res;
}
int res = ans[b[l] + 1][b[r] - 1];
for(int j = l; j <= R[b[l]]; ++j) if(!tmp[a[j]]) {
tmp[a[j]] = f[b[r] - 1][a[j]] - f[b[l]][a[j]];
//if(tmp[a[j]] > 1 && !(tmp[a[j]] & 1)) --res;
}
for(int j = r; j >= L[b[r]]; --j) if(!tmp[a[j]]) {
tmp[a[j]] = f[b[r] - 1][a[j]] - f[b[l]][a[j]];
//if(tmp[a[j]] > 1 && !(tmp[a[j]] & 1)) --res;
}
for(int j = l; j <= R[b[l]]; ++j) {
++tmp[a[j]];

if(!(tmp[a[j]] & 1)) ++res;
else if(tmp[a[j]] > 1) --res;
}
for(int j = r; j >= L[b[r]]; --j) {
++tmp[a[j]];
if(!(tmp[a[j]] & 1)) ++res;
else if(tmp[a[j]] > 1) --res;
}
for(int j = l; j <= R[b[l]]; ++j) tmp[a[j]] = 0;
for(int j = r; j >= L[b[r]]; --j) tmp[a[j]] = 0;
return res;
}

int main() {
n = read(), c = read(), m = read();
for(int i = 1; i <= n; ++i) {
a[i] = read();
}
int t = sqrt(n);
for(int i = 1; i <= t; ++i) {
L[i] = tot + 1;
for(int j = 1; j <= t; ++j)
b[++tot] = i;
R[i] = tot;
}
if(tot < n) {
++t;
L[t] = tot + 1;
while(tot < n) b[++tot] = t;
R[t] = tot;
}
for(int i = 1; i <= t; ++i) {
for(int j = 1; j <= c; ++j) f[i][j] = f[i - 1][j];
for(int j = L[i]; j <= R[i]; ++j) ++f[i][a[j]];
}
for(int i = 1; i <= t; ++i) {
int cnt = 0;
for(int j = L[i]; j <= n; ++j) {
++tmp[a[j]];
if(!(tmp[a[j]] & 1)) ++cnt;
else if(tmp[a[j]] > 1) --cnt;
if(R[b[j]] == j) ans[i][b[j]] = cnt;
}
for(int j = L[i]; j <= n; ++j) tmp[a[j]] = 0;
}
/*for(int i = 1; i <= t; ++i)
for(int j = i; j <= t; ++j)
printf("%d->%d %d\n", i, j, ans[i][j]);*/
int ans = 0;
for(int i = 1; i <= m; ++i) {
int l = read(), r = read();
l = (l + ans) % n + 1;
r = (r + ans) % n + 1;
if(l > r) swap(l, r);
writeln(ans = query(l, r));
}
return 0;
}