同 UVa 12345. Dynamic len(set(a[L:R]))

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

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){
        Add(x, p, -1); Add(x, pp, 1); p = 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;
    void Add(int x, int d){
        ++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){
        for (;x<=n;x+=low_bit(x)) C[x].Add(p, d);
    }
    void Modify(int x, int& p, int pp){
        Add(x, p, -1); Add(x, pp, 1); p = pp;
    }
    int Sum(int x){
        int z = 0; for (;x;x^=low_bit(x)) z += C[x].Sum(a);
        return z;
    }
    int Sum(int _a, int _b){
        a = _a, b = _b;
        return Sum(b) - Sum(a-1);
    }
}

Posted by xiaodao
Category: BZOJ