隐藏
「bzoj4605」崂山白花蛇草水 - K-D树+替罪羊化+权值线段树 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj4605」崂山白花蛇草水 - K-D树+替罪羊化+权值线段树

题目大意

    神犇Aleph在SDOI Round2前立了一个flag:如果进了省队,就现场直播喝崂山白花蛇草水。凭借着神犇Aleph的实力,他轻松地进了山东省省队,现在便是他履行诺言的时候了。蒟蒻Bob特地为他准备了$999,999,999,999,999,999$瓶崂山白花蛇草水,想要灌神犇Aleph。神犇Aleph求(跪着的)蒟蒻Bob不要灌他,由于神犇Aleph是神犇,蒟蒻Bob最终答应了他的请求,但蒟蒻Bob决定将计就计,也让神犇Aleph回答一些问题。具体说来,蒟蒻Bob会在一个宽敞的广场上放置一些崂山白花蛇草水(可视为二维平面上的一些整点),然后询问神犇Aleph在矩形区域$(x_1,y_1),(x_2,y_2)(x_1\le x_2$且$y_1\le y_2$,包括边界$)$中,崂山白花蛇草水瓶数第$k$多的是多少。为了避免麻烦,蒟蒻Bob不会在同一个位置放置两次或两次以上的崂山白花蛇草水,但蒟蒻Bob想为难一下神犇Aleph,希望他能在每次询问时立刻回答出答案。神犇Aleph不屑于做这种问题,所以把这个问题交给了你。


题目分析

题意很简洁。

范围查询,K-D树;$k$大查询,权值线段树。
因此可以使用K-D树套权值线段树或权值线段树套K-D树。

因为有插入操作,因此需要对K-D树替罪羊化。
替罪羊化的数据结构放在内层在时间效率上更优,因此采用权值线段树套K-D树的方法。

直接做就可以了,嘴上AC真简单

然而这是我第一次写替罪羊化的K-D树,稍微讲一讲。
大概的重构方式和替罪羊树类似,但因为K-D树本身有简洁的形态,不希望因为替罪羊化给它加入多余的信息(如:父亲指针,重构位置 等)。
因此稍稍违背了自己的原则,写了指针,用指针指向需要重构的位置。
这样代码的可读性就提高了很多。

然而这道题很卡常数。
因此不要用很多常数不优的写法!
比如少传参(改为全局变量),不用构造函数,不重载(!!)


代码

代码中用到了很多指针的技巧(我也是照着别人学的),不懂可以问我。

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include<algorithm>
#include<cstdio>

