题目链接：https://vjudge.net/problem/HYSBZ-2120
2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MB
Submit: 6898 Solved: 2781
[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
Sample Output
4
4
3
4
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
2016.3.2新加数据两组by Nano_Ape
题意：
查询区间颜色种数，且带修改。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 1e6+; int val[MAXN], tmp[MAXN];
int block, sum[MAXN], Ans[MAXN];
int num1, num2; struct Node
{
//index记录查询的编号， t记录查询时执行了多少步修改
int l, r, index, t;
bool operator<(const Node&x) const{
if(l/block!=x.l/block) return l/block<x.l/block;
else if(r!=x.r) return r<x.r;
else return t<x.t;
}
}q[MAXN]; struct
{
//preCol记录修改前pos位的颜色， nowCol记录修改后pos位的颜色
int pos, nowCol, preCol;
}op[MAXN]; int L, R, T, ans;
void modifyTime(int pos, int col)
{
if(L<=pos && pos<=R)
{
sum[val[pos]]--;
if(sum[val[pos]]==) ans--;
val[pos] = col;
sum[val[pos]]++;
if(sum[val[pos]]==) ans++;
}
else val[pos] = col;
} void add(int pos)
{
sum[val[pos]]++;
if(sum[val[pos]]==) ans++;
} void del(int pos)
{
sum[val[pos]]--;
if(sum[val[pos]]==) ans--;
} void work()
{
L = , R = , T = , ans = ;
memset(sum, , sizeof(sum));
for(int i = ; i<=num1; i++)
{
while(T<q[i].t) T++, modifyTime(op[T].pos, op[T].nowCol);
while(T>q[i].t) modifyTime(op[T].pos, op[T].preCol), T--;
while(L<q[i].l) del(L), L++;
while(L>q[i].l) L--, add(L);
while(R<q[i].r) R++, add(R);
while(R>q[i].r) del(R), R--;
Ans[q[i].index] = ans;
}
} int main()
{
int n, m;
while(scanf("%d%d", &n,&m)!=EOF)
{
block = sqrt(n);
for(int i = ; i<=n; i++)
{
scanf("%d", &val[i]);
tmp[i] = val[i];
} num1 = num2 = ;
for(int i = ; i<=m; i++)
{
char s[]; int x, y;
scanf("%s%d%d", s, &x, &y);
if(s[]=='Q')
{
q[++num1].index = num1;
q[num1].t = num2;
q[num1].l = x;
q[num1].r = y;
}
else //tmp用于记录动态修改时每个位置上的颜色
{
op[++num2].pos = x;
op[num2].nowCol = y;
op[num2].preCol = tmp[x];
tmp[x] = y;
}
} sort(q+, q++num1);
work();
for(int i = ; i<=num1; i++)
printf("%d\n", Ans[i]);
}
}
直接暴力也行：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 1e6+; int val[MAXN], tmp[MAXN];
int block, sum[MAXN], Ans[MAXN];
int num1, num2; struct Node
{
//index记录查询的编号， t记录查询时执行了多少步修改
int l, r, index, t;
}q[MAXN]; struct
{
//preCol记录修改前pos位的颜色， nowCol记录修改后pos位的颜色
int pos, nowCol, preCol;
}op[MAXN]; int L, R, T, ans;
void modifyTime(int pos, int col)
{
if(L<=pos && pos<=R)
{
sum[val[pos]]--;
if(sum[val[pos]]==) ans--;
val[pos] = col;
sum[val[pos]]++;
if(sum[val[pos]]==) ans++;
}
else val[pos] = col;
} void add(int pos)
{
sum[val[pos]]++;
if(sum[val[pos]]==) ans++;
} void del(int pos)
{
sum[val[pos]]--;
if(sum[val[pos]]==) ans--;
} void work()
{
L = , R = , T = , ans = ;
memset(sum, , sizeof(sum));
for(int i = ; i<=num1; i++)
{
while(T<q[i].t) T++, modifyTime(op[T].pos, op[T].nowCol);
while(T>q[i].t) modifyTime(op[T].pos, op[T].preCol), T--;
while(L<q[i].l) del(L), L++;
while(L>q[i].l) L--, add(L);
while(R<q[i].r) R++, add(R);
while(R>q[i].r) del(R), R--;
Ans[q[i].index] = ans;
}
} int main()
{
int n, m;
while(scanf("%d%d", &n,&m)!=EOF)
{
for(int i = ; i<=n; i++)
{
scanf("%d", &val[i]);
tmp[i] = val[i];
} num1 = num2 = ;
for(int i = ; i<=m; i++)
{
char s[]; int x, y;
scanf("%s%d%d", s, &x, &y);
if(s[]=='Q')
{
q[++num1].index = num1;
q[num1].t = num2;
q[num1].l = x;
q[num1].r = y;
}
else //tmp用于记录动态修改时每个位置上的颜色
{
op[++num2].pos = x;
op[num2].nowCol = y;
op[num2].preCol = tmp[x];
tmp[x] = y;
}
} work();
for(int i = ; i<=num1; i++)
printf("%d\n", Ans[i]);
}
}
