题解

练习一下带修改莫队

先按照左端点的块排序，再按照右端点的块排序，然后按照时间排序

每个修改操作存一下修改前这个位置的值就可以逆序操作了

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define pdi pair
      
       #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')#define eps 1e-8#define mo 974711#define MAXN 10005//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
       
        void read(T &res) {    res = 0;char c = getchar();T f = 1;    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 + c - '0';    c = getchar();    }    res *= f;}template
        
         void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {    out(x / 10);    }    putchar('0' + x % 10);}int N,M,S;int c[1000005],res,ans[MAXN],op[MAXN],col[2][MAXN],tot,id[MAXN],a[MAXN],tmp[MAXN];int p,q,x;struct qry_node {    int id,l,r,bl,br;    friend bool operator <  (const qry_node &a,const qry_node &b) {    if(a.bl != b.bl) return a.bl < b.bl;    if(a.br != b.br) return a.br < b.br;    return a.id < b.id;    } }qry[MAXN];void update_pos(int pos,int v) {    if(c[pos] == 0 && c[pos] + v == 1) ++res;    else if(c[pos] == 1 && c[pos] + v == 0) --res;    c[pos] += v;}void Change(int t) {    if(t > x) {    for(int i = x + 1 ; i <= t ; ++i) {        if(op[i]) {        if(op[i] <= q && op[i] >= p) {            update_pos(a[op[i]],-1);            update_pos(col[1][i],1);        }        a[op[i]] = col[1][i];        }    }    }    else {    for(int i = x ; i > t ; --i) {        if(op[i]) {        if(op[i] <= q && op[i] >= p) {            update_pos(a[op[i]],-1);            update_pos(col[0][i],1);        }        a[op[i]] = col[0][i];        }    }    }    x = t;}void Move(int l,int r) {    while(q < r) {update_pos(a[++q],1);}    while(p > l) {update_pos(a[--p],1);}    while(q > r) {update_pos(a[q--],-1);}    while(p < l) {update_pos(a[p++],-1);}}void Solve() {    read(N);read(M);    S = pow(N,2.0 / 3.0);    int h = 0;    for(int i = 1 ; i <= N ; ++i) {read(a[i]);tmp[i] = a[i];}    for(int i = 1 ; i <= N ; i += S) {    int r = min(i + S - 1,N);    ++h;    for(int j = i ; j <= r ; ++j) {        id[j] = h;    }    }    char s[5];    int l,r;    for(int i = 1 ; i <= M ; ++i) {    scanf("%s",s + 1);    read(l);read(r);    if(s[1] == 'Q') {        qry[++tot] = (qry_node){i,l,r,id[l],id[r]};    }    else {        op[i] = l;col[1][i] = r;col[0][i] = tmp[l];        tmp[l] = r;    }    }    sort(qry + 1,qry + tot + 1);    x = 0,p = 1,q = 0;    for(int i = 1 ; i <= tot ; ++i) {    Change(qry[i].id);    Move(qry[i].l,qry[i].r);    ans[qry[i].id] = res;    }    for(int i = 1 ; i <= M ; ++i) {    if(!op[i]) {        out(ans[i]);enter;    }    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();    return 0;}