隐藏
「bzoj3600」没有人的算术 - 替罪羊树+实数区间+线段树 | Bill Yang's Blog

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

0%

「bzoj3600」没有人的算术 - 替罪羊树+实数区间+线段树

题目大意

    定义$0$是最小的数,定义一个二元组$(a,b)$为一个数,定义两个数的大小关系是先按照第一关键字比较,后按照第二关键字比较。
    数可以进行复合,即可以将$(a,b)$,$(c,d)$复合为一个数$((a,b),(c,d))$,大小关系同样进行嵌套。
    修改一个数为已有两个数的复合,询问一段区间的最大值。


题目分析

我们要快速比较两个数的大小关系。
因为数进行了嵌套,故比较这两个数需要先比较内部的数大小,这样的复杂度是不能接受的。

不妨使用陈立杰论文中的方法,将每个数对应一个映射插入到平衡树中,每次插入到平衡树中就对它添加一个映射。

这样我们每次的插入,其内部嵌套的两个数和其他数的大小关系已经知道,我们就可以插入到平衡树中。同样的,我们有了表示大小关系的映射值,就可以建立线段树维护最大值了。

这个映射称为实数区间,每个结点对应一个实数区间,如图:

每个点的数(实数区间中点的值)即为我们使用的映射的值,平衡树的中序遍历有序,故映射的值就可以表示其大小关系。

一个节点的左儿子实数区间为$[l,mid]$,右儿子为$[mid,r]$,故我们可以在插入后维护实数区间。

下面来说明一些东西:

为何替罪羊树重构后不需要更新线段树

因为我们插入一个数才会引起重构,因此无论重构与否,原来的值的大小关系不变,而只有原来的数和现在的数大小关系不同。
而我们在线段树上插入新点的时候,更新了路径上最大值与它的关系,故无需更新线段树,因为更新不会影响任何值的大小关系。

为何不能用Splay维护

替罪羊树显然可以维护,treap也可以维护(因为重量平衡,每次旋转后暴力更新子树的实数区间)。
Splay不能维护的原因不仅仅是深度过大精度不够的问题:

如图,因为旋转后实数区间变了,和原来的映射不再对应,因此新插入的点不满足平衡树性质,故不能使用Splay维护。


代码

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=500005;

int n,m,pos[maxn],_pos;
double Val[maxn],posl,posr;

struct Data {
int l,r;
bool operator < (const Data& y) const {
return Val[l]<Val[y.l]||(Val[l]==Val[y.l]&&Val[r]<Val[y.r]);
}
bool operator == (const Data& y) const {
return Val[l]==Val[y.l]&&Val[r]==Val[y.r];
}
};

struct Tree {
int child[2],father;
int size;
Data val;
};

struct ScapeGoat_Tree {
Tree tree[maxn];
int root,size;
#define ls(x) tree[x].child[0]
#define rs(x) tree[x].child[1]
#define fa(x) tree[x].father
#define val(x) tree[x].val
#define size(x) tree[x].size
bool balance(int index) {
return size(index)*0.7>=max(size(ls(index)),size(rs(index)));
}
bool checkson(int index) {
return rs(fa(index))==index;
}
void push_up(int index) {
size(index)=size(ls(index))+1+size(rs(index));
}
int cnt,a[maxn];
void dfs(int index) {
if(ls(index))dfs(ls(index));
a[++cnt]=index;
if(rs(index))dfs(rs(index));
}
int build(int Left,int Right,double left,double right) {
if(Left>Right)return 0;
int mid=(Left+Right)>>1,pos=a[mid];
double midv=(left+right)/2;
Val[pos]=midv;
ls(pos)=build(Left,mid-1,left,midv);
rs(pos)=build(mid+1,Right,midv,right);
fa(ls(pos))=fa(rs(pos))=pos;
push_up(pos);
return pos;
}
void rebuild(int index,double left,double right) {
cnt=0;
dfs(index);
int father=fa(index),side=checkson(index);
int pos=build(1,cnt,left,right);
tree[father].child[side]=pos;
fa(pos)=father;
if(index==root)root=pos;
}
int insert(int &index,double left,double right,Data val) {
double midv=(left+right)/2;
if(!index) {
index=++size;
val(index)=val;
Val[index]=midv;
size(index)=1;
return index;
}
int tmp;
if(val==val(index))return index;
else {
size(index)++;
if(val<val(index))tmp=insert(ls(index),left,midv,val);
else tmp=insert(rs(index),midv,right,val);
fa(ls(index))=fa(rs(index))=index;
}
if(!balance(index)) {
_pos=index;
posl=left;
posr=right;
}
return tmp;
}
} sgt;

struct Tree2 {
int left,right,max;
};

struct Segment_Tree {
Tree2 tree[maxn*4];
#define ls index<<1
#define rs index<<1|1
void push_up(int index) {
int x=tree[ls].max,y=tree[rs].max;
if(Val[pos[x]]<Val[pos[y]])tree[index].max=y;
else tree[index].max=x;
}
void build(int index,int Left,int Right) {
tree[index].left=Left,tree[index].right=Right;
if(Left==Right) {
tree[index].max=Left;
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
push_up(index);
}
void update(int index,int target) {
if(target<tree[index].left||target>tree[index].right)return;
if(tree[index].left==tree[index].right) {
tree[index].max=tree[index].left;
return;
}
update(ls,target);
update(rs,target);
push_up(index);
}
int query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return 0;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].max;
int x=query(ls,Left,Right),y=query(rs,Left,Right);
if(Val[pos[x]]<Val[pos[y]])return y;
return x;
}
} st;

int main() {
n=Get_Int();
m=Get_Int();
Val[0]=-1;
sgt.insert(sgt.root,0,1,(Data) {0,0});
for(int i=1; i<=n; i++)pos[i]=1;
st.build(1,1,n);
for(int i=1; i<=m; i++) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x=Get_Int(),y=Get_Int();
if(opt=='C') {
int k=Get_Int();
_pos=0;
pos[k]=sgt.insert(sgt.root,0,1,(Data) {pos[x],pos[y]});
if(_pos)sgt.rebuild(_pos,posl,posr);
st.update(1,k);
} else printf("%d\n",st.query(1,x,y));
}
return 0;
}
姥爷们赏瓶冰阔落吧~