luogu1903 【模板】分块/带修改莫队（数颜色）

莫队算法模板

推荐阅读这篇博客

#include <algorithm>

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

int n, m, bse, blc[10005], a[10005], qCnt, cCnt, qwq[10005], ans=0;

int cnt[10005];

char ss[5];

struct Query{

	int xxx, yyy, pre, idx;

}q[10005];

struct Change{

	int pos, val;

}c[1005];

bool cmp(Query u, Query v){

	if(blc[u.xxx]==blc[v.xxx])	return u.yyy<v.yyy;

	else	return blc[u.xxx]<blc[v.xxx];

}

void add(int val){

	if(++cnt[val]==1)	ans++;

}

void del(int val){

	if(--cnt[val]==0)	ans--;

}

void work(int now, int i){

	if(c[now].pos>=q[i].xxx && c[now].pos<=q[i].yyy){

		del(a[c[now].pos]);

		add(c[now].val);

	}

	swap(c[now].val, a[c[now].pos]);

}

void md(){

	int l=1, r=0, now=0;

	for(int i=1; i<=qCnt; i++){

		while(l<q[i].xxx)	del(a[l++]);

		while(l>q[i].xxx)	add(a[--l]);

		while(r<q[i].yyy)	add(a[++r]);

		while(r>q[i].yyy)	del(a[r--]);

		while(now<q[i].pre)	work(++now, i);

		while(now>q[i].pre)	work(now--, i);

		qwq[q[i].idx] = ans;

	}

}

int main(){

	cin>>n>>m;

	bse = sqrt(n);

	for(int i=1; i<=n; i++){

		scanf("%d", &a[i]);

		blc[i] = (i - 1) / bse + 1;

	}

	while(m--){

		scanf("%s", ss);

		if(ss[0]=='Q'){

			qCnt++;

			scanf("%d %d", &q[qCnt].xxx, &q[qCnt].yyy);

			q[qCnt].pre = cCnt;

			q[qCnt].idx = qCnt;

		}

		else{

			cCnt++;

			scanf("%d %d", &c[cCnt].pos, &c[cCnt].val);

		}

	}

	sort(q+1, q+1+qCnt, cmp);

	md();

	for(int i=1; i<=qCnt; i++)

		printf("%d\n", qwq[i]);

	return 0;

}

巴特西

luogu1903 【模板】分块/带修改莫队（数颜色）

最新文章

热门文章