BZOJ 2120. 數顏色

//}/* .................................................................................................................................. */

const int N = int(1e4) + 9;
int A[N], AA[N], n, m;

namespace ST{

#define lx l[x]
#define rx r[x]
#define ly l[y]
#define ry r[y]
#define ml (ll + rr >> 1)
#define mr (ml + 1)

const int NN = N*10*10*7 + 9;
int l[NN], r[NN], c[NN], tot;

int new_node(){
return ++tot;
}

int Add(int y, int p, int d){
int x = new_node(), root = x; int ll = 0, rr = n;
//cout << p << " " << d <<endl;

c[x] = c[y] + d;
while (ll < rr){
if (p < mr){
lx = new_node(), rx = ry;
x = lx, y = ly, rr = ml;
}
else {
lx = ly, rx = new_node();
x = rx, y = ry, ll = mr;
}
c[x] = c[y] + d;
}
return root;
}

int Sum(int x, int p){ // 小於 x
int z = 0, ll = 0, rr = n; while (ll < rr){
if (p < mr) x = lx, rr = ml;
else z += c[lx], x = rx, ll = mr;
}
return z;
}
}

namespace BIT{
int C[N], a, b;

void Add(int x, int p, int d){
for (;x<=n;x+=low_bit(x)) C[x] = ST::Add(C[x], p, d);
}
void Modify(int x, int& p, int pp){
}
int Sum(int x){
int z = 0; for (;x;x^=low_bit(x)) z += ST::Sum(C[x], a);
return z;
}
int Sum(int _a, int _b){
a = _a, b = _b;
return Sum(b) - Sum(a-1);
}
}

const int AMAX = int(1e6) + 9;
SI H[AMAX];

void print(){
REP_1(i, n) cout << A[i] << " "; puts("");
REP_1(i, n) cout << AA[i] << " "; puts("");
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif

RD(n, m); REP_1(i, n){
RD(A[i]); SI &s = H[A[i]]; if (s.empty()) s.insert(0);
BIT::Add(i, AA[i] = *s.rbegin(), 1); s.insert(i);
}

DO(m){
char cmd; int a, b; RC(cmd); RD(a, b);
if (cmd == 'Q'){
OT(BIT::Sum(a, b));
}
else{
if (A[a] == b) continue;
SI::iterator it; SI &sa = H[A[a]], &sb = H[b]; if (sb.empty()) sb.insert(0);
it = sa.upper_bound(a); if (it != sa.end()) BIT::Modify(*it, AA[*it], AA[a]);
it = sb.upper_bound(a); if (it != sb.end()) BIT::Modify(*it, AA[*it], a);
--it; BIT::Modify(a, AA[a], *it);
sa.erase(a); sb.insert(a); A[a] = b;
}
}
}


struct BITT{
map<int, int> C;
++x;
for (;x<=n;x+=low_bit(x)) C[x] += d;
}
int Sum(int x){
int z = 0; for (;x;x^=low_bit(x)) z += C[x];
return z;
}
};

namespace BIT{
BITT C[N]; int a, b;

void Add(int x, int p, int d){
}
void Modify(int x, int& p, int pp){