SPOJ QTREE3

这个变态题目。。有N种做法。。能AC的MS不多囧。。
做法系列1:
思路:从下往上对每个节点维护一个平衡树,然后用平衡树来回答第K大大问题
A:平衡树+启发式合并,两颗平衡树合并直接暴力把小的插进大的。。每个最多被插LogN次。。总共就是O(NLogN^2+QLogN)。。极难AC。。我Treap TLE,SBT也TLE。因为我SBT写得太烂了。。
B:Splay合并,Splay可以做到在O(NLogN)完成合并。。然后Splay常数较大,还是TLE。。。
C:注意题目的特性。。首先就是Q比N小很多,就是说许多结点都不需要维护平衡树,先先序遍历这个树,然后一些节点要插入的话直接用先序遍历中的区间插入。。再设个常数如果一个节点中最大的子树实在太小的话插入也麻烦干脆直接重新建个平衡树好。。估计可以勉强AC。。不过可能很困难吧。。我一直觉得可能可以弄个阀值仿照IOI2009的Region搞出来。。不过很麻烦。。
做法系列2:
思路:从小到大加入每个数,对每个节点维护还需要+几个数就可以输出了。。然后每次都可以取路径中的最小值,如果是0的话就输出,然后变成下一个。。一个节点显然只能影响的它的所有祖先。。所以需要维护路径。。
A:维护路径,还要最小值,直接上动态树,我的动态树写得太烂了。。无法AC。。。
B:维护路径也可以树链剖分啊,还是TLE。。。
做法系列3:
思路:TMD,干脆忽略这个树直接上区间K大值的算法好了,当然要先先序遍历一下了。。
A:一般的先二分在用线段树的做法肯定TLE O(NLogN+QLogN^3)..
B : 有一种二分树就是对所有权值建树,然后每个节点储存当前权值区间中的所有数在序列中的位置。。那么可以LogN得到节点区间中L到R之间的树的个数,就可以在LogN^2完成2分了。。写的好一点可以AC。。。
C:还有一种很NB的划分树,可以在NLogN+QLogN的时间解决问题。。非常NB啊。。具体看www.notonlysuccess.com/ 还不会写哎。。不过应该可以AC。。。

8 thoughts on “SPOJ QTREE3

  1. orz!!本菜看着spoj上交的人的速度都很快啊,本菜用划分树硬生生卡着时限过了排在最后。不知道神牛有没有什么快速的离线算法之类的。

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>