BZOJ2120 数颜色 【带修改莫队】

时间：2020-11-25 08:15:47

2120: 数颜色

Time Limit: 6 Sec  Memory Limit: 259 MB

Submit: 6579  Solved: 2625

[Submit][Status][Discuss]

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。

Output

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

Sample Input

6 5

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

Sample Output

4

4

3

4

HINT

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

2016.3.2新加数据两组by Nano_Ape

第一次用带修改的莫队

实际就是记录下所有的修改，对于每个询问记录下该询问属于修改了几次时的询问

当到达一个询问时，若当前修改次数不符，就转移修改至当前询问所在修改

为了优化时间，我们按①块②右端点③修改次数   排序

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define Redge(u) for (int k = h[u]; k != -1; k = ed[k].nxt)

using namespace std;

const int maxn = 10005,maxm = 1000005,INF = 1000000000;

inline int RD(){

	int out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}

	return out * flag;

}

int co[maxn],N,M,T,nq = 0,nt = 0,ans[maxn],tot[maxm];

struct Que{int l,r,tim,b,id;}Q[maxn];

struct Cha{int pos,from,to;}C[maxn];

inline bool operator <(const Que& a,const Que& b){

	if (a.b != b.b) return a.b < b.b;

	else if (a.r != b.r) return a.r < b.r;

	return a.tim < b.tim;

}

void solve(){

	int t = nt,L = 0,R = 0,cnt = 0;

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

		while (t > Q[i].tim){

			if (C[t].pos >= L && C[t].pos <= R){

				if (!(--tot[C[t].to])) cnt--;

				if (!tot[C[t].from]++) cnt++;

			}

			co[C[t].pos] = C[t].from; t--;

		}

		while (t < Q[i].tim){

			t++;

			if (C[t].pos >= L && C[t].pos <= R){

				if (!(--tot[C[t].from])) cnt--;

				if (!tot[C[t].to]++) cnt++;

			}

			co[C[t].pos] = C[t].to;

		}

		while (L < Q[i].l){if (!(--tot[co[L++]])) cnt--;}

		while (L > Q[i].l){if (!tot[co[--L]]++) cnt++;}

		while (R < Q[i].r){if (!tot[co[++R]]++) cnt++;}

		while (R > Q[i].r){if (!(--tot[co[R--]])) cnt--;}

		ans[Q[i].id] = cnt;

	}

}

int main(){

	N = RD(); M = RD(); T = (int)sqrt(N); char cmd;

	REP(i,N) co[i] = RD();

	REP(i,M){

		cmd = getchar(); while (cmd != 'Q' && cmd != 'R') cmd = getchar();

		if (cmd == 'Q') Q[++nq].l = RD(),Q[nq].r = RD(),Q[nq].tim = nt,Q[nq].b = Q[nq].l / T,Q[nq].id = nq;

		else C[++nt].pos = RD(),C[nt].from = co[C[nt].pos],co[C[nt].pos] = C[nt].to = RD();

	}

	sort(Q + 1,Q + 1 + nq);

	solve();

	REP(i,nq) printf("%d\n",ans[i]);

	return 0;

}

相关文章