2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MB
Submit: 6286 Solved: 2489
[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
Q
Q
R
Q
Q
Sample Output
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
2016.3.2新加数据两组by Nano_Ape
分析：
总时限6s。咳咳，卡着5.4秒过的，已经不想去翻我是rank多少了，估计垫底了。
我的做法是莫队，对于每两次颜色修改间的所有询问做一次莫队，最多做1000次，但做1000次每次莫队的区间肯定很小，均摊是nsqrt（n）的。。再带个1000的常数（滑稽）
话说我是不是应该去看下正解。。。还是啥的，万一正解就是莫队呢（滑稽）。
AC代码：
# include <iostream>
# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>
using namespace std;
const int N = 1e4 + 1e3 + ;
const int M = 1e6 + ;
int block[N],sum[N],number[M],tot,n,m,a[N],ans[N],cnt,cntt,num,qaq;
struct per{
int l,r,id;
bool operator <(const per & other)const{
if(block[l] == block[other.l])return r < other.r;
return block[l] < block[other.l];
}
}q[N];
char str[];
void updata(int pos,int d){
if(!sum[number[a[pos]]])num++;
sum[number[a[pos]]] += d;
if(!sum[number[a[pos]]])num--;
}
void Modui(int k){
memset(sum,,sizeof sum);
int L = ,R = ;num = ;
sort(q,q + k);
for(int i = ;i < k;i++){
while(R < q[i].r)R++,updata(R,);
while(R > q[i].r)updata(R,-),R--;
while(L < q[i].l)updata(L,-),L++;
while(L > q[i].l)L--,updata(L,);
ans[q[i].id] = num;
}
}
int main(){
scanf("%d %d",&n,&m);tot = sqrt(n);
for(int i = ;i <= n;i++){
scanf("%d",&a[i]);block[i] = i / tot + ;
if(!number[a[i]])number[a[i]] = ++qaq;
}
int x,y;
for(int i = ;i <= m;i++){
scanf("%s",str);
if(str[] == 'R'){
scanf("%d %d",&x,&y);
Modui(cntt);a[x] = y;cntt = ;if(!number[a[x]])number[a[x]] = ++qaq;
}else {
scanf("%d %d",&q[cntt].l,&q[cntt].r);
q[cntt++].id = ++cnt;
}
}
Modui(cntt);
for(int i = ;i <= cnt;i++){
printf("%d\n",ans[i]);
}
}