题目地址：洛谷：【P1903】[国家集训队]数颜色 – 洛谷、BZOJ：Problem 2120. — 数颜色

题目描述

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

1. Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2. R P Col 把第P支画笔替换为颜色Col。

为了满足墨墨的要求，你知道你需要干什么了吗？

题意简述

给一个颜色数组，每个位置有一个颜色，两种操作：

1. 改变某位置颜色
2. 查询区间颜色数

输入输出格式

输入格式：
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。
第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式：
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

输入输出样例

输入样例#1：

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

输出样例#1：

4
4
3
4

说明

对于100%的数据，N≤50000，M≤50000，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
本题可能轻微卡常数

题解

我们可以求出每个位置的pre值，表示该位置颜色在该位置之前的最后一次出现位置。如果该位置之前没有出现过这种颜色了，则规定pre值为0。这个问题就可以转化成一个区间内查询pre值小于区间左端点数量的问题，显然可以用树状数组套主席树这样的形式来维护。
至于修改，我们可以用set维护每个颜色的出现位置，这样就可以利用lower_bound找前驱后继，从而维护线段树中的信息。
总复杂度O(n \log^2 n)，不过这种写法跑的特别慢，还好卡进去了。

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <set>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'Q' || c == 'R';
}

inline char readop() {
    char c;
    while(!isop(c = fgc())) {}
    return c;
}

const int MAXN = 50005;

struct Node {
    int lch, rch, val;
} tr[MAXN * 200];
int rt[MAXN], tot;

int sta[MAXN], stop;

inline int newnode() {
    if(!stop) return ++tot;
    int p = sta[--stop];
    memset(tr + p, 0, sizeof(Node));
    return p;
}

inline void delnode(int p) {
    if(!p) return;
    sta[stop++] = p;
}

inline void insert(int &o, int l, int r, int x) {
    int p = newnode(); tr[p] = tr[o]; delnode(o); o = p;
    tr[o].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x);
    else insert(tr[o].rch, mid + 1, r, x);
}

inline void erase(int &o, int l, int r, int x) {
    int p = newnode(); tr[p] = tr[o]; delnode(o); o = p;
    tr[o].val--;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) erase(tr[o].lch, l, mid, x);
    else erase(tr[o].rch, mid + 1, r, x);
}

inline int query(int o, int l, int r, int x) {
    if(l == r) return 0;
    int mid = (l + r) >> 1;
    if(x <= mid) return query(tr[o].lch, l, mid, x);
    else return tr[tr[o].lch].val + query(tr[o].rch, mid + 1, r, x);
}

int n, m;

inline int lowbit(int x) {
    return x & -x;
}

inline void insert(int x, int v) {
    for(int i = x; i <= n; i += lowbit(i)) {
        insert(rt[i], 0, 1000000, v);
    }
}

inline void erase(int x, int v) {
    for(int i = x; i <= n; i += lowbit(i)) {
        erase(rt[i], 0, 1000000, v);
    }
}

inline int query(int x, int v) {
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res += query(rt[i], 0, 1000000, v);
    }
    return res;
}

std::set<int> col[1000005];
int col2[MAXN];

char op; int x, y;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= 1000000; i++) {
        col[i].insert(0);
    }
    for(int i = 1; i <= n; i++) {
        x = readint();
        col[x].insert(i); col2[i] = x;
        if(col[x].empty()) col[x].insert(0);
        std::set<int>::iterator it = col[x].lower_bound(i);
        insert(i, *--it);
    }
    while(m--) {
        op = readop(); x = readint(); y = readint();
        if(op == 'Q') {
            printf("%d\n", query(y, x) - query(x - 1, x));
        } else {
            std::set<int>::iterator it = col[col2[x]].lower_bound(x), 
                itp = --it, itn = ++++it; --it;
            erase(x, *itp); 
            if(itn != col[col2[x]].end()) { 
                erase(*itn, x); insert(*itn, *itp);
            } 
            col[col2[x]].erase(it); col2[x] = y;
            col[col2[x]].insert(x); it = col[col2[x]].lower_bound(x); 
            itp = --it; itn = ++++it; --it;
            insert(x, *itp); 
            if(itn != col[col2[x]].end()) {
                erase(*itn, *itp); insert(*itn, x);
            }
        }
    }
    return 0;
}