强大到无与伦比的数据结构splay-tree

七 8th

由shǎ崽发表在ACM

33个评论

上篇文章~研究了一下sbt(size balance tree)后,三鲜师傅评论说splay-tree功能更强大,并且有很多其他数据结构无法实现的功能

于是赶紧去学习,看了这题后发现sbt几乎完成不了其中的任何一个操作,而线段树也无法完成插入.删除.翻转的操作,但是splay却能很完美的解决

其他平衡二叉树是根据权值来限制树的结构的,没有splay这么灵活.splay的任意旋转可以对一整个区间进行操作,并且可以任意增加区间,任意删除区间,都是logn的复杂度.并且可以沿用线段树的延迟标记,每次不用急着传递给子树,遍历到时候传下去即可,然后更新上来(我写了push_down和push_up两个函数,其实线段树也是这个套路,不过我以前写线段树的时候直接把这两个函数写进update和query里的,现在回去看以前线段树的代码感觉很乱,没有单独写出来优美~)

献上Crash撞神大牛的论文,里边就是将splay对一个区间的具体操作

一些其他二叉平衡树叶能完成的操作在这篇和楼教主同个时代的美女神牛杨思雨的论文里有介绍

介绍一些练习splay的题目:
更多 >

Popularity: 25% [?]

一点都不SB的SBT

七 2nd

由shǎ崽发表在ACM

16个评论

惯例,先献上一篇极品论文..

一种在编程复杂度,时间复杂度,空间复杂度都很优秀的平衡二叉树

这几天我是在学单调DP的时候 发现常常要对一个有序数列进行很多操作,一般的堆完成不了,于是找了二叉平衡树的资料学习.

本来庒神曾经给我splay tree的论文说很强大,但是经过比较发现SBT比伸展树各个方面都要强大…

算法和介绍都在上边论文里提到了.就不多说了

我就负责贴下自己写的模板还有一些练习的题目~

当然,还有很多题目,以下5题是较适合用平衡二叉树来解决的..其实最后一题就很鸡肋了,所以在很多没必要用SBT的时候还是别用好了,虽然SBT和同类算法比很优秀,但如果有其他方法能解决问题的时候用SBT就显得有点SB了..
[HNOI2002]营业额统计 {Insert , pred , succ , find}
[NOI2004]郁闷的出纳员 {Insert , DeleteSmall , Select}
[HNOI2004]宠物收养所 {Insert , pred , succ , Delete}
Double Queue {Insert , DeleteMax , DeleteMin}
Buy Tickets {DeleteSelect , build}

当然,这个模板在只能用于网络赛的时候贴一贴,现场赛的时候还是要理解了才能快速的敲出来~
(一开始用指针的,但是体积是现在的两倍…现场赛时一定难敲了很多,遂改成数组模拟)

?View Code CPP
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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232

template<typename Type>
class SizeBalanceTree {
public:
	void clear() {
		sz = 0;
		LC[0] = LC[0] = 0;
		SZ[0] = 0;
		root = 0;
	}
	int Size() {return SZ[root];}
	bool empty() {return root == 0;}
	void Build(int s,int e) {Build(root,s,e);}
	bool Find(Type key)	{return Find(root  , key);}
	void Insert(Type key)	{Insert(root , key);}
	void Delete(Type key)	{Delete(root , key);}
	Type DeleteSelect(int k) {return DeleteSelect(root , k);}
	void DeleteSmall(Type key) {DeleteSmall(root , key);}
	int Rank(Type key)	{return Rank(root , key);}
	Type Select(int k)	{return Select(root , k);}
	Type pred(Type key)	{return pred(root , key);}
	Type succ(Type key) {return succ(root , key);}
	Type getMin()	{
		int temp = root;
		while (LC[temp]) temp = LC[temp];
		return K[temp];
	}
	Type getMax()	{
		int temp = root;
		while (RC[temp]) temp = RC[temp];
		return K[temp];
	}
	Type DeleteMax() {
		int temp = root;
		if(RC[root] == 0) {
			root = LC[root];
			return K[temp];
		}
		while (RC[RC[temp]]) {
			SZ[temp] --;
			temp = RC[temp];
		}
		SZ[temp] --;
		Type ret = K[RC[temp]];
		RC[temp] = LC[RC[temp]];
		return ret;
	}
	Type DeleteMin() {
		int temp = root;
		if(LC[root] == 0) {
			root = RC[root];
			return K[temp];
		}
		while (LC[LC[temp]]) {
			SZ[temp] --;
			temp = LC[temp];
		}
		SZ[temp] --;
		Type ret = K[LC[temp]];
		LC[temp] = RC[LC[temp]];
		return ret;
	}
private:
	int SZ[maxn];
	Type K[maxn];
	int LC[maxn];
	int RC[maxn];
	int root , sz;
 
