Rockdu's Blog

题目描述

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：

1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。

2、 R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入输出格式

输入格式：

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。

第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式：

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

输入输出样例

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

4
4
3
4

说明

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

来源：bzoj2120

本题数据为洛谷自造数据，使用CYaRon耗时5分钟完成数据制作。

带修改莫队，把二维变成三维，我们把时间轴也计入维度就好了。有点难调，要注意边界。

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 5e4 + 5, maxc = 2e6 + 5, Bsize = 100;
struct Query {
	int l, r, t, id;
}qs[maxn];
char s[20];
int n, m, color[maxn], cnt[maxc], qcnt, a, b, x, y, h, now, tmp;
int ei[maxn], en[maxn], ans[maxn];
bool cmp(const Query & a, const Query & b) {
	if(a.l / Bsize != b.l / Bsize) return a.l < b.l;
	if(a.r / Bsize != b.r / Bsize) return a.r < b.r;
	return a.t < b.t;
}
int main() {
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= n; ++i)
		scanf("%d", &color[i]);
	for(register int i = 1; i <= m; ++i) {
		scanf("%s%d%d", s, &a, &b);
		if(s[0] == 'Q') qs[++qcnt] = (Query) {a, b, i, qcnt};
		else if(s[0] == 'R') ei[i] = a, en[i] = b;
	}
	sort(qs + 1, qs + qcnt + 1, cmp);
	now = x = y = 1, ++cnt[color[1]];
	for(register int i = 1; i <= qcnt; ++i) {
		while(y < qs[i].r) now += !cnt[color[y + 1]], ++cnt[color[y + 1]], ++y;
		while(y > qs[i].r) --cnt[color[y]], now -= !cnt[color[y]], --y;
		while(x < qs[i].l) --cnt[color[x]], now -= !cnt[color[x]], ++x;
		while(x > qs[i].l) now += !cnt[color[x - 1]], ++cnt[color[x - 1]], --x;
		while(h < qs[i].t) {
			++h;
			if(ei[h]) {
				if(ei[h] >= x && ei[h] <= y) {
					now -= !--cnt[color[ei[h]]];
					now += !cnt[en[h]]++;
				}
				swap(color[ei[h]], en[h]);
			}
		}
		while(h > qs[i].t) {
			if(ei[h]) {
				if(ei[h] >= x && ei[h] <= y) {
					now -= !--cnt[color[ei[h]]];
					now += !cnt[en[h]]++;
				}
				swap(color[ei[h]], en[h]);
			}
			--h;
		}
		ans[qs[i].id] = now;
	}
	for(register int i = 1; i <= qcnt; ++i) printf("%d\n", ans[i]);
	return 0;
}