BZOJ2683: 简单题(cdq分治 树状数组)

时间：2021-04-05 23:59:37

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 2142  Solved: 874
[Submit][Status][Discuss]

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令

参数限制

内容

1 x y A

1<=x,y<=N，A是正整数

将格子x,y里的数字加上A

2 x1 y1 x2 y2

1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和

3

无

终止程序

Input

输入文件第一行一个正整数N。
接下来每行一个操作。
 

Output

对于每个2操作，输出一个对应的答案。
 

Sample Input

4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

Sample Output

3
5

HINT

1<=N<=500000,操作数不超过200000个，内存限制20M。
对于100%的数据，操作1中的A不超过2000。

Source

cdq分治裸题。

首先我们对询问点拆为$4$个前缀和查询

再把所有的询问/修改离线，按照$x$轴排序

直接上cdq分治，用树状数组为护$y$轴的贡献

归并排序版太难写了直接上sort

#include<cstdio>

#include<algorithm>

#define lowbit(x) ((x) & (-x))

using namespace std;

const int MAXN =  * 1e5 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, Qnum;

struct Query {

    int opt, x, y, v, ans, xxx;

    bool operator < (const Query &rhs) const {

        return x == rhs.x ? y < rhs.y : x < rhs.x;

    }

}Q[MAXN], Tp[MAXN];

int T[MAXN];

void Add(int pos, int val) {

    for(int i = pos; i <= N; i += lowbit(i)) T[i] += val;

}

int Sum(int pos) {

    int ans = ;

    for(int i = pos; i; i -= lowbit(i)) ans += T[i];

    return ans;

}

int num = , out[MAXN];

void CDQ(int l, int r) {

    if(l == r) return ;

    int mid = l + r >> ;

    CDQ(l, mid);

    CDQ(mid + , r);

    int i = l, j = mid + , p = l, last = ;

    sort(Q + l, Q + mid + );

    sort(Q + mid + , Q + r + );

    while(j <= r) {

        while(Q[i].opt ==  && i <= mid) i++;

        while(Q[j].opt ==  && j <= r) j++;

        if(i <= mid && Q[i].x <= Q[j].x) Add(Q[i].y, Q[i].v), last = i++;

        else if(j <= r) Q[j].ans += Sum(Q[j].y), j++;

    }

    for(int i = l; i <= last; i++)

        if(Q[i].opt == )

            Add(Q[i].y, -Q[i].v);

}

int main() {

    N = read();

    for(;;) {

        int op = read();

        if(op == ) break;

        if(op == ) {Q[++num].opt = op; Q[num].x = read(), Q[num].y = read(), Q[num].v = read();}

        else {

            int xx1 = read(), yy1 = read(), xx2 = read(), yy2 = read();

            Qnum++;

            Q[++num] = (Query) {op, xx2, yy2, , , Qnum};

            Q[++num] = (Query) {op, xx1 - , yy1 - , , , Qnum};

            Q[++num] = (Query) {op, xx1 - , yy2, , , Qnum};

            Q[++num] = (Query) {op, xx2, yy1 - , , , Qnum};

        }

    }

    CDQ(, num);

    for(int i = ; i <= num; i++) {

        if(Q[i].opt == ) {

            if(Q[i].v ==  || Q[i].v == ) out[Q[i].xxx] += Q[i].ans;

            else out[Q[i].xxx] -= Q[i].ans;

        }

    }

    for(int i = ; i <= Qnum; i++)

        printf("%d\n", out[i]);

    return ;

}

相关文章