正睿 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。（黑）