【jzoj2902】【集训队互测 2012】【Middle】【可持久化线段树】

题目大意

一个长度为 n 的序列 a ，设其排过序之后为 b ，其中位数定义为 b[n/2] ，其中 a,b 从 0 开始标号 , 除法取下整。

给你一个长度为 n 的序列 s 。回答 Q 个这样的询问 ： s 的左端点在 [a,b] 之间 , 右端点在 [c,d] 之间的子序列中 ，最大的中位数。

其中a<b<c<d$a<b<c<d$。

位置也从 0 开始标号。

我会使用一些方式强制你在线。

解题思路

考虑求一个区间里的中位数，我们会二分答案，检查大于等于答案减小于答案的个数，如果大于等于0答案就有可能更大，越大答案就越大。那我们发现[b+1,c-1]一定要取，[a,b]取右数最大值，[c,d]取左数最大值，加起来就可以调整答案。

假设当前答案为x，那我们把大于等于x的位置都标为1，小于的位置标为-1就可以用线段树维护以上信息。我们发现不同的答案只有n个，我们对每一个x都维护一颗线段树即可，发现相邻两个x不同权值的位置有一个，那我们可以按x的大小顺序建线段树，利用之前的信息就可以快速求出当前线段树，用可持久化线段树即可。

code