Atcoder ARC100D Equal Cut

发现是 \(3\) 个断点且数据范围的 \(n\le 2\times 10^5\)，根据 2022CSP-S A 留下的心理阴影不难想到可以枚举中间的那个点的同时移动左右两个端点。
考虑如何移动，已知现在在枚举中间的断点 \(i\)，则现在被分为了两部分 \(1\sim i\) 和 \(i\sim n\)，因为要使极差最小，那就先可以让每一部分的极差最小。
因为这样子每个部分分出来的两个段至少比较均匀，不会出现一个特别大一个特别小的情况导致答案更大。

所以可以枚举中间断点 \(i\)，分出的两端每段都用双指针求出段中极差最小的那一个断点，此时四段极差即为当中间断点为 \(i\) 时的最优解，求出每一个 \(i\) 的最优解取 \(\min\) 即可。
对于区间和还是老套路前缀和一下就行。

时间复杂度 \(O(n)\)。

// lhzawa(https://www.cnblogs.com/lhzawa/)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
long long a[N];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		a[i] += a[i - 1];
	}
	long long ans = 0x3f3f3f3f3f3f;
	for (int i = 2, l = 1, r = 3; i <= n - 1; i++) {
		for (; l + 1 <= i && abs(a[i] - a[l] - a[l]) > abs(a[i] - a[l + 1] - a[l + 1]); l++);
		for (; r + 1 <= n && abs(a[n] - a[r] - a[r] + a[i]) > abs(a[n] - a[r + 1] - a[r + 1] + a[i]); r++);
		ans = min(ans, max({a[n] - a[r], a[r] - a[i], a[i] - a[l], a[l]}) - min({a[n] - a[r], a[r] - a[i], a[i] - a[l], a[l]}));
	}
	printf("%lld\n", ans);
	return 0;
}