	void Build(int &root,int s,int e) {
		if(s > e) return ;
		int mid = (s + e)/2;
		root = ++sz;
		K[root] = mid;
		LC[root] = 0;
		RC[root] = 0;
		SZ[root] = e - s + 1;
		if(s == e) return ;
		Build(LC[root] , s , mid - 1);
		Build(RC[root] , mid + 1 , e);
	}
	bool Find(int &root,Type key) {
		if (root == 0) {
			return false;
		} else if (key < K[root]) {
			return Find(LC[root] , key);
		} else {
			return (K[root] == key || Find(RC[root] , key));
		}
	}
	void Insert(int &root,Type key) {
		if (root == 0) {
			root = ++ sz;
			LC[root] = RC[root] = 0;
			SZ[root] = 1;
			K[root] = key;
			return ;
		}
		SZ[root] ++;
		if (key < K[root]) {
			Insert(LC[root] , key);
		} else {
			Insert(RC[root] , key);
		}
		maintain(root , !(key < K[root]));
	}
	Type Delete(int &root,Type key) {
		SZ[root] --;
		if ((K[root] == key) || (key < K[root] && LC[root] == 0) || (K[root] < key && RC[root] == 0)) {
				Type ret = K[root];
				if ( LC[root] == 0 || RC[root] == 0 ) {
					root = LC[root] + RC[root];
				} else {
					K[root] = Delete(LC[root] , K[root] + 1);
				}
				return ret;
		} else {
			if ( key < K[root] ) {
				return Delete(LC[root] , key);
			} else {
				return Delete(RC[root] , key);
			}
		}
	}
	void DeleteSmall(int &root , Type key) {
		if ( root == 0 ) return ;
		if ( K[root] < key ) {
			root = RC[root];
			DeleteSmall(root , key);
		} else {
			DeleteSmall(LC[root] , key);
			SZ[root] = 1 + SZ[LC[root]] + SZ[RC[root]];
		}
	}
	int Rank(int &root , Type key) {
		if ( K[root] == key ) {
			return 1;
		} else if ( key < K[root] ) {
			return Rank(LC[root], key);
		} else {
			return SZ[LC[root]] + 1 + Rank(RC[root] , key);
		}
	}
	Type Select(int &root , int k) {
		if ( SZ[LC[root]] + 1 == k ) {
			return K[root];
		} else if ( k > SZ[LC[root]] ) {
			return Select(RC[root] , k - 1 - SZ[LC[root]]);
		} else {
			return Select(LC[root] , k);
		}
	}
	Type DeleteSelect(int &root,int k) {
		SZ[root] --;
		if ( SZ[LC[root]] + 1 == k ) {
			Type ret = K[root];
			if (LC[root] == 0 || RC[root] == 0 ) {
				root = LC[root] + RC[root];
			} else {
				K[root] = Delete(LC[root] , K[root] + 1);
			}
			return ret;
		} else if ( k > SZ[LC[root]] ) {
			return DeleteSelect(RC[root] , k - 1 - SZ[LC[root]]);
		} else {
			return DeleteSelect(LC[root] , k);
		}
	}
	Type pred(int &root , Type key) {
		if (root == 0) {
			return key;
		} else if (key > K[root]) {
			Type ret = pred(RC[root] , key);
			if(ret == key) return K[root];
			return ret;
		} else {
			return pred(LC[root] , key);
		}
	}
	Type succ(int &root , Type key) {
		if (root == 0) {
			return key;
		} else if (K[root] > key) {
			Type ret = succ(LC[root] , key);
			if (ret == key) return K[root];
			return ret;
		} else {
			return succ(RC[root] , key);
		}
	}
	void LeftRotate(int &root) {
		int temp = RC[root];
		RC[root] = LC[temp];
		LC[temp] = root;
		SZ[temp] = SZ[root];
		SZ[root] = 1 + SZ[LC[root]] + SZ[RC[root]];
		root = temp;
	}
	void RightRotate(int &root) {
		int temp = LC[root];
		LC[root] = RC[temp];
		RC[temp] = root;
		SZ[temp] = SZ[root];
		SZ[root] = 1 + SZ[LC[root]] + SZ[RC[root]];
		root = temp;
	}
	void maintain(int &root , bool flag) {
		if (root == 0) return ;
		if ( !flag ) {
			if ( SZ[LC[LC[root]]] > SZ[RC[root]] ) {
				RightRotate( root );
			} else if ( SZ[RC[LC[root]]] > SZ[RC[root]] ) {
				LeftRotate( LC[root] );
				RightRotate( root );
			} else {
				return ;
			}
		} else {
			if ( SZ[RC[RC[root]]] > SZ[LC[root]] ) {
				LeftRotate( root );
			} else if ( SZ[LC[RC[root]]] > SZ[LC[root]] ) {
				RightRotate( RC[root] );
				LeftRotate( root );
			} else {
				return ;
			}
		}
		maintain(LC[root] , false);
		maintain(RC[root] , true);
		maintain(root , false);
		maintain(root , true);
	}
};

