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
| #include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
int read(){
register int x = 0;
register char f = 1, ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f ^= 1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
return f ? x : -x;
}
#define N 150005
const int B = 420, C = 360, P = 550;
int n, q, k, a[N], b[N], c[N], vis[N];
int L[365][365][425], R[365][365][425], V[365][365][555];
void pre(){
for (register int i = 0; i < n; i += B){
for (register int j = 0; j < n; ++j) b[j] = 0;
for (register int j = 0; j < P; ++j) c[j] = 0;
for (register int j = i; j < n; ++j){
--c[b[a[j]]], ++b[a[j]], ++c[b[a[j]]];
if ((j + 1) % B == 0){
register int bi = i / B, bj = j / B;
for (register int k = 0; k < P; ++k) V[bi][bj][k] = c[k];
for (register int k = 0; k < B && i - k - 1 >= 0; ++k) L[bi][bj][k] = b[a[i - k - 1]];
for (register int k = 0; k < B && j + k + 1 < n; ++k) R[bi][bj][k] = b[a[j + k + 1]];
}
}
}
}
int solve(int q, int l, int r){
register int bl = (l - 1) / B + 1, br = (r + 1) / B - 1;
register int pl = B * bl, pr = B * (br + 1) - 1;
if (bl <= br){
for (register int i = 0; i < P; ++i) c[i] = V[bl][br][i];
for (register int i = 0; i < pl - l; ++i){
register int j = pl - i - 1;
if (vis[a[j]] != q) vis[a[j]] = q, b[a[j]] = L[bl][br][i];
--c[b[a[j]]], ++b[a[j]], ++c[b[a[j]]];
}
for (register int i = 0; i < r - pr; ++i){
register int j = pr + i + 1;
if (vis[a[j]] != q) vis[a[j]] = q, b[a[j]] = R[bl][br][i];
--c[b[a[j]]], ++b[a[j]], ++c[b[a[j]]];
}
}
else{
for (register int i = 0; i < P; ++i) c[i] = 0;
for (register int i = l; i <= r; ++i){
if (vis[a[i]] != q) vis[a[i]] = q, b[a[i]] = 0;
--c[b[a[i]]], ++b[a[i]], ++c[b[a[i]]];
}
}
for (register int i = 0; i < P; ++i) if (!c[i]) return i;
return -1;
}
int main(){
freopen("mex.in", "r", stdin);
freopen("mex.out", "w", stdout);
n = read(), q = read(), k = read();
for (register int i = 0; i < n; ++i) a[i] = b[i] = read();
std :: sort(b, b + n);
int m = std :: unique(b, b + n) - b;
for (register int i = 0; i < n; ++i)
a[i] = std :: lower_bound(b, b + m, a[i]) - b;
pre();
int ans = 0, l, r;
for (register int _ = 1; _ <= q; ++_){
l = (read() ^ (k * ans)) - 1, r = (read() ^ (k * ans)) - 1;
ans = solve(_, l, r), printf("%d\n", ans);
}
}
|
