[THUPC 2024 决赛] 古明地枣的袜子 题解

[THUPC 2024 决赛] 古明地枣的袜子
先把前缀加，全局最大值转换成单点加，最大非空后缀和。
不妨先考虑所有操作的 \(x_i\) 都互不相同的情况。
对 \(a\) 序列分块，设块长 \(B=\sqrt{n}\)。
对于一个询问，如果我们已经知道了每个块内的和以及这个块内的最大后缀和，那么我们可以 \(O(B)\) 的从后往前扫每个块，然后用类似于线段树维护最大子段和的方式合并信息，得出全局的最大非空后缀和（注意：因为要求非空，所以不能随便对 \(0\) 取 \(\max\)，但这是细节问题，这里不赘述）。具体的，如果我们扫到了第 \(i\) 个块，目前的全局和是 \(S\)，最大非空后缀和是 \(maxn\)，现在要加入第 \(i-1\) 个块，假设第 \(i-1\) 个块内部的和是 \(sum_{i-1}\)，最大后缀和是 \(suf_{i-1}\)，那么就做如下更新：\(\max(suf_{i-1}+S,maxn) \to maxn,S+sum_{i-1} \to S\)。
因为修改操作的 \(x\) 互不相同，这意味着落在每个块里的修改操作只有 \(B\) 个，也就是说对于这个块来讲，本质不同的询问只有 \(O(B^2)\) 个，如果我们能对每个块预处理出这 \(O(B^2)\) 种询问对应的信息就可以在 \(O(n\sqrt{n})\) 的复杂度内回答所有询问了。

现在只需要知道如和预处理每个块要的 \(O(B^2)\) 个信息。
先把这个块内的修改按照 \(x\) 排序，然后考虑分治。
如果当前分治区间是 \([l,r]\)，我们要处理的就是在只考虑所有 \(x_i \in [l,r]\) 的修改操作时，所有的询问 \((i,j)(i