【题解】Luogu UVA12345 Dynamic len(set(a[L:R]))

原题传送门

这题要用动态莫队，我博客里有介绍

这道题和luogu P1903 [国家集训队]数颜色 / 维护队列差不多，解法就在上面那篇博客里qaq

主要的问题是如何排序？

排序有三个关键字：

1.左端点所在块数 2.右端点所在块数 3.在这次修改之前查询的次数

在写莫队模板后面还要加上修改操作

注意，序列是从0r-1

#include <bits/stdc++.h>

#define N 50005

using namespace std;

inline int read()

{

	register int x=0,f=1;register char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return x*f;

}

inline void write(register int x)

{

	if(!x)putchar('0');if(x<0)x=-x,putchar('-');

	static int sta[25];int tot=0;

	while(x)sta[tot++]=x%10,x/=10;

	while(tot)putchar(sta[--tot]+48);

}

struct change{

	int pos,pre,suf;

}ch[N];

struct query{

	int l,r,id,time,bll,blr;

}q[N];

int a[N],blocksize=0,num[1000001],ans[N];

inline bool cmp(register query a,register query b)

{

	return a.bll!=b.bll?a.bll<b.bll:(a.blr!=b.blr?a.blr<b.blr:a.time<b.time);

}

int main()

{

	int n=read(),m=read(),tota=0,totb=0;

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

		a[i]=read();

	for(register int i=1;i<=m;++i)

	{

		char cha=getchar();

		while(cha!='Q'&&cha!='M')

			cha=getchar();

		if(cha=='Q')

		{

			int l=read()+1,r=read();

			++tota;

			q[tota]=(query){l,r,tota,totb,0,0};

		}

		else

		{

			int pos=read()+1,x=read();

			++totb;

			ch[totb]=(change){pos,a[pos],x};

			a[pos]=x;

		}

	}

	blocksize=ceil(exp((log(n)+log(tota))/3));

	for(register int i=1;i<=tota;++i)

		q[i].bll=(q[i].l-1)/blocksize+1,q[i].blr=(q[i].r-1)/blocksize+1;

	for(register int i=totb;i>=1;--i)

		a[ch[i].pos]=ch[i].pre;

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

	int l=1,r=0,t=0,sum=0;

	for(register int i=1;i<=tota;++i)

	{

		int ll=q[i].l,rr=q[i].r,tt=q[i].time;

		while(ll<l)

			sum+=!num[a[--l]]++;

		while(ll>l)

			sum-=!--num[a[l++]];

		while(rr>r)

			sum+=!num[a[++r]]++;

		while(rr<r)

			sum-=!--num[a[r--]];

		while(t<tt)

		{

			int pos=ch[++t].pos;

			if(l<=pos&&pos<=r)

				sum-=!--num[a[pos]];

			a[pos]=ch[t].suf;

			if(l<=pos&&pos<=r)

				sum+=!num[a[pos]]++;

		}

		while(t>tt)

		{

			int pos=ch[t].pos;

			if(l<=pos&&pos<=r)

				sum-=!--num[a[pos]];

			a[pos]=ch[t--].pre;

			if(l<=pos&&pos<=r)

				sum+=!num[a[pos]]++;

		}

		ans[q[i].id]=sum;

	}

	for(register int i=1;i<=tota;++i)

		write(ans[i]),printf("\n");

	return 0;

}