Bzoj 2120(带修莫队)

发表于 | 分类于 | | + s

Bzoj 2120
带修莫队基础题，见此处讲解

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
const int MAXN = 10000 + 5;
int n, m, bl[MAXN], totblo, n_q, n_u, ai[MAXN], oai[MAXN], ans[MAXN], lst[MAXN], tax[1000000 + 5];
//n_q, n_u分别为q，u数组大小(询问，修改个数)
//oai为原数组，lst为该位置现在的值是哪个修改修改的(没有修改为0) 
//tax为桶 
struct query {//询问 
    int l, r, t, id;
    //t为时间戳 
    bool operator < (const query &b) const {//带修莫队排序 
        if (bl[l] == bl[b.l]) 
            return (bl[r] == bl[b.r] ? t < b.t : r < b.r);
        return bl[l] < bl[b.l];
    }
}q[MAXN];
struct update {//修改 
    int p, col, lst;//位置、颜色、上一个该位置(p)的修改 (没有修改为0) 
}u[MAXN];
int nt, nl, nr, nans;
void clean() {
    n_q = n_u = 0;
    ms(tax, 0);
}
void adjust(int x, int add) {
    tax[ai[x]] += add;
    if (add == 1 && tax[ai[x]] == 1) nans++;
    if (add == -1 && tax[ai[x]] == 0) nans--;
}
void update_update(int type, int id, int x) {
    //1撤销，2更新 
    if (type == 1) {
        if (nl <= x && x <= nr) adjust(x, -1);//nl <= x && x <= nr才adjust!!!!!  
        if (u[id].lst == 0) ai[x] = oai[x]; else ai[x] = u[u[id].lst].col;
        if (nl <= x && x <= nr) adjust(x, +1);//nl <= x && x <= nr才adjust!!!!! 
        lst[x] = u[id].lst;
    } else {
        u[id].lst = lst[x];
        lst[x] = id;
        if (nl <= x && x <= nr) adjust(x, -1);//nl <= x && x <= nr才adjust!!!!! 
        ai[x] = u[id].col;
        if (nl <= x && x <= nr) adjust(x, +1);//nl <= x && x <= nr才adjust!!!!! 
    }
}
int solve() {
    clean();
    totblo = pow(n, 0.66666666);
    for (int i = 1; i <= n; i++) scanf("%d", &ai[i]), oai[i] = ai[i];
    for (int i = 1; i <= m; i++) {
        char opt[10];
        scanf("%s", opt);
        if (opt[0] == 'Q') {
            n_q++;
            q[n_q].id = n_q, q[n_q].t = n_u;
            scanf("%d%d", &q[n_q].l, &q[n_q].r);
        } else {
            n_u++, lst[n_u] = 0, u[n_u].lst = 0;
            scanf("%d%d", &u[n_u].p, &u[n_u].col);
        }
    }
    sort(q + 1, q + 1 + n_q);
    nt = 0, nl = 1, nr = 0, nans = 0;
    for (int i = 1; i <= n_q; i++) {
        while (nt > q[i].t) update_update(1, nt, u[nt].p), nt--;//撤销
        while (nt < q[i].t) update_update(2, nt + 1, u[nt + 1].p), nt++;//更新 

        while (nl < q[i].l) adjust(nl    , -1), nl++;
        while (nl > q[i].l) adjust(nl - 1, +1), nl--;
        while (nr < q[i].r) adjust(nr + 1, +1), nr++;
        while (nr > q[i].r) adjust(nr    , -1), nr--;

        ans[q[i].id] = nans;
    }
    for (int i = 1; i <= n_q; i++) printf("%d\n", ans[i]);
    return 0;
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}
/*
不判 nl <= x && x <= nr WA的数据 
6 8
1 2 3 4 5 5
R 4 4
R 2 3
Q 1 4
R 1 2
Q 1 4
R 3 5
R 5 8
Q 1 4
*/
------ 本文结束 ------