RT

后三个点一直RE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
}

const int N = 1e6 + 10;
int n, m, B, tot, res = 0;
int tp, tq;
int col[N], vis[N];
int ans[N];
struct Upd{
	int pos, c, pre;
}p[N];
struct Qry{
	int l, r, t, qry;
}q[N];

#define get_B(x) x / B

inline bool cmp(Qry a, Qry b){
	if(get_B(a.l) != get_B(b.l)) return get_B(a.l) < get_B(b.l);
	return get_B(a.r) != get_B(b.r) ? get_B(a.r) < get_B(b.r) : a.t < b.t;
}

int main(){
	n = read(), m = read();
	for(int i = 1; i <= n; i++)
		col[i] = read();
	for(int i = 1; i <= m; i++){
		char op;
		int x, y;
		cin >> op >> x >> y;
		if(op == 'R'){
			p[++tp] = (Upd){x, y, col[x]};
			col[x] = y;
		}else q[++tq] = (Qry){x, y, tp, tq};
	}
	B = ceil(exp((log(n) + log(tp)) / 3));
	for(int i = tp; i >= 1; i--)
		col[p[i].pos] = p[i].pre;
	sort(q + 1, q + 1 + tq, cmp);
	int l = 1, r = 0, t = 0;
	for(int i = 1; i <= tq; i++){
		while(l > q[i].l) res += !vis[col[--l]]++;
		while(l < q[i].l) res -= !--vis[col[l++]];
		while(r < q[i].r) res += !vis[col[++r]]++;
		while(r > q[i].r) res -= !--vis[col[r--]];
		while(t > q[i].t){
			int x = p[t].pos;
			if(l <= x && x <= r) res -= !--vis[col[x]];
			col[x] = p[t--].pre;
			if(l <= x && x <= r) res += !vis[col[x]]++;
		}
		while(t < q[i].t){
			int x = p[++t].pos;
			if(l <= x && x <= r) res -= !--vis[col[x]];
			col[x] = p[t].c;
			if(l <= x && x <= r) res += !vis[col[x]]++;
		}
		ans[q[i].qry] = res;
	}
	for(int i = 1; i <= tq; i++)
		printf("%d\n", ans[i]);
	return 0;
}