二分+主席树

个人感觉这道题非常好，思维难度高，代码好写(然而自己写的时候神志不清，转态全无qwq)

首先要知道一个关于中位数的基本套路，将大于等于它的赋值成1，小于它的赋值成-1

然后通过区间和就能找出中位数了

对于本题来说：

首先显然答案满足单调性，因为二分的是第k大的数，所以1,-1这个序列和肯定是单调变化的

其次我们考虐将[a,b],[c,d]区间转化成[a,b],(b,c),[c,d]

所以我们只需查询[a,b]中的最大右连续子段和(必选一个)，(b,c)的区间和，[c,d]的最大左连续子段和(必选一个)

若这三个和>=0，则说明当前二分的第k大的数是ok的，否则不行，然后继续二分

对于维护每个数作为中位数时的1,-1序列，我们用主席树维护一下就ok了

效率:O(n(logn)^3)