75+100+35=210 rk2

T1

直接比较 \(a_{i-1}\) 和 \(a_i\)

如果 \(a_{i-1} < a_i\)限制了x的在他们的最高不同位必须是0

如果 \(a_{i-1} > a_i\)限制了x的在他们的最高不同位必须是1

分位考虑，开两个桶记录，直接暴力修改即可

时间复杂度:\(O(30n)\)

T2

暴搜优化

T3

55->35

没看见有个挡\(l_{max}<=200\)自己卡自己，少了20分

一个朴素的想法，设\(dp_i\)表示\(A_{1...i}\)的最小代价，转移就从前面\(dp_j(j<i)\) 转移，加上\(A_{j+1...i}\)的最小代价

关于最小代价，可以把B插入trie树，每个点记录min_c

时间复杂度:\(O(nl_{max})\)

考虑另一种转移：

枚举前后缀转移，考虑一个固定的\(?_?\)，如果\(?_? [:−?]\)是\(?[:?]\)的后缀，则可以以代价\(?_?\) 从\(??[?−?]\rightarrow ??[?]\)。同理，如果\(?_? [:?]\)是\(?[?:]\)的前缀，则可以以代价\(?_?\)从\(??[?]\rightarrow ??[?+?]\)。

我们发现每一段\(?\)都满足二分性质，在前后缀分别求出\(?\)的合法范围，用线段树转移，复杂度\(?(?? log⁡?+?)\)

将长度大于?的用方法1，其余的用方法2，总复杂度为\(?(? \frac{?}{?} \log ⁡?+??)\)。
令\(?=?(\sqrt{? \log ⁡?})\)，总复杂度为\(?(?\sqrt{? \log ⁡? })\)