本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-03 19:41:38

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

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

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

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

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

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

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

submission