[数据结构与算法]洛谷-数颜色-(带修改莫队)

数颜色

题意：
就是给你n个彩色的笔，然后有两种操作，一种是查询l到r中有多少个颜色，一种是把a位置的颜色换成b颜色。

思考：
这种修改和查询的想了想线段树，但是发现没啥维护信息。要么去分块？但是我的分块掌握的也不怎么好。然后去想莫队，但是这个带修改，其实带修改的莫队也就能做一下单调修改的。node存的时候多存一个时间线tim。也就是处理到这个查询的时候，比如我已经修改了x次了，如果当前的全局变量now还不到x，那么就要去更新，如果超过x了也要减回来。对于这个，如果修改的操作是我查询的区间内，那么就修改，否则的话就交换一下就行了，为什么要交换，因为既然我now到这里了就代表我修改了，下次有人到这个点的时候那么就直接相当于修改了。

代码：

struct Node{
	int l,r,tim;
	int id;
}node[N];

int T,n,m,k;
int va[N];
PII vb[N];
int cnt1,cnt2;
int pos[N],cnt[N],siz;
int anw[N],now,ans;

bool cmp(Node A,Node B) //同时cmp也有了变化。
{
	if(pos[A.l]!=pos[B.l]) return pos[A.l]<pos[B.l];
	if(pos[A.r]!=pos[B.r]) return pos[A.r]<pos[B.r];
	return A.tim<B.tim;
}

void add(int x)
{
	cnt[va[x]]++;
	ans += (cnt[va[x]]==1);
}

void sub(int x)
{
	cnt[va[x]]--;
	ans -= (cnt[va[x]]==0);
}

void update(int x,int tim)
{
	if(vb[tim].fi>=node[x].l&&vb[tim].fi<=node[x].r) //如果在我的区间内
	{
		cnt[va[vb[tim].fi]]--;
		ans -= (cnt[va[vb[tim].fi]]==0);
		cnt[vb[tim].se]++;
		ans += (cnt[vb[tim].se]==1);
	}
	swap(va[vb[tim].fi],vb[tim].se); //如果不在也要修改，交换的意思呢就是如果下次now太大了，再变回来就是这个意思。
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>va[i];
	siz = pow(n,2.0/3.0);
	for(int i=1;i<=n;i++) pos[i] = i/siz;
	for(int i=1;i<=m;i++)
	{
		char op;
		int a,b;
		cin>>op>>a>>b;
		if(op=='Q') node[++cnt1] = {a,b,cnt2,cnt1};
		else vb[++cnt2] = {a,b};
	}
	sort(node+1,node+1+cnt1,cmp);
	int l = 1,r = 0;
	for(int i=1;i<=cnt1;i++)
	{
		while(l<node[i].l) sub(l++);
		while(l>node[i].l) add(--l);
		while(r<node[i].r) add(++r);
		while(r>node[i].r) sub(r--);
		while(now<node[i].tim) update(i,++now); //同理
		while(now>node[i].tim) update(i,now--);
		anw[node[i].id] = ans;
	}
	for(int i=1;i<=cnt1;i++) cout<<anw[i]<<"\n";
	return 0;
}

总结：
多多思考呀。