正睿 CSP 7 连测
终于 ak 了一场。
D
给定长度为 \(n(n \le 2 \times 10^5)\) 的序列 \(a(|a_i| \le 10^9)\)。若 \(a_i < 0\),\(b_i = -2^{-a_i}\);否则,\(b_i = 2^{a_i}\)。求 \(b\) 的最大子段和对 \(998244353\) 取模的结果。
令 \(f_i\) 表示以 \(i\) 结尾的子段最大值,\(f_i = \max\{f_{i - 1} + b_i, 0\}\)。\(ans = \max\limits_{i = 1}^n f_i\)。
如果直接维护 \(f_i, ans\),需要维护 \(+, -, \max\)。有一个比较粗暴的主席树做法:\(+\) 为找到第一个不比 \(b_i\) 低的位置,然后进行区间修改,\(-\) 同理。而 \(\max\) 操作可以维护 \(hash\) 值做(比较时若右半部分相同则比较左半部分,否则比较右半部分)。但是巨难写,且时空的常数都巨大,幸好出题人没卡。(硬刚 \(2.5h\) 才过)。
而另一种更简单做法是维护 \(f_i, ans - f_i\)。这样就只有对 \(0\) 取 \(\max\) 的操作,使用 ODT 维护连续 \(01\)段,\(+, -\) 运算暴力 lower_bound
的一下,然后暴力修改即可。
时间复杂度 \(O(n \log n)\)
早该想到 S 组模拟赛不会有主席树这种变态玩意的。这个题将 \(\max\) 操作简化后就十分好做了。
CF464E,这个题只能主席树,因为需要 dij
。(黑)