bzoj 1176 cdq分治套樹狀數組 -开发者知识库

bzoj 1176 cdq分治套樹狀數組 -开发者知识库,第1张

題面:

維護一個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的答案

思路:正常思路用樹狀數組套樹狀數組,但是w范圍過大,開不下。考慮用cdq分治套樹狀數組。我們用cdq分治對x坐標排序,用樹狀數組維護y坐標,把詢問用差分思想拆分成四個不同的詢問即可。

代碼:

#include <bits/stdc  .h>
#define LL long long
#define lowbit (x & (-x))
using namespace std;
const int maxn = 200010;
int tot, tot_ans, n;
struct query{
	int type, x, y, pos, flag;
};
query q[maxn], tmp[maxn];
int c[maxn * 10], ans[maxn];
void add(int x, int y) {
	for (; x <= n; x  = lowbit)
		c[x]  = y;
}
int ask(int x) {
	int ans = 0;
	for (; x; x-= lowbit) {
		ans  = c[x];
	}
	return ans;
}
void clear(int x) {
	for (; x <= n; x  = lowbit) {
		c[x] = 0;
	}
}
void cdq(int l, int r) {
	if(l == r) return;
	int mid = (l   r) >> 1;
	cdq(l, mid);
	cdq(mid   1, r);
	int l1 = l, l2 = mid   1, pos = l;
	while(l1 <= mid && l2 <= r) {
		if(q[l1].x <= q[l2].x) {
			if(q[l1].type == 1) {
				add(q[l1].y, q[l1].pos);
			}
			tmp[pos  ] = q[l1  ];
		} else {
			if(q[l2].type == 2) {
				ans[q[l2].pos]  = q[l2].flag * ask(q[l2].y);
			}
			tmp[pos  ] = q[l2  ];
		}
	}
	while(l1 <= mid) tmp[pos  ] = q[l1  ];
	while(l2 <= r) {
		if(q[l2].type == 2) {
			ans[q[l2].pos]  = q[l2].flag * ask(q[l2].y);
		}
		tmp[pos  ] = q[l2  ];
	}
	for (int i = l; i <= mid; i  ) {
		if(q[i].type == 1) {
			clear(q[i].y);
		}
	}
	for (int i = l; i <= r; i  )
		q[i] = tmp[i];
}
int main() {
	int l1, r1, l2, r2, x, op, val;
	scanf("%d%d", &x, &n);
	while(~scanf("%d", &op) && op != 3) {
		if(op == 1) {
			scanf("%d%d%d", &l1, &r1, &val);
			q[  tot] = (query){1, l1, r1, val, 0};
		} else {
			scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
			tot_ans  ;
			ans[tot_ans] = x * (l2 - l1   1) * (r2 - r1   1);
			q[  tot] = (query){2, l1 - 1, r1 - 1, tot_ans, 1};
			q[  tot] = (query){2, l1 - 1, r2, tot_ans, -1};
			q[  tot] = (query){2, l2, r1 - 1, tot_ans, -1};
			q[  tot] = (query){2, l2, r2, tot_ans, 1};
		}
	}
	cdq(1, tot);
	for (int i = 1; i <= tot_ans; i  ) {
		printf("%d\n", ans[i]);
	}
} 

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复