题解 | 山峰数组计数

#include <iostream>

using namespace std;

typedef long long ll;

int main() {
	int n;
	cin >> n;
	int tmp;
	ll* sum = new ll[n + 1];
	sum[0] = 0;
	for	(int i = 1; i <= n; i++) {
		cin >> tmp;
		sum[i] = tmp + sum[i - 1];
	}
	int left = 1, right;
	if (sum[n - 1] - sum[1] <= sum[1] || sum[n] - sum[n - 1] >= sum[n - 1] - sum[1]) {
		cout << 0 << endl;
	} else {
		int l = 3, r = n;
		while (r > l) {
			int mid = (r - l) / 2 + l;
			if (sum[mid - 1] - sum[left] > sum[n] - sum[mid - 1] && sum[mid - 1] - sum[left] > sum[left]) r = mid;
			else l = mid + 1;
		}
		right = r;
		ll ans = 0;
		while (right <= n) {
			while (right <= n && !(sum[right - 1] - sum[left] > sum[n] - sum[right - 1] && sum[right - 1] - sum[left] > sum[left])) {
				right++;
			}
			ans += max(n - right + 1, 0);
			left++;
		}
		cout << ans << endl;
	}
}