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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| #pragma GCC optimize(3)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
const int maxn = 1e+5 + 5;
struct node
{
int pos, val;
bool operator < (const node &rhs) const {
return (val == rhs.val) ? (pos < rhs.pos) : (val < rhs.val);
}
}ar[maxn];
int n, c, m, a[maxn], bkt[maxn], tot, sum;
int blo, bel[maxn], f[2000][2000];
int stk[maxn], top;
int l[2000], r[2000];
int fir[maxn], lst[maxn], vis[maxn];
inline int rd() {
register int x = 0, c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
return x;
}
void init() {
for (int i = 1; i <= tot; ++i) {
sum = 0;
for (int j = l[i]; j <= n; ++j) bkt[a[j]] = 0;
for (int j = l[i]; j <= n; ++j) {
if (!(bkt[a[j]] & 1) && bkt[a[j]]) sum--;
bkt[a[j]]++;
if (!(bkt[a[j]] & 1)) sum++;
f[i][bel[j]] = sum;
}
}
for (int i = 1; i <= n; ++i) ar[i] = (node){i, a[i]};
sort(ar + 1, ar + 1 + n);
for (int i = 1; i <= n; ++i) {
if (!fir[ar[i].val]) fir[ar[i].val] = i;
lst[ar[i].val] = i;
}
}
int rbound(int up, int v) {
int L = fir[v], R = lst[v], ans = 0;
while (L <= R) {
int mid = (L + R) >> 1;
if (ar[mid].pos <= up) ans = mid, L = mid + 1;
else R = mid - 1;
}
return ans;
}
int lbound(int dn, int v) {
int L = fir[v], R = lst[v], ans = 0x3f3f3f3f;
while (L <= R) {
int mid = (L + R) >> 1;
if (dn <= ar[mid].pos) ans = mid, R = mid - 1;
else L = mid + 1;
}
return ans;
}
int find(int L, int R, int v) {
return max(rbound(R, v) - lbound(L, v) + 1, 0);
}
int solve(int L, int R) {
int ans = 0, bl = bel[L], br = bel[R];
if (bl == br || bl + 1 == br) {
for (int i = L; i <= R; ++i) {
if (vis[a[i]]) continue;
int t = find(L, R, a[i]);
if (!(t & 1)) ans++;
vis[a[i]] = 1;
}
for (int i = L; i <= R; ++i) vis[a[i]] = 0;
return ans;
} else {
int lb = l[bl + 1], rb = r[br - 1];
ans = f[bl + 1][br - 1];
for (int i = L; i < lb; ++i) {
if (vis[a[i]]) continue;
int extn = find(L, R, a[i]), intn = find(lb, rb, a[i]);
if (!(extn & 1)) {
if ((intn & 1) || !intn) ans++;
} else if (!(intn & 1) && intn) ans--;
vis[a[i]] = 1;
}
for (int i = rb + 1; i <= R; ++i) {
if (vis[a[i]]) continue;
int extn = find(L, R, a[i]), intn = find(lb, rb, a[i]);
if (!(extn & 1)) {
if ((intn & 1) || !intn) ans++;
} else if (!(intn & 1) && intn) ans--;
vis[a[i]] = 1;
}
for (int i = L; i < lb; ++i) vis[a[i]] = 0;
for (int i = rb + 1; i <= R; ++i) vis[a[i]] = 0;
return ans;
}
}
int main() {
n = rd(); c = rd(); m = rd();
for (int i = 1; i <= n; ++i) a[i] = rd();
blo = sqrt((double)n / log2(n));
for (int i = 1; i <= n; ++i) bel[i] = (i - 1) / blo + 1;
tot = (n % blo) ? (n / blo + 1) : (n / blo);
for (int i = 1; i < tot; ++i) l[i] = (i - 1) * blo + 1, r[i] = i * blo;
l[tot] = r[tot - 1] + 1; r[tot] = n;
init();
int ql, qr, lstans = 0;
while (m--) {
ql = (rd() + lstans) % n + 1;
qr = (rd() + lstans) % n + 1;
if (ql > qr) swap(ql, qr);
lstans = solve(ql, qr);
printf("%d\n", lstans);
}
return 0;
}
|
