superbt — 超级bt的题目

Posted on 三月 22nd, 2008.

这道题简直把平衡树的BT程度发挥到了极致…
上次写WA了,这次先是WA,然后RE201,然后RE215(这个东西…最后确认是某个节点的father是它自己,然后不断的把size增大…就溢出了),最后AC.还有比较囧的,我的程序一度无法编译…后来发现是因为数组开的太大,到了几百M.似乎object里面的这个错误检查不出?
这道题其实也很简单了,题目描述都不用发,注释里都写的很清楚了…不过考到了平衡树的所有操作.里面删除大于等于k的所有数,似乎Splay最简单…然后还有Treap据说也可以和Splay一样做,别的平衡树都要一个一个删.我这个程序就是Splay的…效率不错.
虽然AC了也很恶心…因为用了object…所以400+行…不过object在那些并查集+平衡树啊,线段树套平衡树啊,还有我一直没做的线段树+LCA之类的题目中还是挺有用的,至少过程不会混淆了.
{ superbt - sqybi’s code - Splay - delete出错:   “if son[1, y] <> 0 then father[son[1, y]] := z;”   写作   “if son[1, y] <> 0 then father[son[1, y]] := son[1, z];”}{$APPTYPE CONSOLE}//for my winstyprogram superbt_sqybi;  const    fin = ’superbt.in’;    fout = ’superbt.out’;    nn = 10000000;    unable = 100000000;
  type    TSplayTree = object      private        root, […]