CF1037 G1&G2
题意：
给定一个长为 \(n\) 的正整数序列，找出一个子段，最大化
\[\text{med}(a_l,a_{l+1},\dots,a_r)-\min(a_l,a_{l+1},\dots,a_r)
\]
其中 \(\text{med}\) 代表中位数， \(n,a_i\le 2\times 10^5\) 。
G1：
特殊性质：\(a_i\le 100\)
看到区间中位数可以套路的想到
此时中位数种类较少，可以套路地暴力枚举中位数 \(med\) ，把 \(a_i\ge med\) 的位置标记为 \(1\) ，其余标记为 \(-1\)，进行前缀和。
我们求 \(\min\) 操作是很好处理的，所以可以通过枚举最小值，然后判断当前位置是否能够包含在一段合法区间内，对于上面前缀和求出前缀的 \(\min\) ，后缀的 \(\max\)。
时间复杂度 \(O(n*V)\)
G2:
G1 的做法启示我们对于一段区间我们可以枚举该段区间的最小值，那么我们可以很自然的想到通过 主席树 来处理中位数 \(med\) 为 \(1\sim n\) 时的区间，然后通过枚举每个成为最小值的点，二分最大中位数，与 G1 相同的判断规则，时间复杂度 \(O(n\log^2 n)\)
我们考虑优化，由于当最小值逐渐递增时，为了求出最优答案，答案不可能递减，所以中位数也会随之递增，我们维护一个双指针，左端点从小到大枚举最小值，右端点不断枚举更大的中位数，我们只需要维护一棵线段树，每次中位数递增的时候进行单点修改，时间复杂度 \(O(n\log n)\)