题解：[ABC378E] Mod Sigma Problem

首先把区间长度 $\le 2$ 的提前计算好。接下来我们只计算长度 $\ge 3$ 的区间的答案。

考虑 CDQ 分治。

```cpp
void solve(int l, int r) {
  if (r - l + 1 <= 2) return;
  int mid = l + r >> 1;
  solve(l, mid), solve(mid, r);
  // work
}
```

考虑计算左端点在 $[l, mid-1]$，右端点在 $[mid+1,r]$ 的区间的答案。

我们处理出两个数组 $a,b$（$|a|=mid-l,|b|=r-mid$），其中 $a_i = \sum\limits_{j=mid-i+1}^i A_j$，$b_i = \sum\limits_{j=mid+1}^{mid+i} A_j$。即以 $mid$ 为右端点的每一段后缀的和，和以 $mid + 1$ 为左断点的每一段前缀的和。

那么答案显然为 $\sum_{i=1}^{|a|} \sum_{j=1}^{|b|} \Big((a_i+b_j) \bmod M\Big)$。

在计算这个答案前，不妨先将 $a, b$ 中的每个元素对 $M$ 取模。不难发现这并不影响上面答案的计算。

此时 $a_i,b_j < M$。那么必然也有 $a_i+b_j < 2M$。于是：

$$
(a_i + b_j) \bmod M = \begin{cases}
a_i+b_j & a_i+b_j < M \\
a_i+b_j-M & a_i+b_j \ge M
\end{cases}
$$

于是我们可以尝试统计有多少对 $(i, j)$ 满足 $a_i+b_j \ge M$。令其为 $k$。那么答案：

$$
\begin{aligned}
\sum_{i=1}^{|a|} \sum_{j=1}^{|b|} \Big((a_i+b_j) \bmod M\Big) &= \left(\sum_{i=1}^{|a|} \sum_{j=1}^{|b|} (a_i+b_j)\right) - kM \\
&= |b|\sum a_i + |a|\sum b_i - kM
\end{aligned}
$$

于是问题变成了求 $k$。

不妨枚举 $i$。问题变成了求有多少 $j$ 满足 $b_j \ge M - a_i$。我们可以提前对 $b$ 进行排序，然后二分找到最小的这样的 $j$。two-pointers 亦可。

复杂度两只 $\log$。一个是分治，一个是排序。

正在渲染内容...