寒假的时候的一道题，原来写平衡树大数据超时。今天花了一个下午多终于搞定了，呼。。。
程序如下:
type
pp=^point; 『指针表示二叉树』
point=record
left,right:pp;
data,ldata,rdata:longint;
priority:real;
end;var
nullnode:pp;
i,j,n:longint;
total:int64;function lrotate(r:pp):pp; 『左旋』
var
tmp:pp;
begin
tmp:=r^.left;
r^.ldata:=tmp^.rdata;
tmp^.rdata:=tmp^.rdata+1+r^.rdata;
r^.left:=tmp^.right;
tmp^.right:=r;
if nullnode=r then nullnode:=tmp;
exit(tmp);
end;function rrotate(r:pp):pp; 『右旋』
var
tmp:pp;
begin
tmp:=r^.right;
r^.rdata:=tmp^.ldata;
tmp^.ldata:=tmp^.ldata+1+r^.ldata;
r^.right:=tmp^.left;
tmp^.left:=r;
if nullnode=r then nullnode:=tmp;
exit(tmp);
end;function insert(q,t:pp):pp;
var
r:pp;
begin
if q^.data〈t^.data then
begin
if t^.left〈〉nil then
begin
total:=total+t^.rdata+1; 『往下沉的时候，父节点及父节点右边的都比它大』
inc(t^.ldata);
t^.left:=insert(q,t^.left);
end
else
begin
inc(t^.ldata);
total:=total+t^.rdata+1;
t^.left:=q;
end;
r:=t^.left;
if r^.priority〈t^.priority then t:=lrotate(t);
exit(t); 『最后要记得返回值』
end
else
begin
if t^.right〈〉nil then
begin
inc(t^.rdata);
t^.right:=insert(q,t^.right);
end
else
begin
t^.right:=q;
inc(t^.rdata);
end;
r:=t^.right;
if r^.priority〈t^.priority then t:=rrotate(t);
exit(t);
end;
end;procedure deal(x:longint);
var
p:pp;
begin
new(p);
p^.data:=x;
p^.priority:=random;
p^.left:=nil; p^.right:=nil;
p^.ldata:=0; p^.rdata:=0;
if nullnode=nil then nullnode:=p
else nullnode:=insert(p,nullnode);
end;begin
assign(input,'inverse.in'); assign(output,'inverse.out');
reset(input); rewrite(output);
readln(n);
nullnode:=nil;
randomize;
total:=0;
for i:=1 to n do
begin
read(j);
deal(j);
end;
writeln(total);
close(input); close(output);
end.
前面调了很久都没有过，直到后面把过程改为了函数后就ok了。
Treap维护堆性质的方法用到了旋转，这里先简单地介绍一下。Treap只需要两种旋转，这样编程复杂度比Splay等就要小一些，这正是Treap的特色之一。
插入
给节点随机分配一个优先级，先和二叉排序树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是跟的左儿子就右旋如果当前节点是跟个右儿子就左旋。
我们如果把插入写成递归形式的话，只需要在递归调用完成后判断是否满足堆性质，如果不满足就旋转，实现非常容易。
由于旋转是
的，最多进行h次(h是树的高度),插入的复杂度是
的，在期望情况下
，所以它的期望复杂度是
删除
有了旋转的操作之后，Treap的删除比二叉排序树还要简单。因为Treap满足堆性质，所以我们只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。
删除最多进行次旋转，期望复杂度是。
查找
和一般的二叉排序树一样，但是由于Treap的随机化结构，可以证明Treap中查找的期望复杂度是。
分离
要把一个Treap按大小分成两个Treap，只要在需要分开的位置加一个虚拟节点，然后旋至根节点删除，左右两个子树就是得出的两个Treap了。根据二叉排序树的性质，这时左子树的所有节点都小于右子树的节点。
时间相当于一次插入操作的复杂度，也就是
合并
合并是指把两个Treap合并成一个Treap，其中第一个Treap的所有节点都必须小于或等于第二个Treap中的所有节点，也就是分离的结果所要满足的条件。合并的过程和分离相反，只要加一个虚拟的根，把两棵树分别作为左右子树，然后把根删除就可以了。
时间复杂度和删除一样，也是期望
转自：nocow.cn
From yesterday until today morning, after nearly 8 hours, my computer has downloaded the numb3rs using the emule. Yes, I must say that I was certainly influenced by M67. However, the first one is pretty good.
What really suprised me is the serious classification in the U.S. They don't check the whole season play cursorily but check every play!
I especially like the following picture:
Tags: numb3rs
我不知道自己是否是多少有几分跟达尔文过不去，不过我只是想说说我的看法。
（一）关于物竞天择
我曾经被无数人无数次重复的所谓物竞天择理论所麻痹，也相当长一段时间未曾怀疑其正确性：认为这是进化论所导出的理所当然的公式。然而，最近却发现达尔文曾在他的一本书中写道自己对于自己的进化论别有用心的种族主义者的看法——认为多少有几分荒谬。
最初也不曾在意。
几日后自己在历史课上却又思考起来了，在关于邓人比黄花瘦小玉枕纱厨平以及真理大讨论时候，我脑子里突然迸发出一个想法：人类由于不能证明其自身在某阶段其理论和行为的正确性，所以在偶然的情况下不自觉的意识到某时刻真正正确的理论可能存在于当时被认为想法荒谬乃至错误的人身上。物竞天择是不二的自然法则，如同一种存在于万物间的化学平衡般，人类的偶然行为却使得这种平衡破坏。打个俗一点的比方，自然法则如同经济学里的市场经济中的价值规律，起着基础性的作用，它有着其固有的盲目性，人类在某种程度上制止了这种盲目，使得人类能够借此从外物中脱颖而出。可以说，医药的发明，社会保障的建立，以及对贫困人口的救助并不是某些种族主义者所认为的阻碍人类发展，相反的，这些都是想当必要的。
历史上有不少所谓的异类在最后都能得到平凡，并且得到后人的称赞、学习、敬仰。先秦的孔子，这些可以佐证我理论的事例可谓举不胜举，我再次就不多赘言了。
（二）退化论
如今的人类（特别是都市人）多少有几分厌倦现代生活的所谓科学，所谓的变化，渴望回归，渴望真正的田原、乡间生活。我便又有了一个想法，人类有退化的趋势，即想原始生活方向变化的趋势。从人变猿，从猿变猴，然后逐渐的变为单细胞生物，然后有一次经历轮回（也有可能就是单方向）。
不过我得说，这理论（第二个）多数是出于我的一些回归自然的浪漫情怀，一没论据，二没精彩的叙述，我也并没有认真思考多少。
Tags: thinking
DP题，但是想了好一阵子（大大的菜一下-_-|||）。
最终要求的是情况数，很容易想到要DP：
1.状态：
最终是求n个元素构成的两个集合相等的情况，这种情况肯定是从n-1个元素演变过来的，而且刚好是从n-1个中两个元素差为±n变来，于是可用f[i,j]表示前i个元素，差为j的情况数。
然而再一分析就可得知，若以±n来计算势必会浪费不少时间和空间，因为为n或-n的情况正好对称，于是可以将±n变为n(以n来表示-n）。
2.动态转移方程
显然：f[i,j]=f[i-1,|j-i|(将负的转为正的计算)]+f[i-1,j+i]，最终结果为(f[n,0]/2)。
3.思考：j的取值范围
想是很麻烦，其实只需要首先将j的范围弄大点就可以watch出大概范围。
完整代码：subset
Tags: usaco
Starcraft2! It's just unbelivable, hardly can I imagine that it would be possibly release in a year or two. And I bet not, Coz it's so hard to keep the balance among the races. Blizzard must be under a lot of pressure obviously.
More info, click here.
Tags: games, starcraft2
Minutes to Midnight 想要表达出的其实就是『世界末日钟（Doomsday Clock）』的概念！『世界末日钟』是源自于美国二次世界大战时期，当美国在日本长崎及广岛投下两颗原子佳节又重阳弹之后，在1974年由一群芝加哥大学研究原子 科学的科学家们所一起创立的概念。科学家们以『世界末日钟』这个虚拟的定时器，来警惕人类将因过度使用核武，而导致自我灭亡。而"Midnight" 午夜，所代表的就是灭亡时刻。在二次世界大战之后，由于核武疯狂急速地发展，世界末日钟的时针一度被推进到距离代表世界末日的午夜不到15分钟的时间，甚 至在1960年代美苏冷战、核武竞争时期，时针还曾被推进到只剩3分钟(11点57分)。而目前在经过前前后后18次调整之后，在核武、天气异常、及环境 污染的影响之下，世界距离毁灭的午夜时分也只剩五分钟的时间。
主唱查斯特表示：「创立这个末日钟的目的就是要提醒世人，虽然人类拥有巨大力量，但当这股毁灭性力量反扑之时，我们都该仔细思考这股威力带来的严重影响， 转眼之间世界末日已进入倒数计时.「Linkin Park」刚出道时，即使是最年长的团员：主唱查斯特也只有23岁，他承认这种极具争议性的主题，在几年前「Linkin Park」是完全不会触及的，但现在的「Linkin Park」却认为它跟我们息息相关。这张专辑所比喻的「午夜」的概念，不单单只有指涉地球遭到人类破坏的这种巨观层面，同时也映像出Linkin Park自我的微观层面。「午夜」所代表的『终结』同样也呼应Linkin Park在音乐上面的改变，因为所有和Linkin Park一同成长的信徒们，将在这张最新专辑里发现Linkin Park的全新面貌，过去大家所熟悉的Linkin Park将毁灭消失，Linkin Park将以崭新姿态解构重生。
单曲《What I've Done》以蒙太奇的手法，将近半世纪在地球上发生过足以影响所有人类、动物、植物生存权的大件事记录下来，包括：政治的纷乱、种族冲突造成无谓的战争杀 戮、环保意识不彰造成自然生态崩解、百年冰川消融、北极熊等珍贵的生物濒临绝种、人类面对世纪末的仓皇不安，以吸毒等极端的手段暂实逃离现实等等。
Tags: linkin park