如果需要用到int,double,longlong之外的一些类型的话,重载几个符号就好了,就像下边一样

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

struct Node{
	int key , priority;
	Node() {}
	Node(int a,int b):key(a) , priority(b) {}
	bool operator < (Node b) {
		return priority < b.priority;
	}
	bool operator > (Node b) {
		return priority > b.priority;
	}
	bool operator == (Node b) {
		return priority == b.priority;
	}
	Node operator + (int a) {
		return Node(key , priority + a);
	}
};
SizeBalanceTree<Node> SBT;

Popularity: 14% [?]

,

【Astar】坦克大战.final

七 1st

由shǎ崽发表在F.M.L.

12个评论

astar.baidu.com/final
历时一个多月，累计消耗时间达到15天的百度之星刚刚终于公布了最后的决赛名单。
很幸运用了上半年积累的RP(看我博客这半年的记录就知道没记几件好事)搭上了去百度总决赛的末班车（坦克大战第九）
十几天前用了四级和复习考试的时间对坦克进行了最后的修改。。
记得最后6个小时，也就是第二轮复赛结束后，我还向strongczq请教了一点经验，并且对盲狙进行了一次很大的修正。最后提交了一个AI名为hh.final的AI.
当时最后几个小时如果因为怕新版本会出bug不稳定而放弃修改的话今天的结果可能就不同了。
我们乱搞委员会有10个人进决赛，又可以群聚了，YM all
感谢各个和我们一起PK的“战友”（乱搞委员会四个人坦克进了前世）；也感谢自己对坦克执着到了最后；特别要感谢hhanger给我
们这么好的练习平台，而且他后来不更新坦克了，帮我们搞完全是无私的
祝各位去决赛玩的开心，hhanger决赛夺杯

Popularity: 10% [?]

考完一水~

六 24th

由shǎ崽发表在F.M.L.

7个评论

最后一门考试也随着我提前交白卷结束了..

这个学期的考试还真的一塌糊涂…

一部分客观原因是预习时间和坦克大战相冲突.我毅然选择了搞坦克大战

另外一部分主观原因是…我觉得在课堂里越来越学不到自己想要了解和有用的东西,想学东西等到要用的时候自然可以自己找资料自学.(其实这大概是我逃避的一个借口)说的明白点就是我一点都不想上学了…每次期末都要花时间去应付一堆对我来说毫无意义的东西

坦克大战也在前几天就结束提交了.结果据说已经比出来了.就是还没有公布,大概周末知道成绩,我应该离晋级决赛非常非常的接近….

