爱悠闲 > BZOJ 2120 数颜色 暴力

BZOJ 2120 数颜色 暴力

分类: BZOJ  |  标签: BZOJ,BZOJ2120,暴力  |  作者: popoqqq 相关  |  发布日期 : 2014-10-02  |  热度 : 160°

题目大意:给定一个序列,提供两种操作:

1.查询[l,r]区间内有多少不同的数字

2.单点修改

n,m<=1W

树套树?主席树?啥都不需要!这题暴力才2s,不要想复杂了!妥妥水过!

数字离散化一下!标记用时间戳代替!675B秒切!不是一般爽!

。。。好吧如果觉得这样没啥意思可以试试树状数组套bitset 应该会快一些

总之50%达成 假期进度:66.7% 死ね

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 10010
using namespace std;
int n,m,a[M],map[1001001],tot;
int f[M+1000],T,ans;
int main()
{
	int i,j,x,y;
	char p[10];
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if(!map[x])
			map[x]=++tot;
		a[i]=map[x];
	}
	for(i=1;i<=m;i++)
	{
		scanf("%s%d%d",p,&x,&y);
		if(p[0]=='R')
		{
			if(!map[y])
				map[y]=++tot;
			a[x]=map[y];
		}
		else
		{
			ans=0;++T;
			for(j=x;j<=y;j++)
				if(f[ a[j] ]!=T)
					++ans,f[ a[j] ]=T;
			printf("%d\n",ans);
		}
	}
}