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
| #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long ll;
ll const MAXN = 1000010;
struct x {
ll where, val;
} xiu[MAXN];
struct c {
ll l, r, pre, id;
} cha[MAXN];
ll xiugai = 0, chaxun = 0, N, M, a[MAXN], kuai[MAXN];
ll color[MAXN], ans, ooo[MAXN];
bool st(c, c);
void read(ll &x);
int main() {
read(N);read(M);
ll tem = pow(N, 0.75);
for (ll i = 1; i <= N; i++) {
read(a[i]);
kuai[i] = (i-1)/tem+1;
}
for (ll i = 1; i <= M; i++) {
char opt[5];
scanf("%s", opt);
if (opt[0] == 'Q') {
chaxun++;
read(cha[chaxun].l);read(cha[chaxun].r);
cha[chaxun].id = chaxun;
cha[chaxun].pre = xiugai;
} else {
++xiugai;
read(xiu[xiugai].where);read(xiu[xiugai].val);
}
}
sort(cha+1, cha+chaxun+1, st);
ll l = 1, r = 0, now = 0;
for (ll i = 1; i <= chaxun; i++) {
while (cha[i].l < l) {
ans += (++color[a[l-1]]) == 1;
l--;
}
while (cha[i].l > l) {
ans -= (--color[a[l]] == 0);
l++;
}
while (cha[i].r < r) {
ans -= (--color[a[r]] == 0);
r--;
}
while (cha[i].r > r) {
ans += (++color[a[r+1]] == 1);
r++;
}
while (now < cha[i].pre) {
now++;
if (xiu[now].where >= cha[i].l && xiu[now].where <= cha[i].r) {
if (--color[a[xiu[now].where]] == 0) ans--;
if (++color[xiu[now].val] == 1) ans++;
}
swap(a[xiu[now].where], xiu[now].val);
}
while (now > cha[i].pre) {
if (xiu[now].where >= cha[i].l && xiu[now].where <= cha[i].r) {
if (--color[a[xiu[now].where]] == 0) ans--;
if (++color[xiu[now].val] == 1) ans++;
}
swap(a[xiu[now].where], xiu[now].val);
now--;
}
ooo[cha[i].id] = ans;
}
for (ll i = 1; i <= chaxun; i++) {
printf("%lld\n", ooo[i]);
}
return 0;
}
bool st(c a, c b) {
return (kuai[a.l] ^ kuai[b.l]) ? kuai[a.l] < kuai[b.l] : ((kuai[a.r] ^ kuai[b.r]) ? kuai[a.r] < kuai[b.r] : a.pre < b.pre);
}
void read(ll &x) {
char s = getchar();
x = 0;
while (s < '0' || s > '9') {
s = getchar();
}
while (s >= '0' && s <= '9') {
x = 10 * x + (s - '0');
s = getchar();
}
}
|
