RT

P1903 [国家集训队]数颜色 / 维护队列

# include <iostream>
# include <cmath>
# include <algorithm>
# include <cstdio>
using namespace std;
const int N = 1e8 + 5;
int a[N];
int n , m;
char opt[2];
int x , y;
int l , r , t;
typedef struct {
	int l , r , id , Time;
}Ask;
Ask ask[N];
int Ans[N];
int tot = 0;
int cnt[N];
typedef struct {
	int pos , New , old;
}Change;
Change change[N];
int A[N];
void del(int p) {
	int k = A[p];
	cnt[k] --;
	if (cnt[k] == 0) tot --;
}
void add(int p) {
	int k = A[p];
	cnt[k] ++;
	if (cnt[k] == 1) tot ++;
}
void modify(int p , int v) {
	if (p >= l && p <= r) del(p);
	A[p] = v;
	if (p >= l && p <= r) add(p);
}
int sq;
int ltk[N];
bool cmp(Ask a , Ask b) {
	if (ltk[a.l] == ltk[b.l]) return a.r < b.r;
	else return ltk[a.l] < ltk[b.l];
}


int main() {
	cin >> n >> m;
	sq = sqrt(n);
	for (register int i = 1 ; i <= n ; i ++) {
		cin >> a[i];
		A[i] = a[i];
		ltk[i] = (i - 1) / sq + 1;
	}
	int Num = 0;
    for (register int i = 1 , j = 0 ; i <= m ; i ++) {
        cin >> opt >> x >> y;
    	if (opt[0] == 'Q') {
    		Num ++;
    		ask[Num].l = x;
    		ask[Num].r = y;
    		ask[Num].id = Num;
    		ask[Num].Time = j;
		} else {
			j ++;
			change[j].pos = x;
			change[j].New = y;
			change[j].old = a[x];
			a[x] = y;
		}
	}  
	sort(ask + 1 , ask + 1 + Num , cmp);
	l = r = t = 0;
	for (register int i = 1 ; i <= Num ; i ++) {
		while (r < ask[i].r) add(r + 1) , r ++;
		while (r > ask[i].r) del(r) , r --;
		while (l < ask[i].l) del(l) , l ++;
		while (l > ask[i].l) add(l - 1) , l --;
		while (t > ask[i].Time) modify(change[t].pos , change[t].old) , t --;
		while (t < ask[i].Time) t ++ , modify(change[t].pos , change[t].New);
		Ans[ask[i].id] = tot;
	}
	for (register int i = 1 ; i <= Num ; i ++) {
		printf("%d\n" , Ans[i]);
	}
	return 0;
}