Description
維護一個W*W的矩陣，初始值均為S.每次操作可以增加某格子的權值,或詢問某子矩陣的總權值.修改操作數M<=160000,詢問數Q<=10000,W<=2000000. Input
第一行兩個整數,S,W;其中S為矩陣初始值;W為矩陣大小
接下來每行為一下三種輸入之一(不包含引號):
“1 x y a”
“2 x1 y1 x2 y2”
“3”
輸入1:你需要把(x,y)(第x行第y列)的格子權值增加a
輸入2:你需要求出以左下角為(x1,y1),右上角為(x2,y2)的矩陣內所有格子的權值和,并輸出
輸入3:表示輸入結束 Output
對于每個輸入2,輸出一行,即輸入2的答案 Sample Input 0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3 Sample Output 3
5
解題方法： 給個別人的鏈接 初學CDQ花了快1天理解這個原理，再推薦一位大牛寫的關于CDQ分治的總結: 見這里 初級CDQ大概理解了，不過CDQ套CDQ，以及高維偏序還不理解，強擼題吧！注意這個題數組開小不是RE,是WA，神坑。
//bzoj 1176//1維排序，二維分治，3維BIT#include <bits/stdc++.h>using namespace std;const int maxq = 200010;const int maxn = 500010;int S, W, ans[maxq];inline int read(){ char ch=getchar(); int f=1,x=0; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x*f;}namespace BIT{ int tree[2000010]; inline int lowbit(int x) {return x & -x;} inline void update(int x, int y) {for(int i = x; i <= W; i+=lowbit(i)) tree[i] += y;} inline int query(int x) {int res = 0; for(int i = x; i; i -= lowbit(i)) res += tree[i]; return res;}}using namespace BIT;struct Q{ int id, x, y, opt, del, ID; Q(){} Q(int id, int x, int y, int opt, int del, int ID) : id(id), x(x), y(y), opt(opt), del(del), ID(ID) {} bool Operator < (const Q &rhs) const{ return (x == rhs.x && y == rhs.y) ? opt < rhs.opt : ((x == rhs.x) ? y < rhs.y : x < rhs.x); }}q[maxq*4], tmp[maxq*4];void CDQ(int l, int r){ if(l == r) return ; int mid = (l+r)>>1, z1 = l, z2 = mid + 1; for(int i = l; i <= r; i++){ if(q[i].opt == 1 && q[i].id <= mid) update(q[i].y, q[i].del); if(q[i].opt == 2 && q[i].id > mid) ans[q[i].ID] += query(q[i].y) * q[i].del; } for(int i = l; i <= r; i++) if(q[i].opt == 1 && q[i].id <= mid) update(q[i].y, -q[i].del); for(int i = l; i <= r; i++) if(q[i].id <= mid) tmp[z1++] = q[i]; else tmp[z2++] = q[i]; for(int i = l; i <= r; i++) q[i] = tmp[i]; CDQ(l, mid); CDQ(mid + 1, r);}int t, z;void PResolve(int x1, int y1, int x2, int y2){ //操作拆分 sum(x2,y2)+sum(x1-1,y1-1)+sum(x1-1,y2)-sum(x2,y1-1) z++; t++; q[t].id = t; q[t].ID = z; q[t].x = x1 - 1; q[t].y = y1 - 1; q[t].del = 1; q[t].opt = 2; t++; q[t].id = t; q[t].ID = z; q[t].x = x2; q[t].y = y2; q[t].del = 1; q[t].opt = 2; t++; q[t].id = t; q[t].ID = z; q[t].x = x1 - 1; q[t].y = y2; q[t].del = -1; q[t].opt = 2; t++; q[t].id = t; q[t].ID = z; q[t].x = x2; q[t].y = y1 - 1; q[t].del = -1; q[t].opt = 2;}int main(){ //scanf("%d%d", &S, &W); S = read(); W = read(); t = z = 0; while(1){ int cmd; //scanf("%d", &cmd); cmd = read(); if(cmd == 3) break; if(cmd == 1){t++; //scanf("%d%d%d", &q[t].x, &q[t].y, &q[t].del); q[t].x = read(), q[t].y = read(), q[t].del = read(); q[t].id = t; q[t].opt = 1; } if(cmd == 2){ int x1, x2, y1, y2; //scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x1 = read(), y1 = read(), x2 = read(), y2 = read(); presolve(x1, y1, x2, y2); } } sort(q + 1, q + t + 1); CDQ(1, t); for(int i = 1; i <= z; i++) printf("%d/n", ans[i]); return 0;}新聞熱點
疑難解答
