bzoj 4066 简单题

Posted on | Views:

$kd$ 树 + 定期重构.

由于这道题强制在线 + 卡空间,其它时间效率上比较优秀的二维数点方法不太适用.

利用 $kd$ 树维护所有点, $kd​$ 树的本质是高维的二叉搜索树,所以插入的时候就在上面选方向走.

需要定期重构保证树的形态平衡一些,也可以像替罪羊树一样,维护一个因子判断是否需要重构.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int inf=1e9;
const int MAXN=2e5+10;
int n,lastans,D;
struct node
{
	int ch[2],v[2],mx[2],mi[2];
	node()
	{
		ch[0]=ch[1]=0,mx[0]=mx[1]=-inf,mi[0]=mi[1]=inf;
		val=sum=0;
	}
	bool operator < (const node &rhs) const
	{
		return v[D]==rhs.v[D]?v[D^1]<rhs.v[D^1]:v[D]<rhs.v[D];
	}
	int val,sum;
} Tree[MAXN];
#define root Tree[o]
#define lson Tree[root.ch[0]]
#define rson Tree[root.ch[1]]
void pushup(int o)
{
	root.sum=lson.sum+rson.sum+root.val;
	for(int i=0; i<2; ++i)
	{
		root.mx[i]=max(root.mx[i],max(lson.mx[i],rson.mx[i]));
		root.mi[i]=min(root.mi[i],min(lson.mi[i],rson.mi[i]));
	}
}
int xl,xr,yl,yr;
void ins(int o,int d)
{
	int k=Tree[n].v[d]>root.v[d];
	if(root.ch[k])
		ins(root.ch[k],d^1);
	else
		root.ch[k]=n;
	pushup(o);
}
int BuildTree(int l,int r,int d)
{
	D=d;
	int mid=(l+r)>>1;
	int o=mid;
	nth_element(Tree+l,Tree+mid,Tree+r+1);
	for(int i=0;i<2;++i)
		root.mx[i]=root.mi[i]=root.v[i];
	if(l<=mid-1)
		root.ch[0]=BuildTree(l,mid-1,d^1);
	else
		root.ch[0]=0;
	if(mid+1<=r)
		root.ch[1]=BuildTree(mid+1,r,d^1);
	else
		root.ch[1]=0;
	pushup(o);
	return o;
}
bool check(int o)
{
	if(!o || root.mx[0]<xl || root.mi[0]>xr || root.mx[1]<yl || root.mi[1]>yr)
		return 0;
	return 1;
}
int query(int o)
{
	if(xl<=root.mi[0] && root.mx[0]<=xr && yl<=root.mi[1] && root.mx[1]<=yr)
		return root.sum;
	int res=0;
	if(xl<=root.v[0] && root.v[0]<=xr && yl<=root.v[1] && root.v[1]<=yr)
		res+=root.val;
	if(check(root.ch[0]))
		res+=query(root.ch[0]);
	if(check(root.ch[1]))
		res+=query(root.ch[1]);
	return res;
}
int main()
{
	read();
	int rt=0;
	while("RLDAKIOI")
	{
		int tp=read();
		if(tp==1)
		{
			++n;
			Tree[n].v[0]=Tree[n].mx[0]=Tree[n].mi[0]=read()^lastans;
			Tree[n].v[1]=Tree[n].mx[1]=Tree[n].mi[1]=read()^lastans;
			Tree[n].val=Tree[n].sum=read()^lastans;
			if(n==1)
				rt=n;
			else
				ins(rt,0);
			if(n%5000==0)
				rt=BuildTree(1,n,0);
		}
		else if(tp==2)
		{
			xl=read()^lastans;
			yl=read()^lastans;
			xr=read()^lastans;
			yr=read()^lastans;
			if(check(rt))
				lastans=query(rt);
			else
				lastans=0;
			printf("%d\n",lastans);
		}
		else if(tp==3)
			break;
	}
	return 0;
}