Menci

眉眼如初,岁月如故

在那无法确定的未来
只愿真心如现在一般清澈


「BZOJ 1176」Mokia - CDQ

维护一个 N×N N \times N N2000000 N \leq 2000000 )的矩阵,初始值均为 S S 。每次操作可以增加某格子的权值,或询问某子矩阵的总权值。

修改操作数 160000 \leq 160000 ,询问数 10000 \leq 10000

链接

BZOJ 1176

题解

Q(x1, y1, x2, y2) Q(x1,\ y1,\ x2,\ y2) 表示左上角 [x1, y1] [x1,\ y1] 右下角 [x2, y2] [x2,\ y2] 的矩形数字总和,则

Q(x1, y1, x2, y2)=Q(0, 0, x2, y2)Q(0, 0, x11, y2)Q(0, 0, x2, y11)+Q(0, 0, x1, y1) \begin{aligned} Q(x1,\ y1,\ x2,\ y2) = & Q(0,\ 0,\ x2,\ y2) \\ & - Q(0,\ 0,\ x1 - 1,\ y2) - Q(0,\ 0,\ x2,\ y1 - 1) \\ & + Q(0,\ 0,\ x1,\ y1) \end{aligned}

问题转化为三维(时间、x x y y )偏序问题,时间是有序的,对 x x 进行分治,用树状数组维护 y y 即可。

代码

#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;
}
最近的文章

「CQOI2011」动态逆序对 - CDQ

对于序列 A A ,它的逆序对数定义为满足 i<j i < j ,且 Ai>Aj A_i > A_j 的数对 (i, j) (i,\ j) 的个数。给 1 1 n n 的一个排列,按照某种顺序依次删除 m m 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

于  BZOJ, CDQ, CQOI, 分治, 数据结构, 树状数组 继续阅读
更早的文章

「SDOI2010」地精部落 - DP

我们称一个排列是合法的,当且仅当每一个数都满足这个数比它相邻的数都要大或都要小。

求长度为 N N 的合法排列数量。

于  BZOJ, DP, SDOI 继续阅读
comments powered by Disqus