```cpp
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
inline ll read() {
ll ans = 0;
char last = ' ', ch = getchar();
while (ch < '0' || ch > '9') last = ch, ch = getchar();
while (ch >= '0' && ch <= '9') ans = ans * 10 + ch -'0', ch = getchar();
if (last == '-') return -ans;
return ans;
}
void write(int x) {
if (x > 9) write(x / 10);
putchar(x%10 + '0');
}
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
int last[N], a[N], bl[N], sum[N];
struct QUERY {
int l, r, id, tim;
} q[N];
struct CHANGE {
int p, col, last;
} c[N];
bool cmp_1(const QUERY &a, const QUERY &b) {
/*if (bl[a.l] == bl[b.l]) {
if (bl[a.r] == bl[b.r]) return a.tim < b.tim;
return a.r < b.r;
}
return a.l < b.l;*/
if (bl[a.l] ^ bl[b.l]) {
return bl[a.l] < bl[b.l];
} else {
if (bl[a.r] ^ bl[b.r]) return bl[a.r] < bl[b.r];
return bl[a.r] & 1 ? a.r < b.r : a.r > b.r;
}
}
int num = 0;
int l;
int r;
inline void modify(int x, int v) {
sum[a[x]] += v;
if (sum[a[x]] == 0 && v < 0) num--;
if (sum[a[x]] == 1 && v > 0) num++;
}
inline void go(int tim, int col) {
int pos = c[tim].p;
if (l <= pos && pos <= r) modify(pos, -1), a[pos] = col, modify(pos, 1);
else a[pos] = col;
}
int n, m;
int ans[N];
char op[5];
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = read(), m = read();
int blo = pow(n, 0.6666667);
int tim = 0, t = 0;
for (int i = 1; i <= n; ++i) a[i] = read(), bl[i] = i / blo + 1, last[i] = a[i];
for (register int i = 1; i <= m; ++i) {
scanf("%c", &op[0]);
if (op[0] == 'Q') {
++t;
q[t].id = t;
q[t].l = read(), q[t].r = read();
q[t].tim = tim;
} else {
c[++tim].p = read(), c[tim].col = read();
c[tim].last = last[c[tim].p];
last[c[tim].p] = c[tim].col;
}
}
sort(q + 1, q + t + 1, cmp_1);
tim = 0;
l = 1, r = 0;
for (register int i = 1; i <= m; ++i) {
while (tim < q[i].tim) go(tim + 1, c[tim + 1].col), tim++;
while (tim > q[i].tim) go(tim, c[tim].last), tim--;
while (l < q[i].l) {modify(l, -1), ++l;}
while (l > q[i].l) {modify(l - 1, 1), --l;}
while (r < q[i].r) {modify(r + 1, 1), ++r;}
while (r > q[i].r) {modify(r, -1), --r;}
ans[q[i].id] = num;
}
for (int i = 1; i <= t; ++i) {
write(ans[i]);
puts("");
}
return 0;
}
```
by Stream月 @ 2020-04-22 23:41:56
@[Stream月](/user/156945) 改块大小
by DepletedPrism @ 2020-04-22 23:51:03
@[DepletedPrism](/user/109751) 造个大样例试块大小？
by Stream月 @ 2020-04-22 23:55:44
@[Stream月](/user/156945) 可以看第一篇题解的...
~~感觉只造一点大样例容易得出在某些特定条件下较快的结果...~~
by DepletedPrism @ 2020-04-23 00:02:09
过了，给你~~魔~~改了一下代码
```cpp
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
//char buf[1<<23],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline ll read() {
ll ans = 0;
char last = ' ', ch = getchar();
while (ch < '0' || ch > '9') last = ch, ch = getchar();
while (ch >= '0' && ch <= '9') ans = ans * 10 + ch -'0', ch = getchar();
if (last == '-') return -ans;
return ans;
}
void write(int x) {
if (x > 9) write(x / 10);
putchar(x%10 + '0');
}
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5;
int blo,last[N], a[N], bl[N], sum[N];
struct QUERY {
int l, r, id, tim;
bool operator < (QUERY a){
if((l / blo) ^ (a.l / blo)) return l / blo < a.l / blo;
else if((r / blo) ^ (a.r / blo)) return r / blo < a.r / blo;
else return tim < a.tim;
}
} q[N];
struct CHANGE {
int p, col, last;
} c[N];
bool cmp_1(const QUERY &a, const QUERY &b) {
/*if (bl[a.l] == bl[b.l]) {
if (bl[a.r] == bl[b.r]) return a.tim < b.tim;
return a.r < b.r;
}
return a.l < b.l;*/
if (bl[a.l] ^ bl[b.l]) {
return bl[a.l] < bl[b.l];
} else {
if (bl[a.r] ^ bl[b.r]) return bl[a.r] < bl[b.r];
return a.tim < b.tim;
}
}
int num = 0;
int l;
int r;
inline void modify(int x, int v) {
sum[a[x]] += v;
if (sum[a[x]] == 0 && v < 0) num--;
if (sum[a[x]] == 1 && v > 0) num++;
num -= !--sum[a[x]];
num += !sum[a[x]] ++;
}
inline void go(int tim, int col) {
int pos = c[tim].p;
if (l <= pos && pos <= r) num -= !--sum[a[pos]], a[pos] = col, num += !sum[a[pos]] ++;
else a[pos] = col;
}
int n, m;
int ans[N];
char op[5];
int main() {
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = read(), m = read();
//int blo = pow(n, 0.6666667);
int tim = 0, t = 0;
for (int i = 1; i <= n; ++i) a[i] = read(), last[i] = a[i];
for (register int i = 1; i <= m; ++i) {
if (getchar() == 'Q') {
++t;
q[t].id = t;
q[t].l = read(), q[t].r = read();
q[t].tim = tim;
} else {
c[++tim].p = read(), c[tim].col = read();
c[tim].last = last[c[tim].p];
last[c[tim].p] = c[tim].col;
}
}
blo = ceil(exp((log(n)+log(tim))/3));
// for (int i = 1; i <= n; ++i) {
// bl[i] = i / blo + 1;
// }
sort(q + 1, q + t + 1);
tim = 0;
l = 1, r = 0;
for (register int i = 1; i <= m; ++i) {
while (tim < q[i].tim) {
tim ++;
int pos = c[tim].p;
if (l <= pos && pos <= r) num -= !--sum[a[pos]], a[pos] = c[tim].col, num += !sum[a[pos]] ++;
else a[pos] = c[tim].col;
}
while (tim > q[i].tim) {
int pos = c[tim].p;
if (l <= pos && pos <= r) num -= !--sum[a[pos]], a[pos] = c[tim].last, num += !sum[a[pos]] ++;
else a[pos] = c[tim].last;
tim --;
}
// while (tim < q[i].tim) go(tim + 1, c[tim + 1].col), tim++;
// while (tim > q[i].tim) go(tim, c[tim].last), tim--;
while (l < q[i].l) num -= !--sum[a[l++]];
while (l > q[i].l) num += !sum[a[--l]] ++;
while (r < q[i].r) num += !sum[a[++r]] ++;
while (r > q[i].r) num -= !--sum[a[r --]];
ans[q[i].id] = num;
}
for (int i = 1; i <= t; ++i) {
write(ans[i]);
puts("");
}
return 0;
}
```
by __ykl @ 2020-04-23 07:29:54
~~改完居然跑的比我自己的还快~~
by __ykl @ 2020-04-23 07:33:47
火车头再世。。
by bovine__kebi @ 2020-04-23 08:18:11
@[刘开予2019](/user/172763) 多谢，带佬orz
by Stream月 @ 2020-04-23 09:08:55