【学习笔记】[ARC150F] Constant Sum Subsequence

第一眼看上去，这道题一点都不套路

第二眼看上去，大概是要考$dp$优化，那没事了，除非前面$3$道题都做完了否则直接做这道题肯定很亏

首先我们要定义一个好的状态。废话

设$f_s$表示$B$序列的和为$s$时，能达到的$A$序列的最大长度，也就是最紧的限制。

这一步定义非常自然，到这里都没有任何问题

不过直接暴力转移复杂度$O(S^2\log n)$，考场上好像只能得到$20pts$。

似乎有根号乱搞的做法，但是这道题$n$,$S$比较大所以会被卡掉

这是逼着我们想正解啊

不管了，根号乱搞比较好想，而且确实也是考场上性价比最高的做法

$\text{cdq}$分治的想法挺阳间的，应该可以学一下

乱胡一下吧，不过考场上可能我也不会写 考虑计算区间$[l,r]$的$dp$值，显然我们知道转移的这个数不会超过$[l,r]$这个区间的长度。

发挥$\text{bot}$的能力 我们有转移式$f_s={\max }_{x\le s}\text{nxt}(f_{s-x},x)$，并且$f_s$是单增的，因此$\forall i\in [mid+1,r],f_i>f_{mid}$。先枚举一个$x$，则我们只需要考虑可能对右区间有贡献的$s$，即满足$\text{nxt}(f_s,x)=\text{nxt}(f_{mid},x)$。不难猜想，这些$s$ 形成了一个区间，并且这个区间的左端点就是最小的$i$满足$f_i\ge \text{front}(f_{mid},x)$，于是对于这个区间，贡献是相同的，而对应的右半部分下标是连续的，因此用一个线段树维护即可。

复杂度两个$\log$。应该可以通过吧？

代码先咕了