记录编号	537015	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	Cooook	是否通过	通过
代码语言	C++	运行时间	2.064 s
提交时间	2019-07-09 09:59:31	内存使用	17.67 MiB

# include <bits/stdc++.h>
const int MAXN = 1e4 + 5;
const int len = 100;
int n, m, col[MAXN], block[MAXN], pos[MAXN * 100], bl[MAXN], pre[MAXN], cp[MAXN];


inline int read() {
    int x = 0, f = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
    for (; isdigit(ch); ch = getchar()) x = x * 10 + (ch ^ 48);
    return x * f;
}

inline bool read_char(){
    char ch = getchar();
    for(; ch !='Q' && ch != 'R'; ch = getchar());
    return ch == 'Q';
}

inline void rebuild(int x) {
    int l = (x - 1) * len + 1, r = std::min(x * len, n);
    for (int i = l; i <= r; ++i) block[i] = pre[i];
    std::sort(&block[l], &block[r + 1]);
}

inline int find(int x, int t) {
    int Ans = t, l = (x - 1) * len + 1, r = std::min(n, x * len), mid;
    int L = l;
    while (l <= r) {
        mid = l + r >> 1;
        if (block[mid] < t) Ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return Ans - L + 1;
}

inline int Query(int L, int R) {
    int bl_l = bl[L] + 1, bl_r = bl[R] - 1, Ans = 0;
    for (int i = bl_l; i <= bl_r; ++i) Ans += find(i, L);
    for (int i = L; i <= (bl_l - 1) * len && i <= R; ++i) if (pre[i] < L) ++ Ans;
    if (bl[L] != bl[R]) for (int i = bl_r * len + 1; i <= R; ++i) if (pre[i] < L) ++ Ans;
    return Ans;
}

int main() {
    freopen("nt2011_color.in", "r", stdin);
    freopen("nt2011_color.out", "w", stdout);
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) {
        col[i] = read();
        pre[i] = pos[col[i]];
        pos[col[i]] = i;
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= bl[n]; ++i) rebuild(i); 
    bool op; int x, y;
    while (m --) {
        op = read_char();
        x = read(), y = read();
        if (op) printf("%d\n", Query(x, y));
        else {
            col[x] = y;
            memset(pos, 0, sizeof pos);
            for (int i = 1; i <= n; ++i) cp[i] = pre[i]; 
            for (int i = 1; i <= n; ++i) {
                pre[i] = pos[col[i]];
                pos[col[i]] = i;
                if (pre[i] != cp[i]) rebuild(bl[i]);
            }
        }
    }
    return 0; 
}