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。
【分析】
好吧，正解应该是树套树，但是...分块可以做....
我的方法很暴力...改了暴力重建..居然还可以过。。
/*
宋代
辛弃疾
青玉案·元夕
东风夜放花千树。更吹落、星如雨。宝马雕车香满路。凤箫声动，玉壶光转，一夜鱼龙舞。
蛾儿雪柳黄金缕。笑语盈盈暗香去。众里寻他千百度。蓦然回首，那人却在，灯火阑珊处。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <utility>
#include <iomanip>
#include <string>
#include <cmath>
#include <queue>
#include <assert.h>
#include <map>
#include <ctime>
#include <cstdlib>
#include <stack>
#include <set>
#define LOCAL
const int INF = ;
const int MAXN = + ;
const int maxnode = * + * ;
const int MAXM= + ;
using namespace std;
int tot;
int n, q, block_size;
int data[MAXN];
int belong[MAXN], block[MAXN];
int t[MAXN],last[MAXM]; //寻找第x块内有多少个比v要小的
int find(int x, int v){
int l = (x - ) * block_size + , r = min(x * block_size, n);
int first = l;
while (l <= r){
int mid = (l + r) >> ;
if (block[mid] < v) l = mid + ;
else r = mid - ;
}
return l - first;
}
int query(int l, int r){
int ans = ;
if (belong[l] == belong[r]){
for (int i = l; i <= r; i++) if (t[i] < l) ans++;
}else {
for (int i = l; i <= block_size * belong[l]; i++) if (t[i] < l) ans++;
for (int i = block_size * (belong[r] - ) + ; i <= r; i++) if (t[i] < l) ans++;
}
for (int i = belong[l] + ; i < belong[r]; i++) ans += find(i, l);
return ans;
}
//处理块
void build(int x){
int l = (x - ) * block_size + , r = min(x * block_size, n);
for (int i = l; i <= r; i++) block[i] = t[i];
sort(block + l, block + r + );//对一个块的上一次出现的颜色进行排序
}
//将x的颜色改变为v
void change(int x, int v){
for (int i = ; i <= n; i++) last[data[i]] = ;//暴力重构
data[x] = v;
for (int i = ; i <= n; i++){
int tmp = t[i];
t[i] = last[data[i]];
if (tmp != t[i]) build(belong[i]);
last[data[i]] = i;
}
} void init(){
scanf("%d%d", &n, &q);
for (int i = ; i <= n; i++) scanf("%d", &data[i]);
block_size = (int)(sqrt(n * 1.0));
//tot记录总共块的个数
tot = n / block_size;
if (n % block_size) tot++; for (int i = ; i <= n; i++){
//链表式插入
t[i] = last[data[i]];
last[data[i]] = i;
belong[i] = (i - ) / block_size + ;
}
for (int i = ; i <= tot; i++){ build(i);
}
}
void work(){
for (int i = ; i <= q; i++){
char str[];
scanf("%s", str);
if (str[] == 'Q'){
int l, r;
scanf("%d%d", &l, &r);
printf("%d\n", query(l, r));
}else{
int l, x;
scanf("%d%d", &l, &x);
change(l, x);
}
}
} int main(){ init();
work();
return ;
}