0/10

AGC028

AGC028E - High Elements code

请先思考后再展开

为了方便我的实现改为考虑更小的元素；设E集合为全局的前缀最小值

考虑逐位确定，那么我们需要判断的就是可行性，$设前面i个已经填完，前面的mi_0,mi_1，前面的长度c_0,c_1，后面的前缀最小值个数cnt$

对于两个集合只考虑下降部分，因为其他数总是至少有一种让它没用的分配方案（每个数丢到左边第一个更小的数所在集合即可）

将元素分为来自E的A类、其他B类，那么能等效地转化为至少一个集合的下降是只有A类的（设为集合0）

$c_0+cnt-a=c_1+a+b即2a+b=c_0-c_1+cnt$ 即要求存在一个「开头<mx，满足权值（A贡献2，B贡献1）为定值」的下降序列

因为一定能$a–$，所以对于某个奇偶性求最长的即可，考虑一个维护前缀max的支持撤销树状数组，询问也是前缀

从后往前插入元素来维护$f(num)$表示以num为开头的最长下降子序列，插入就是一个链修改，因为端点一直往后移动，这种东西是可以撤回的

时空复杂度 $O(nlogn)$