「BZOJ 1176」Mokia - CDQ

维护一个 （）的矩阵，初始值均为 。每次操作可以增加某格子的权值，或询问某子矩阵的总权值。

修改操作数 ，询问数 。

链接

BZOJ 1176

题解

设 表示左上角 右下角 的矩形数字总和，则

问题转化为三维（时间、、）偏序问题，时间是有序的，对 进行分治，用树状数组维护 即可。

代码

#include <cstdio>

const int MAXN = 2000000 + 1;
const int MAXQ = 10000;
const int MAXM = 160000 + MAXQ * 4;

struct Triple {
    int id, x, y, d, delta, *ans;

    Triple() {}
    Triple(const int x, const int y, const int d, int *ans) : x(x), y(y), d(d), delta(0), ans(ans) { setID(); }
    Triple(const int x, const int y, const int delta) : x(x), y(y), d(0), delta(delta), ans(NULL) { setID(); }

    void setID() {
        static int id = 0;
        this->id = id++;
    }

    bool isQuery() const { return d != 0; }
} a[MAXM];

int s, n, m, cnt, ans[MAXQ];

struct BinaryIndexedTree {
    int a[MAXN];

    static int lowbit(const int x) { return x & -x; }

    int query(const int x) const {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += a[i - 1];
        return ans;
    }

    void update(const int x, const int delta) {
        for (int i = x; i <= n; i += lowbit(i)) a[i - 1] += delta;
    }

    void clear(const int x) {
        for (int i = x; i <= n; i += lowbit(i)) {
            if (a[i - 1]) a[i - 1] = 0;
            else break;
        }
    }
} bit;

inline void cdq(Triple *l, Triple *r) {
    if (l == r) return;

    Triple *mid = l + (r - l) / 2;

    cdq(l, mid);
    cdq(mid + 1, r);

    static Triple tmp[MAXM];
    for (Triple *p = tmp, *p1 = l, *p2 = mid + 1; p <= tmp + (r - l); p++) {
        if ((p1->x <= p2->x && p1 <= mid) || p2 > r) {
            *p = *p1++;
            if (!p->isQuery()) bit.update(p->y, p->delta);
        } else {
            *p = *p2++;
            if (p->isQuery()) *p->ans += bit.query(p->y) * p->d;
        }
    }

    for (Triple *p = tmp, *q = l; q <= r; p++, q++) {
        if (q <= mid && !q->isQuery()) bit.clear(q->y);
        *q = *p;
    }
}

int main() {
    scanf("%d %d", &s, &n), n++;

    int qcnt = 0;
    while (true) {
        int t;
        scanf("%d", &t);
        if (t == 3) break;
        else if (t == 2) {
            int x1, y1, x2, y2;
            scanf("%d %d %d %d", &x1, &y1, &x2, &y2), x1++, y1++, x2++, y2++;

            int *p = &ans[qcnt++];
            *p = (y2 - y1 + 1) * (x2 - x1 + 1) * s;
            a[cnt++] = Triple(x2, y2, 1, p);
            a[cnt++] = Triple(x1 - 1, y2, -1, p);
            a[cnt++] = Triple(x2, y1 - 1, -1, p);
            a[cnt++] = Triple(x1 - 1, y1 - 1, 1, p);
        } else if (t == 1) {
            int x, y, delta;
            scanf("%d %d %d", &x, &y, &delta), x++, y++;
            a[cnt++] = Triple(x, y, delta);
        }
    }

    /*
    for (int i = 0; i < cnt; i++) {
        printf("Triple(x = %d, y = %d, d = %d, delta = %d)\n", a[i].x, a[i].y, a[i].d, a[i].delta);
    }
    */

    cdq(a, a + cnt - 1);

    for (int i = 0; i < qcnt; i++) printf("%d\n", ans[i]);

    return 0;
}