abc378e 题解

· · 题解

本来不想打 ABC，unr 看了题，很快啊，一眼序列分治！刚好这几天写了一车序列分治板子，于是就整活写了。

题意是：对于所有子区间，求它的区间和模 P 的加和。只对区间和取模，答案不取模。

首先有简单性质：对于两个小于 P 的数，加起来也小于 2P。换句话说，把两个模后的数加起来，再取模，最多就减少一个 P。

考虑序列分治，那么区间和由在中点左边的后缀和和中点右边的前缀和组成。不妨把所有在中点右边的前缀和存起来，放到 vector 里并排序，然后枚举左端点确定后缀和。

由于刚才提到的性质，那么后缀和和前缀和凑成的区间和，要么已经小于 P，不再需要取模，要么最多只需要取模一次，也就是减掉一个 P。我们二分出第一个需要减去 P 的位置，其左边的直接加起来，右边的加起来，然后减去右边的数量个 P。

复杂度 O(n\log^2n)。

p.s. 序列分治写起来比树状数组顺手，因此抢了个自己榜上首 A。整活成功。

submission