1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <vector>
using namespace std;

namespace fast_io {
    ...
}using namespace fast_io;

const int MAXN = 11000,MAX = 1100000;

int n,m,Q;
int col[MAXN],re_col[MAXN],re_pos[MAXN],cnum = 1;
int l = 0,r = 0,x = 0;

int num[MAX],ans = 0;

struct Query{
    int id,ql,qr,qx,ans;
    //运算符重载
    bool operator < (Query b)const{
        if(ql/Q != b.ql/Q)
            return ql/Q < b.ql/Q;
        if(qr/Q != b.qr/Q) 
            return qr/Q < b.qr/Q;
        return qx < b.qx;
    }
};

bool cmp(Query a,Query b){
    return a.id < b.id;
}

vector<Query> query;

void init(){
    read(n),read(m);Q = sqrt(n*2);
    for(int i = 1;i<=n;i++)
        read(col[i]);
    for(int i = 1;i<=m;i++){
        char op[10];int a,b;
        read(op);read(a),read(b);
        if(op[0] == 'Q'){
            Query w;w.ql = a,w.qr = b,w.qx = cnum-1;
            w.id = i;query.push_back(w);
        }
        else if(op[0] == 'R'){
            re_pos[cnum] = a,re_col[cnum] = b;
            cnum++;
        }
    }
    sort(query.begin(),query.end());
}

//加入第pos个数并更新答案
void add(int pos){
    if(num[col[pos]]++ == 0)
        ans++;
}

//删去第pos个数并更新答案
void del(int pos){
    if(--num[col[pos]] == 0)
        ans--;
}

//进行第times次修改
void change(int times){
    if(l<=re_pos[times]&& re_pos[times] <= r){
        if(num[re_col[times]]++ == 0)
            ans++;
        if(--num[col[re_pos[times]]] == 0)
            ans--;
    }
    swap(re_col[times],col[re_pos[times]]);
}

void solve(){
    for(int i = 0;i<query.size();i++){
        //莫队核心转移
        Query w = query[i];
        while(l > w.ql)  add(--l);
        while(r < w.qr)  add(++r);
        while(l < w.ql)  del(l++);
        while(r > w.qr)  del(r--);
        while(x < w.qx)  change(++x);
        while(x > w.qx)  change(x--);
        query[i].ans = ans;
    }
    sort(query.begin(),query.end(),cmp);
    for(int i = 0;i<query.size();i++)
        print(query[i].ans),print('\n');
}

int main(){
    init();
    solve();
    flush();
    return 0;
}