```cpp
#include <cstdio>
#include <algorithm>
#include <cmath>
using std::sort;
const int MAXN =1.5e5+50;
/*------------------------------莫队------------------------------*/
int l, r, t;
int col[MAXN], cntcol[MAXN];
bool vis[MAXN], nvist[MAXN];
int id[MAXN], record[2][MAXN], totc, totq;
struct query{
int l, r, t, ord, chunkl, chunkr;
}q[MAXN];
int cmp(query a, query b){
if(a.chunkl == b.chunkl){
if(a.chunkr == b.chunkr) return (a.chunkr&1) ? a.t < b.t : a.t > b.t;
else return (a.chunkl&1) ? a.r < b.r : a.r > b.r;
}
else return a.l < b.l;
}
int ANS;
/*用了一个没减少多少代码量还难懂的 trick(*/
inline void mov(int pos){
if(vis[pos] ^=1){ if(++cntcol[col[pos]] == 1) ++ANS; }
else if(--cntcol[col[pos]] == 0) --ANS;
}
inline void movt(int Time){
nvist[Time] ^=1;
//if(nvist[post] == 1) nvist[post] =0;
//else nvist[post] =1;
//printf("%d[%d]\n", nvist[post], post);
bool fl =nvist[Time];
int pos =id[Time];
col[pos] =record[!fl][Time];
if(pos >= l && pos < r){
if(--cntcol[record[fl][Time]] == 0) --ANS;
if(++cntcol[record[!fl][Time]] == 1) ++ANS;
}
}
/*------------------------------Main------------------------------*/
int ans[MAXN];
inline int read(){
int x =0; char c =getchar();
while(c < '0' || c > '9') c =getchar();
while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (48^c), c =getchar();
return x;
}
int main(){
//freopen("P1903_1.in", "r", stdin);
//freopen("P1903_1.out", "w", stdout);
int n =read(), m =read();
for(int i =0; i < n; ++i) col[i] =read();
for(int i =0; i < m; ++i){
char s[10]; scanf("%s", s);
int x =read()-1, y =read()-1;
if(s[0] == 'R') record[0][totc] =col[x], record[1][totc] =col[x] =y+1/*!*/, id[totc] =x, ++totc;
else q[totq].l =x, q[totq].r =y, q[totq].t =totc, q[totq].ord =totq, ++totq;
}
int S =pow(n, 2.0/3);
for(int i =0; i < totq; ++i) q[i].chunkl =q[i].l/S+1, q[i].chunkr =q[i].r/S+1;
sort(q, q+totq, cmp);
l =0, r =0, t =totc;
for(int i =0; i < totq; ++i){
query nw =q[i];
while(l < nw.l) mov(l++);
while(l > nw.l) mov(--l);
while(r < nw.r+1) mov(r++);
while(r > nw.r+1) mov(--r);
while(t < nw.t) movt(t++);
while(t > nw.t) movt(--t);
ans[nw.ord] =ANS;
}
for(int i =0; i < totq; ++i) printf("%d\n", ans[i]);
}
```
by Piwry @ 2020-05-26 18:39:06
棒,发完贴我就找到了((((
颜色最大会有 $10^6$ ,n 那个`MAXN`不够大
就这破东西调了我几小时
by Piwry @ 2020-05-26 18:42:25
![(((((((((((((((((((((((((((((((((((((((((((((((((((((((W***D](https://cdn.luogu.com.cn/upload/image_hosting/g2cv97bv.png)
by Piwry @ 2020-05-26 18:43:00
@[Piwry](/user/105254) /kk
by Limit @ 2020-05-26 19:31:35
谢谢大佬,没您这个帖子我就真的改不出来了QAQ
by Сontіnuе @ 2021-02-25 16:23:27