任意门：
2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MBSubmit: 10095 Solved: 4222[][][]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
解题思路：
单点更新，xjb查询，莫队或者分块。
但是莫队需要离线，这里需要修改，怎么办呢？
引入第三个参数记录时间，根据时间点的不同更新答案。
AC code：
1 #include2 #define INF 0x3f3f3f3f 3 #define LL long long 4 using namespace std; 5 const int MAXN = 1e4+10; 6 const int MAXM = 1e6+10; 7 int N, M; 8 int h[MAXN], num[MAXN]; 9 int ans[MAXN], sum[MAXM]; 10 struct Query 11 { 12 int l, r, id, t; 13 }Q[MAXN]; 14 15 struct Time 16 { 17 int ip, co, lt; 18 }t[MAXN]; 19 int last[MAXN]; 20 21 bool cmp(Query a, Query b) 22 { 23 if(h[a.l] != h[b.l]) return h[a.l] < h[b.l]; 24 else{ 25 if(h[a.r] != h[b.r]) return h[a.r] < h[b.r]; 26 else return a.t < b.t; 27 } 28 } 29 30 int update(int tt, int L, int R, int no) 31 { 32 int res = 0; 33 int x = t[tt].ip, val = t[tt].co, lst = t[tt].lt; 34 if(t[tt].ip >= L && t[tt].ip <= R){ 35 if(sum[num[x]] == 1) res--; 36 sum[num[x]]--; 37 if(no == 1){ 38 if(sum[val] == 0) res++; 39 sum[val]++; 40 } 41 else if(no == -1){ 42 if(sum[lst] == 0) res++; 43 sum[lst]++; 44 } 45 } 46 if(no == 1) num[x] = val; 47 else if(no == -1) num[x] = lst; 48 return res; 49 } 50 51 int add(int x, int val) 52 { 53 int res = 0; 54 if(val == 1 && sum[num[x]] == 0) res++; 55 if(val == -1 && sum[num[x]] == 1) res--; 56 sum[num[x]]+=val; 57 return res; 58 } 59 60 int main() 61 { 62 scanf("%d %d", &N, &M); 63 for(int i = 1; i <= N; i++){ 64 scanf("%d", &num[i]); 65 last[i] = num[i]; 66 } 67 int lim = pow(N, (double)2/3); 68 for(int i = 1; i <= N; i++) h[i] = (i-1)/lim+1; 69 int cnt = 0, Tcnt = 0; 70 char com[5]; 71 for(int i = 1; i <= M; i++){ 72 scanf("%s", com); 73 if(com[0] == 'Q'){ 74 cnt++; 75 scanf("%d %d", &Q[cnt].l, &Q[cnt].r); 76 Q[cnt].t = Tcnt; 77 Q[cnt].id = cnt; 78 } 79 else{ 80 Tcnt++; 81 scanf("%d %d", &t[Tcnt].ip, &t[Tcnt].co); 82 t[Tcnt].lt = last[t[Tcnt].ip]; 83 last[t[Tcnt].ip] = t[Tcnt].co; 84 //printf("%d %d\n", t[Tcnt].co, t[Tcnt].lt); 85 } 86 } 87 sort(Q+1, Q+1+cnt, cmp); 88 89 int L = 1, R = 0, T = 0, cur = 0; 90 for(int i = 1; i <= cnt; i++){ 91 while(T < Q[i].t) cur+=update(++T, L, R, 1); 92 while(T > Q[i].t) cur+=update(T--, L, R, -1); 93 while(L < Q[i].l) cur+=add(L++, -1); 94 while(L > Q[i].l) cur+=add(--L, 1); 95 while(R < Q[i].r) cur+=add(++R, 1); 96 while(R > Q[i].r) cur+=add(R--, -1); 97 ans[Q[i].id] = cur; 98 } 99 100 for(int i = 1; i <= cnt; i++){101 printf("%d\n", ans[i]);102 }103 104 return 0;105 106 }