首页 > 代码库 > 【bzoj4066】简单题 KD-tree

【bzoj4066】简单题 KD-tree

2024-09-29 19:01:02   217人阅读

题目描述

你有一个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

无

终止程序

 
 

 

 

 

 

 

 

输入

输入文件第一行一个正整数N。
接下来每行一个操作。每条命令除第一个数字之外，均要异或上一次输出的答案last_ans，初始时last_ans=0。

输出

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

样例输入

4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3

样例输出

3
5

题解

KD-tree

题目强制在线，所以不能离线分治；平面上问题，可以用KD-tree来解决。

具体来说大部分都是板子，只有查询时有点变化，类似于 线段树/平衡树 的区间查询，不断缩小范围。

然而这样裸上亲测会TLE，究其原因是KD-tree的退化。

所以每次加入一定数目的点后，我们需要将KD-tree重构，类似于替罪羊树，只不过替罪羊树重构的是子树，而这里直接重构整棵树。

这样能够使得树高不会特别离谱，然后就可以过了。

#include <cstdio>#include <cstring>#include <algorithm>#define N 500010using namespace std;struct data{	int p[2] , maxn[2] , minn[2] , c[2] , w , sum;}a[N];int d , root;bool cmp(data a , data b){	return a.p[d] == b.p[d] ? a.p[d ^ 1] < b.p[d ^ 1] : a.p[d] < b.p[d];}void pushup(int k , int s){	a[k].maxn[0] = max(a[k].maxn[0] , a[s].maxn[0]);	a[k].minn[0] = min(a[k].minn[0] , a[s].minn[0]);	a[k].maxn[1] = max(a[k].maxn[1] , a[s].maxn[1]);	a[k].minn[1] = min(a[k].minn[1] , a[s].minn[1]);	a[k].sum += a[s].sum;}int build(int l , int r , int now){	int mid = (l + r) >> 1;	d = now , nth_element(a + l , a + mid , a + r + 1 , cmp);	a[mid].maxn[0] = a[mid].minn[0] = a[mid].p[0];	a[mid].maxn[1] = a[mid].minn[1] = a[mid].p[1];	a[mid].sum = a[mid].w;	a[mid].c[0] = a[mid].c[1] = 0;	if(l < mid) a[mid].c[0] = build(l , mid - 1 , now ^ 1) , pushup(mid , a[mid].c[0]);	if(r > mid) a[mid].c[1] = build(mid + 1 , r , now ^ 1) , pushup(mid , a[mid].c[1]);	return mid;}void ins(int x){	int *t = &root;	d = 0;	while(*t) pushup(*t , x) , t = &a[*t].c[a[x].p[d] > a[*t].p[d]] , d ^= 1;	*t = x;}int query(int k , int x1 , int y1 , int x2 , int y2){	if(!k || a[k].maxn[0] < x1 || a[k].maxn[1] < y1 || a[k].minn[0] > x2 || a[k].minn[1] > y2) return 0;	if(a[k].maxn[0] <= x2 && a[k].maxn[1] <= y2 && a[k].minn[0] >= x1 && a[k].minn[1] >= y1) return a[k].sum;	int ans = 0;	if(a[k].p[0] >= x1 && a[k].p[0] <= x2 && a[k].p[1] >= y1 && a[k].p[1] <= y2) ans += a[k].w;	ans += query(a[k].c[0] , x1 , y1 , x2 , y2) + query(a[k].c[1] , x1 , y1 , x2 , y2);	return ans;}int main(){	int opt , x1 , y1 , x2 , y2 , last = 0 , tot = 0;	scanf("%*d");	while(scanf("%d" , &opt) != EOF && opt != 3)	{		if(opt == 1)		{			tot ++ , scanf("%d%d%d" , &a[tot].p[0] , &a[tot].p[1] , &a[tot].w);			a[tot].p[0] ^= last , a[tot].p[1] ^= last , a[tot].w ^= last , a[tot].sum = a[tot].w;			a[tot].maxn[0] = a[tot].minn[0] = a[tot].p[0];			a[tot].maxn[1] = a[tot].minn[1] = a[tot].p[1];			ins(tot);			if(tot % 10000 == 0) root = build(1 , tot , 0);		}		else scanf("%d%d%d%d" , &x1 , &y1 , &x2 , &y2) , x1 ^= last , y1 ^= last , x2 ^= last , y2 ^= last , printf("%d\n" , last = query(root , x1 , y1 , x2 , y2));	}	return 0;}

 

 

【bzoj4066】简单题 KD-tree


联系
我们