题目

有n个数编号从0→n-1,两种操作：

Q L R:询问编号为L→R-1的数中共有多少种不同的数

M X Y：将编号为X的数改为Y

共有m个操作

分析

既然是单点修改，查询，我们考虑一下分块。

首先，定义\(next_{i}\)表示，在\(i\)之后的第一个与编号为\(i\)的数相同的数的位置。

接着，我们把\(i\)向\(next_{i}\)连一条边。

那么就会发现，当把边处理好后，查询操作就迎刃而解了；

查询操作

假设现在要查询\([x，y]\)，

其中next，以及它们的连边的情况是：

发现，编号为\(a\)的数和编号为\(next_a\)的数的数以及编号为\(b\)的数和编号为\(next_b\)的数的数都重复了。

那么就要减去重复的，

而编号为\(next_c\)的数并不在\([x，y]\),所以并不需要减去。

我们得出一个结论：\(\color{red}{当next_i<=y时，编号为i的数一定有重复，所以我们就只记录最后一个，即next_i>y的那一个}\)

那如何处理呢？

对于不是整块的部分，暴力处理。时间复杂度\(O(2\sqrt{n})\)。

对于整块的部分，把整块按\(next_{i}\)排序，二分求答案。

修改操作

我们再定义\(last_{i}\)表示，在\(i\)之前的第一个与编号为\(i\)的数相同的数的位置。

再把\(i\)向\(last_{i}\)连一条边；

假设我们修改位置x，

那么，因为x修改成别的值，所以\(next[last[x]]\)就要就修成\(next[x]\)，\(last[next[x]]\)就要就改成\(last[x]\)

接着，发现，这样\(next[last[x]]\)改变了，于是，重新把\(last[x]\)所在的块排序。

然后，就要处理位置x新的\(last和next\)。

假设x所在的块的开头和结尾是s和t。

处理\(last\)：

我们先暴力查看x-1~s的位置中是否出现过y，如果有，修改\(last[x]\)以及\(next[last[x]]\)。

否则查看前面的块，

再定义\(sum[i][j]\)表示，在第i个块中，j这个数出现过多少次。

找到了，就修改就可以了。

处理\(next\)类似。

记住，如果某个位置的\(next\)修改了，就将这个位置所在的块排个序。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=50005;

using namespace std;

int a[N*2],n,m,ans,next[N*2],last[N*2],part[N][2],size,as[N*2],pos[N*2],stead[1000005],sum[250][N*2],tot,color[N*2],num;

bool cmp(int x,int y)

{

	return next[x]<next[y];

}

int preblock()

{

	size=sqrt(n);

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

	{

		part[++tot][0]=i;

		if(i+size-1>n)

			part[tot][1]=n;

				else

					part[tot][1]=i+size-1;

	}

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

		for(int j=part[i][0];j<=part[i][1];j++)

		{

			sum[i][stead[a[j]]]++;

			pos[j]=i;

		}

}

int prenexus()

{

	memset(color,0,sizeof(color));

	for(int i=0;i<=n;i++)

	{

		last[i]=color[stead[a[i]]];

		color[stead[a[i]]]=i;

	}

	memset(color,0,sizeof(color));

	for(int i=n;i>=0;i--)

	{

		next[i]=color[stead[a[i]]];

		if(!next[i])

			next[i]=maxlongint;

		color[stead[a[i]]]=i;

	}

}

int so(int x)

{

	sort(as+part[x][0],as+part[x][1]+1,cmp);

}

int fs(int x,int y,int y1)

{

	for(int i=x;i<=y;i++)

		if(next[i]>y1)

			ans++;

}

int zt(int x,int y,int y1)

{

	int ll=x-1,rr=y;

	while(ll<rr-1)

	{

		int mid=(ll+rr)/2;

		if(next[as[mid]]<=y1) ll=mid;

			else rr=mid;

	}

	int q=0;

	if(next[as[rr]]<=y1) q=rr;

		else q=ll;

	ans+=y-x+1-(q-x+1);

}

int main()

{

	scanf("%d%d",&n,&m);

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

	{

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

		if(!stead[a[i]])

		{

			stead[a[i]]=++num;

		}

	}

	preblock();

	prenexus();

	for(int i=1;i<=n;i++) as[i]=i;

	for(int i=1;i<=tot;i++) so(i);

	for(int k=1;k<=m;k++)

	{

		char c=getchar();

		while(c!='Q' && c!='M') c=getchar();

		int x,y;

		scanf(" %d %d",&x,&y);

		x+=1;

		if(c=='Q')

		{

			ans=0;

			int l=pos[x],r=pos[y];

			if(l==r)

			{

				for(int i=x;i<=y;i++)

					if(next[i]>y) ans++;

					printf("%d\n",ans);

				continue;

			}

			if(x>part[l][0])

			{

				for(int i=x;i<=part[l][1];i++)

					if(next[i]>y) ans++;

				l++;

			}

			if(y<part[r][1])

			{

				for(int i=part[r][0];i<=y;i++)

					if(next[i]>y) ans++;

				r--;

			}

			for(int i=l;i<=r;i++)

				zt(part[i][0],part[i][1],y);

			printf("%d\n",ans);

		}

		else

		{

			bool q=true;

			if(!stead[y])

			{

				stead[y]=++num;

				q=false;

			}

			next[last[x]]=next[x];

			if(next[x]!=maxlongint)

				last[next[x]]=last[x];

			sum[pos[x]][stead[a[x]]]--;

			sum[pos[x]][stead[y]]++;

			so(pos[last[x]]);

			a[x]=y;

			if(!q)

			{

				last[x]=0;

				next[x]=maxlongint;

			}

			else

			{

				int p=0,p1=0;

				for(int i=x-1;i>=part[pos[x]][0];i--)

					if(a[i]==y)

					{

						p=i;

						break;

					}

				if(!p)

				{

					for(int i=pos[x]-1;i>=1;i--)

					{

						if(sum[i][stead[y]])

						{

							for(int j=part[i][1];j>=part[i][0];j--)

								if(a[j]==y)

								{

									p=j;

									break;

								}

							break;

						}

					}

				}

				if(p)

				{

					last[x]=p;

					next[p]=x;

					so(pos[p]);

				}

				else

					last[x]=0;

				for(int i=x+1;i<=part[pos[x]][1];i++)

					if(a[i]==y)

					{

						p1=i;

						break;

					}

				if(!p1)

				{

					for(int i=pos[x]+1;i<=tot;i++)

					{

						if(sum[i][stead[y]])

						{

							for(int j=part[i][0];j<=part[i][1];j++)

								if(a[j]==y)

								{

									p1=j;

									break;

								}

							break;

						}

					}

				}

				if(p1)

				{

					next[x]=p1;

					last[p1]=x;

					so(pos[x]);

				}

				else

					next[x]=maxlongint;

			}

			so(pos[x]);

		}

	}

}

巴特西

Dynamic len

题目

分析

查询操作

修改操作

最新文章

热门文章