Bless me….

Popularity: 6% [?]

悲剧的gcj

六 6th

由shǎ崽发表在ACM

27个评论

10:00

开场看到A题分值小,以为是水题,结果搞了半天没搞出来

然后就看到C有300+人过了,马上去看,还算有点思路,想看半天终于想到了n^2的算法.并且证明了正确性,此题全场只有60个人过,也算是难题了…

敲了好久好久才敲出来,主要是有个”两个矩形判交”的函数写不来,浙大模板拉了长时间,由于都是整数,于是用了整形几何函数

搞定后看了分数31分,要出现只要把B的小数据搞定就OK了,很顺利的搞定,现在41分,排在200+名,只要C的大数据不挂就晋级了

如果C的大数据挂了,B的大数据做出来也没办法,于是很从容想B的标准算法..最后10分钟想出来但是敲不来及了

0:30

一刷新..只有16分了,我知道我的C挂了.但是想不出原因,可能是我临时写的矩形判交写错了.后来code6说他的B越界了,改成long long就能过.

C题100000的数据量,本来不会益处,答案最多200000,但是到了判交的时候点积叉积一相乘就溢出了,我勒个叉,不会真是这么悲剧吧,马上按ctrl + z退回到提交C时候的代码..改成long long之后,果了个然,Correct!崩溃…熬夜做gcj遇到这样的结果…

当时我还稍微考虑过要不要用long long,但是答案不会益处我就没多想了….为什么当时我不用一般通用的double来写呢?为什么….

唉,google的T-shirt无缘了,但愿能积累点RP用到十几天后的百度坦克总决赛吧…

Popularity: 7% [?]

【Astar】百度之星–坦克大战

六 2nd

由shǎ崽发表在F.M.L.

8个评论

5.15校赛回来之后发现百度出现了一年一度的比赛–Astar百度之星(详情见此).而且内容很吸引人—写AI进行坦克大战.以前和朋友就讨论过这番ACM之外的趣事,程序间的PK.而且我最爱的游戏便是战棋类的,但国产单机日益衰败,更别说战旗了,早在10年前遍以几乎没有公司愿意做.(说到单机,顺便为烛龙打个广告,这个暑假国产RPG神作《古剑奇谭》与君相约.) 现在看到这”另类的战棋”,自然是非常感兴趣.

更多 >

Popularity: 9% [?]

奥拉基

五 25th

由shǎ崽发表在F.M.L.

2个评论

ACM集训告一段落,终于有时间做作业了,昨天连夜写了思想教育课上为了之前逃课多次而补偿的作业—–做一个人的报告—–奥拉基

今天上台神采飞扬的乱扯了一通,好在提前准备了几个冷笑话来热场,而且奥拉基此人较为传奇,所以老师给了我一个不错的评价(偷偷观察了下,台下的女生们注意力比老师上课的时候还集中),由于逃了三次课,所以下节课还要做一次PPT,这次老师给我的话题是–web2.0对社会带来的影响力

还不知道讲什么好,大家给给意见

Popularity: 5% [?]

近日小结

五 5th

由shǎ崽发表在F.M.L.

3个评论

从学校发了奖学金之后就没有好运过，果然RP是守恒的
/*
本来想发一段牢骚文，想想还是算了，终归是自己太弱了
*/
5.1回家几天，发现好久没运动了，去跑了一个晚上的步，结果第二天走楼梯都疼T T
整天呆着做题我的脑子已经僵化了，运动运动效果还是蛮好的

Popularity: 8% [?]

珠海之行

四 27th

由shǎ崽发表在ACM

11个评论

恩,结果我就不多说了,挺攒RP的
赛后发现最佳MM队就在我们边上,被她们虐+bs了

Popularity: 12% [?]

《难以忽视的真相》

四 19th

由shǎ崽发表在F.M.L.

7个评论

今天上课的时候看了这纪录片

地球有危险，要好好保护地球啊，不然2012就真的出现了

为了地球的安危，我决定六教七教教室晚上通宵点灯的这个重大的危机就由我来解决

Popularity: 9% [?]

12345...最后一页 »