namespace FastIO {
const int L=1<<15;
char buf[L],*S,*T;
char getchar() {
if(S==T) {T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
return *S++;
}
int Get_Int() {
int res=0,bj=1;char c=getchar();
while(!isdigit(c)) {if(c=='-')bj=-1;c=getchar();}
while(isdigit(c)) {res=res*10+c-'0';c=getchar();}
return res*bj;
}
}
using FastIO::Get_Int;

int min(int a,int b) {
return a<b?a:b;
}

int max(int a,int b) {
return a>b?a:b;
}

const int maxn=100005,maxv=1e9,K=2;
const double alpha=0.78;

int D,Insert[K]; //少传参

struct Point { //不用构造函数
int d[K],Min[K],Max[K],cnt,size;
Point *child[2];
} tree[maxn*25],*tcnt=tree,*P[maxn],**pcnt;

bool cmp(const Point *a,const Point *b) { //不重载
return a->d[D]<b->d[D];
}

struct KD_Tree {
int get_size(Point *p) {
return p?p->size:0;
}
bool balance(Point *p) {
return p->size*alpha>=max(get_size(p->child[0]),get_size(p->child[1]));
}
void push_up(Point *p) {
for(int i=0; i<K; i++) {
p->Max[i]=p->Min[i]=p->d[i];
if(p->child[0]) {
p->Min[i]=min(p->Min[i],p->child[0]->Min[i]);
p->Max[i]=max(p->Max[i],p->child[0]->Max[i]);
}
if(p->child[1]) {
p->Min[i]=min(p->Min[i],p->child[1]->Min[i]);
p->Max[i]=max(p->Max[i],p->child[1]->Max[i]);
}
}
p->size=get_size(p->child[0])+get_size(p->child[1])+p->cnt;
}
void build(Point *&p,int Left,int Right,bool now) {
D=now;
int mid=(Left+Right)>>1;
std::nth_element(P+Left,P+mid,P+Right+1,cmp);
p=P[mid]; //!!!
p->child[0]=p->child[1]=0; //!!!
if(Left<mid)build(p->child[0],Left,mid-1,now^1);
if(Right>mid)build(p->child[1],mid+1,Right,now^1);
push_up(p);
}
Point **pos;
bool pnow;
void insert(Point *&p,bool now) {
if(!p) {
p=++tcnt;
for(int i=0; i<K; i++)p->d[i]=Insert[i];
p->child[0]=p->child[1]=0;
p->cnt=1;
push_up(p);
return;
}
if(Insert[now]<p->d[now])insert(p->child[0],now^1);
else insert(p->child[1],now^1);
push_up(p);
if(!balance(p))pos=&p,pnow=now;
}
void dfs(Point *p) {
if(!p)return;
*++pcnt=p;
dfs(p->child[0]);
dfs(p->child[1]);
}
void rebuild(Point *&root,bool now) {
pcnt=P;
dfs(root);
build(root,1,pcnt-P,now);
}
void insert(Point *&root) {
pos=0;
insert(root,0);
if(pos)rebuild(*pos,pnow);
}
bool inspace(int* Min,int* Max,int* down,int* up) {
return down[0]<=Min[0]&&up[0]>=Max[0]&&down[1]<=Min[1]&&up[1]>=Max[1];
}
bool outspace(int* Min,int* Max,int* down,int* up) {
return Min[0]>up[0]||Max[0]<down[0]||Min[1]>up[1]||Max[1]<down[1];
}
int get_sum(Point *p,int* down,int* up) {
if(!p)return 0;
if(inspace(p->Min,p->Max,down,up))return p->size;
if(outspace(p->Min,p->Max,down,up))return 0;
return get_sum(p->child[0],down,up)+get_sum(p->child[1],down,up)+p->cnt*inspace(p->d,p->d,down,up);
}
} kdtree;

struct Segment_Tree {
struct Tree {
int lson,rson;
Point *root;
} tree[maxn*20];
int size;
#define ls tree[index].lson
#define rs tree[index].rson
void insert(int &index,int left,int right,int target) {
if(!index)index=++size;
kdtree.insert(tree[index].root);
if(left==right)return;
int mid=(left+right)>>1;
if(target<=mid)insert(ls,left,mid,target);
else insert(rs,mid+1,right,target);
}
int query(int index,int left,int right,int* down,int* up,int k) {
if(left==right)return left;
int mid=(left+right)>>1,sum=kdtree.get_sum(tree[rs].root,down,up);
if(sum>=k)return query(rs,mid+1,right,down,up,k);
else return query(ls,left,mid,down,up,k-sum);
}
} st;

int q,root,lastans=0;

int main() {
Get_Int();
q=Get_Int();
while(q--) {
int opt=Get_Int();
if(opt==1) {
Insert[0]=Get_Int()^lastans,Insert[1]=Get_Int()^lastans;
st.insert(root,1,maxv,Get_Int()^lastans);
} else {
int down[K],up[K];
down[0]=Get_Int()^lastans,down[1]=Get_Int()^lastans;
up[0]=Get_Int()^lastans,up[1]=Get_Int()^lastans;
int v=Get_Int()^lastans;
if(kdtree.get_sum(st.tree[root].root,down,up)<v) {
puts("NAIVE!ORZzyz.");
lastans=0;
} else printf("%d\n",lastans=st.query(root,1,maxv,down,up,v));
}
}
return 0;
}

姥爷们赏瓶冰阔落吧~