这是一篇题解

<----------------------------------------------------->

Codeforces 963 div2 D

比赛链接：https://codeforces.com/contest/1993
原题链接：https://codeforces.com/contest/1993/problem/D
代码链接：https://codeforces.com/contest/1993/submission/274883256

题目大意： 对于一个长度n的数组a,删去若干次长度为m的连续区间，直到该数组长度<=m
最大化最终剩余数组中最大的中位数

题目等价于 <=> 以下命题 ：
从原数组中寻找一个子序列L = {Al0,Al1,Al2, … ,Alnn-1}
其中 nn为最终需要选的数的个数, l0 ~ lnn-1 为 0 ~ nn-1
即 li % m = i, li < li+1,
0 <= i < nn,1 <= nn <= m
并且若对原数组中每个数的下标 %m ,得到 0 1 2 0 1 2 0 1 2 …
手玩一下即发现 就是选择 从 0 ~ nn-1 的一段子序列 L

我们发现以下二分性质 ：
(1) L 有 >= lim 的中位数 => L 中有 >= (nn + 1) / 2(上取整)个 >= lim 的数

该条件符合二分性质

lim 越小，越符合，反之

代码实现：
对于每个 lim,每次把 a 中 i%m < nn && a[i] >= lim 的数的下标 %m 后加入到
pos数组中，对pos数组求最长严格上升子序列，最长 len >= (nn + 1) / 2(上取整) ?

(此处求最长上升子序列，可以用树状数组实现)

附上代码
https://codeforces.com/contest/1993/submission/274883256
不知道为啥上传不了png图片,自己去翻链接吧