BZOJ2683: 简单题(cdq分治 树状数组)
程序员文章站
2022-04-18 20:17:28
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 输出 ......
Submit: 2142 Solved: 874
[][][]
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
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
3
5
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 = 5 * 1e5 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', 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 = 0; for(int i = pos; i; i -= lowbit(i)) ans += T[i]; return ans; } int num = 0, out[MAXN]; void CDQ(int l, int r) { if(l == r) return ; int mid = l + r >> 1; CDQ(l, mid); CDQ(mid + 1, r); int i = l, j = mid + 1, p = l, last = 0; sort(Q + l, Q + mid + 1); sort(Q + mid + 1, Q + r + 1); while(j <= r) { while(Q[i].opt == 2 && i <= mid) i++; while(Q[j].opt == 1 && 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 == 1) Add(Q[i].y, -Q[i].v); } int main() { N = read(); for(;;) { int op = read(); if(op == 3) break; if(op == 1) {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, 1, 0, Qnum}; Q[++num] = (Query) {op, xx1 - 1, yy1 - 1, 2, 0, Qnum}; Q[++num] = (Query) {op, xx1 - 1, yy2, 3, 0, Qnum}; Q[++num] = (Query) {op, xx2, yy1 - 1, 4, 0, Qnum}; } } CDQ(1, num); for(int i = 1; i <= num; i++) { if(Q[i].opt == 2) { if(Q[i].v == 1 || Q[i].v == 2) out[Q[i].xxx] += Q[i].ans; else out[Q[i].xxx] -= Q[i].ans; } } for(int i = 1; i <= Qnum; i++) printf("%d\n", out[i]); return 0; }
推荐阅读
-
BZOJ2683: 简单题(cdq分治 树状数组)
-
陌上花开 HYSBZ - 3262 三维偏序问题 CDQ分治+树状数组
-
三维偏序(陌上花开)---洛谷P3810&&BZOJ3262(cdq分治--归并排序+树状数组)
-
Luogu P3810 【模板】三维偏序(陌上花开) CDQ分治 树状数组
-
P3810-[模板]三维偏序(陌上花开)【CDQ分治,树状数组】
-
洛谷 - P3810 【模板】三维偏序(陌上花开)(CDQ分治套树状数组)
-
洛谷 P3810 【模板】三维偏序(陌上花开)【cdq 分治】【树状数组】
-
【题解】洛谷P3810【模板】三维偏序(陌上花开)cdq分治+树状数组
-
BZOJ2683: 简单题(cdq分治 树状数组)
-
陌上花开 bzoj3262 CDQ分治套树状数组 三维偏序问题