E题 | 智乃的最大子段和取模

解题思路：

为了 求解区间和，本题需要先求前缀和并取模。用 表示区间 的和取模 。

在固定右端点 的情况下，要想让区间和 最大， 有两种可能取值：

• 要么尽可能小，要么刚好比 大一点点（此时减为负数，需要加上一个p）。

先说结论：对于每个 ，只需找第一个大于 的 。若不存在，再退而求其次用最小的 。

为什么前者比后者更优呢？下面给出证明：

定义 表示区间 的和取模 。

证明：有 时，它一定不比 差

设 = 最小的 （结果为 ）， = 全局最小的 （结果为 ）。

因为 ，所以 ，恒成立

关于查找第一个大于某某的某某，可以联想到用二分查找。因此可使用 或者 这种自带二分查找的容器存储每个位置的前缀和，按照前缀和排序。

示例代码：

int mx = -1, L, R;
void solve() {
	int n, p;
	cin >> n >> p;

	map<int, int> mp; // sum,i
	mp[0] = 0;

	int pre = 0;
	for (int i = 1, x; i <= n; i++) {
		cin >> x;
		pre = (pre + x) % p;

		auto it = mp.upper_bound(pre);
		if (it == mp.end()) it = mp.begin();

		auto &[lst, j] = *it;
		int sum = (pre - lst + p) % p;
		if (mx < sum) {
			mx = sum;
			L = j;
			R = i - 1;
		}
		mp[pre] = i;
	}

	cout << L << ' ' << R << ' ' << mx << endl;
}