洛谷P1903 数颜色 （带修莫队）

题目链接：https://www.luogu.com.cn/problem/P1903

带修莫队在莫队基础上增加一个时间维即可

注意排序的时候右端点也要按块排序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 150010;

int n, m, t, len, cnt1, cnt2;
int a[maxn], c[maxn * 10], blo[maxn], la[maxn], res[maxn];
int ql = 0, qr = 0, tim = 0, ans = 0;

struct Mo{
	int l, r, t;
	int la;
}mo[maxn];

struct Query{
	int l, r, t, id;
	int ans;
}q[maxn];

inline bool cmp(Query a, Query b){
	if(blo[a.l] == blo[b.l]){
		if(blo[a.r] == blo[b.r]) return a.t < b.t;
		return blo[a.r] < blo[b.r];
	}
	return blo[a.l] < blo[b.l];
}

inline void change(int x, int col){
	if(ql <= x && x <= qr){
		--c[a[x]];
		if(!c[a[x]]) --ans;
		a[x] = col;
		++c[col];
		if(c[col] == 1) ++ans;
	} else{
		a[x] = col;
	}
}

inline void add(int x){
	if(c[a[x]] == 0) ++ans;
	++c[a[x]];
}

inline void del(int x){
	--c[a[x]];
	if(c[a[x]] == 0) --ans;
}

inline bool cmp_id(Query a, Query b){
	return a.id < b.id;
}

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

int main(){
	n = read(), m = read();
	t = pow(n, 0.6666667);
	for(int i = 1 ; i <= n ; ++i) {
		a[i] = read();
		la[i] = a[i];
		blo[i] = (i - 1) / t + 1;
	}
	char s[10];
	int l, r;
	for(int i = 1 ; i <= m ; ++i){
		scanf("%s", s);
		if(s[0] == 'Q'){
			l = read(), r = read();
			q[++cnt1].l = l, q[cnt1].r = r;
			q[cnt1].t = cnt2, q[cnt1].id = cnt1;
		} else{
			l = read(), r = read();
			mo[++cnt2].l = l, mo[cnt2].r = r;
			mo[cnt2].la = la[mo[cnt2].l];
			la[l] = r;
		}
	}
	
	sort(q + 1, q + 1 + cnt1, cmp);
	
//	for(int i = 1 ; i <= cnt1 ; ++i){
//		printf("%d %d
", q[i].l, q[i].r);
//	}
	
	for(int i = 1 ; i <= cnt1 ; ++i){
		while(tim < q[i].t){
			++tim;
			change(mo[tim].l, mo[tim].r);
		}
		while(tim > q[i].t){
			change(mo[tim].l, mo[tim].la);
			tim--;
		}
		
		while(ql < q[i].l) del(ql++);
		while(ql > q[i].l) add(--ql);
		while(qr < q[i].r) add(++qr);
		while(qr > q[i].r) del(qr--);
		
		res[q[i].id] = ans;
	}
	
	for(int i = 1 ; i <= cnt1 ; ++i) printf("%d
", res[i]);
	
	return 0;
}