1.LQP的那个题目二进制求结果确实很霸气。。。但其实还有更囧一点的办法。。
考虑一个经典问题，就是给你n个数和两个格子，每个格子只能记一个数，然后求这堆数中出现超过n/2的那个数。。
这个是可以搞出来的。。具体的说步骤是这样的，
记录 一个数a和一个计数器c。。
考虑下一个数b，如果a==b，那么c++

如果a!=b，如果c>1，那么c–，否则将a替换为b，令c为1。。。。
这个的证明是很显然的。。因为其它所有的数也不能吧这个出现次数最多的数消掉。。
所以最后的数必然是这个出现次数超过n/2的数。。
那么。。最关键的一点是。。这个是可以合并的。。
那么我们用Lca算法就可以搞出所有询问的可能的那个答案。。
然后验证。。。。

可以用Tarjan搞。。。

验证我也有一个很那啥的方法。。。具体就是对所有相同权值的点。。提取出来。。。。可以建成一棵树（可以看成忽略其他权值的点没有价值。。那么很多节点都可以缩在一起，同时有一些0权点去啊）。。可以通过dfs的办法在搞出所有这样的树。。然后离线所有询问。。可以得出每个节点在那些这样的数中第一个祖先，然后出现个数就是这两个节点的第一个祖先间长度和。。
就是Tarjan。。。

于是可以很复杂的用两次Tarjan搞定。。复杂度为O（N*a（N）），a为某函数的反函数>_<。。。。

复杂度似乎好了一点。。编写的话好像复杂了一点。。不过也不是很难写。。。。

 

2.Stone的那道有些相似的题似乎是POI2009的Lyz?我做过啊。。。

可是还是没想出来。。。太弱了T_T。。。。

 

3.JZP教主的题目似乎还有NLog^2N的算法。。。。如果树分治的话。。

关键的问题说白了就是给一些有序数组，然后求所有数的第K大。。。

这个问题。。。有一个论文算法是Log（总大小）*数组个数的。。

然后放到这个题目里面似乎就是N*LogN*LogN。。。

（。。。。。但那个算法似乎只有理论价值>_<。。。。。太BT了。。。）

 

不过也有一个比单纯的二分答案好很多的算法：
具体是维护所有有序数组的中点，
那么如果当前Kth>=Size/2。。那么最小的那个中点的前面是没用的。。删掉前面那些。。

如果Kth<Size/2。。那么最大的那个中点的后面是没用的。。。删掉后面那些。。

然后需要删Sum（Log Size[i]）次。。。
同时维护的代价是Log Log(N)。。。

Sum（Size[i]）=N。。

Sum(Log(Size[i]))=

Log(Mult(Size[i]))<=Log(N/Log N)^LogN)=

Log(N/LogN)*LogN。。。

 

Mult(S)表示集合S各个数相乘。。。。
那么复杂度就是Log(Log(N))*Log(N/LogN)*LogN。。。

比Log^3N的那个要好一点囧。。。。

@Update:lqp那题的证明：

设出现最多的数的出现次数大于一半，设其为x

令S表示一个序列，F(S)表示该序列的权值（见后面的定义），G(S)表示该序列中x的个数-不是x的数的个数。。

假设通过合并，S这个序列对应的二元组是a和c

令F(S)= c (a=x)

         -c (a!=x)

我们只需要证明F(S)>=G(S)。。

由于G(所有数)>0，故F(所有数)>0,既最后的a是x。。

使用归纳法。

首先长度为1的序列满足条件。

将S分成L和R顺次相接，

因为F(L)>=G(L),F(R)>=G(R)，

同时G(S)=G(L)+G(R)，

我们只需要证明F(S)=F(L+R)>=F(L)+F(R)即可。

考虑合并的过程，

令L对应的二元组为aL和cL，

R为aR和cR。。

若aL=x并且aR=x，那么F(S)=cL+cR满足条件

若aL和aR中有且只有一个不为x。。

那么F(S)=F(L)+F(R)满足条件。

若aL和aR都不等于x。

那么F(S)=-|cL-cR|>=-cL-cR=F(L)+F(R)。。

故归纳命题成立，由归纳法只F(S)衡大于等于G(S)。