2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MB
Submit: 2645 Solved: 1039
[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
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
4
3
4
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
2016.3.2新加数据两组by Nano_Ape
Source
题解：
好像可以用bitset。。。
#include<bits/stdc++.h>
using namespace std;
int a[];
bitset<> vis;
int main()
{
int n,m,i,l,r,sum,j;
char fh;
scanf("%d %d",&n,&m);
for(i=;i<=n;i++)scanf("%d",&a[i]);
for(i=;i<=m;i++)
{
scanf("\n%c %d %d",&fh,&l,&r);
if(fh=='Q')
{
vis.reset();
sum=;
for(j=l;j<=r;j++)if(vis[a[j]]==){sum++;vis[a[j]]=;}
printf("%d\n",sum);
}
else
{
a[l]=r;
}
}
return ;
}
直接用莫队也可以。。。
好像重题了（见Bzoj2453）>_<
好像和 HH的项链 几乎一样。。。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 10010
#define MAXM 1000010
int n,a[MAXN],last[MAXN],pre[MAXM],block,pos[MAXN],h[MAXN];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
void cl(int k)
{
int l=(k-)*block+,r=min(n,k*block),i;
for(i=l;i<=r;i++)a[i]=last[i];
sort(a+l,a+r+);
}
void Change(int x,int c)
{
int i,t;
for(i=;i<=n;i++)pre[h[i]]=;
h[x]=c;
for(i=;i<=n;i++)
{
t=last[i];
last[i]=pre[h[i]];
if(t!=last[i])cl(pos[i]);
pre[h[i]]=i;
}
}
int Find(int k,int ll)
{
int l=(k-)*block+,r=min(k*block,n),mid,t=;
while(l<=r)
{
mid=(l+r)/;
if(a[mid]>=ll)r=mid-;
else if(a[mid]<ll)t=mid,l=mid+;
}
if(t==)return ;
else return t-((k-)*block+)+;
}
int Query(int l,int r)
{
int ans=,i;
if(pos[l]==pos[r])
{
for(i=l;i<=r;i++)if(last[i]<l)ans++;
}
else
{
for(i=l;i<=pos[l]*block;i++)if(last[i]<l)ans++;
for(i=(pos[r]-)*block+;i<=r;i++)if(last[i]<l)ans++;
for(i=pos[l]+;i<=pos[r]-;i++)ans+=Find(i,l);
}
return ans;
}
int main()
{
int M,i,m,s1,s2;
char fh[];
n=read();M=read();
block=(int)sqrt(n);
memset(last,,sizeof(last));
memset(pre,,sizeof(pre));
for(i=;i<=n;i++)
{
h[i]=read();
last[i]=pre[h[i]];
pre[h[i]]=i;
pos[i]=(i-)/block+;
}
if(block*block==n)m=n/block;
else m=n/block+;
for(i=;i<=m;i++)cl(i);
for(i=;i<=M;i++)
{
scanf("\n%s",fh);s1=read();s2=read();
if(fh[]=='Q')
{
printf("%d\n",Query(s1,s2));
}
else Change(s1,s2);
}
return ;
}