AGC021到030

AGC021到AGC030题解合集

AGC的题面一般都不难懂,就不给出翻译了

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)$

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/919438ff.html
转载请注明出处,谢谢!