DZY 's BLOG

题意：给定一个序列，每次询问左端点在[a,b]中，右端点在[c,d]中的子序列中，最大的中位数。强制在线。

前几天做到与这道题有一点点类似的。那道题是给定一个序列，求多少个子序列的中位数大于等于给定值M。

这两道题中的中位数的定义都是一样的。设序列S从大到小排序后为S[1..k]，中位数为M=S[k/2向上取整]。

那就意味着，在序列S中，大于等于M的数大于等于k/2。如果把序列S转化为T，T[i]=1(S[i]>=M),-1(S[i]<M)，则ΣT[i]一定非负。

同理，如果对于任意一个M。将序列S转化为T之后，如果ΣT[i]非负。那么这个序列的中位数一定大于等于M。

回到这道题。我们可以先考虑一个弱版：只询问一次。

有了上面那道题的经验。对于M<M'，如果发现中位数大于等于M'，那一定也大于等于M。所以有单调性，很容易就想到了二分。二分M。得到T[]。因为要求了左端点和右端点。所以，如果能在满足要求的情况下找到这一段ΣT[i..j]（i∈[a,b]，j∈[c,d]）非负，那么中位数一定就大于等于M了。所以，我们只需要求出符合要求的最大子序列和，看是不是非负即可。

感觉回到了GSS。线段树维护lmax,rmax,sum即可。因为有a<b<c<d，所以[a,b],[c,d]是互不包含的。最大连续子序列和就是[a,b]的rmax+(b,c)的sum+[c,d]的lmax。

另外n个数都是要离散化的这是必然的。二分的时候二分下标。

现在感觉已经很明了了。这样的话。二分logn。重建序列T和线段树nlogn。总复杂度是O(nlog^2n)。可以很好的解决一次询问。= =

多个询问怎么办。O(nqlog^2n)作死？其实瓶颈在这：为什么每次都要重建线段树？根本就不需要。

假设离散化的时候数值是从小到大排序的。那我们可以这么想，二分到M时，排序后的下标第1~M-1位上都是-1。第M~n位上都是1。然后还是跟上面一样的方法判定。

这就要用到函数式编程的思想。在原来的基础上不做修改，继续建树，也就是函数式线段树。

具体来说：初始的树，每个位置都是1。序列从小到大插入主席树时，修改第i棵树的时候，第i-1大的数的位置上改为-1。这样以此类推，就有n棵不同版本的线段树。

二分到M时，就在第M棵线段树上查询。可以保证此时下标为1~M-1的位置上的数都是-1。其余位置上都是1。这样就可以进行查询了。

这样就没问题了。二分logn。建函数式线段树nlogn。查询一次logn。总复杂度(nlogn+qlog^2n)。

题意：给定一颗树。询问一个子树中第k大的节点。

【终于在0:02的时候A掉了=。=】

这几天复习一下数据结构。先复习POJ2104。写可持久化线段树练手先。

然后到了这道题。其实也蛮裸的。

先求出dfs序。记录每个节点开始和结束的时间戳。然后就相当于每个点开始到结束这个区间里求第2*k大。

然后就是一个主席树了。

根据JC大神的指点结束的时间戳不用占位置了，根据下一个开始的时间戳减一就行。这样可以省一半的空间，也可以省很多时间。

由于spoj太慢加了一个read。后来一不小心就A了。速度还行吧。。