2019牛客暑期多校训练营（第三场）G Removing Stones

题目链接
大意：给你一个数组，让你求出有多少个合法的区间。
合法区间定义为：每次选择两个元素同时减1，若能都减为0即为合法，特别的，如果区间和为奇数时，可以选择一个值最小的使他减1.
思路：转换一下问题就是，让你求多少个区间，使得区间的最大值不大于区间和的1/2，（向下取整）。
那么我们可以分治做，先跑一个rmq，记录最大值下标，然后分治一个区间，每次分治的区间，先求出他的最大值下标，然后扫小的那一边，再二分另一边的最大/最小范围，然后统计答案即可。
细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define LL long long
#define SZ(X) X.size()
#define pii pair<int,int>
#define ALL(X) X.begin(),X.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 3e5 + 11;
int t, n, a[N];
LL sum[N], pre[N];
int dp[N + 33][35];
LL ans = 0;
void RMQ() {
	for (int i = 1; i <= n; i++) dp[i][0] = i;
	for (int i = 1; (1ll << i) <= 1000000000; i++) {
		for (int j = 1; j + (1ll << i) - 1 <= n; j++) {
			dp[j][i] = a[dp[j][i - 1]] >= a[dp[j + (1 << (i - 1))][i - 1]] ?
			           dp[j][i - 1] : dp[j + (1 << (i - 1))][i - 1];
		}
	}
}
int lg[N + 3];
void init() {
	lg[0] = -1;
	for (int i = 1; i < N; i++)lg[i] = lg[i >> 1] + 1;
}
int get(int L, int R) {
	int k = lg[R - L + 1];
	int Mid = (a[dp[L][k]] >= a[dp[R - (1 << k) + 1][k]] ? dp[L][k] : dp[R - (1 << k) + 1][k]); //最大值下标
	return Mid;
}
void slove(int l, int r) {
	if (l >= r)return;
	int k = get(l, r);
	if (k - l <= r - k) {
		for (int i = l; i <= k; i++) {
			int L = (i == k ? (k + 1) : k), R = r;
			int ANS = -1 ;
			while (L <= R) {
				int mid = L + R >> 1;
				if ((sum[mid] - sum[i - 1]) / 2 < a[k])L = mid + 1;
				else R = mid - 1, ANS = mid;
			}
			if (ANS != -1)ans += r - ANS + 1 ;
		}
	} else {
		for (int i = k; i <= r; i++) {
			int L = l, R = (i == k ? (k - 1) : k);
			int ANS = -1 ;
			while (L <= R) {
				int mid = L + R >> 1;
				if ((pre[mid] - pre[i + 1]) / 2 < a[k])R = mid - 1;
				else L = mid + 1, ANS = mid;
			}
			if (ANS != -1)ans += ANS - l + 1;
		}

	}
	slove(l, k - 1);
	slove(k + 1, r);
}
int main() {
	init();
	for (scanf("%d", &t); t; t--) {
		scanf("%d", &n);
		pre[n + 1] = 0;
		for (int i = 1; i <= n; i++)scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];
		for (int i = n; i >= 1; i--)pre[i] = pre[i + 1] + a[i];
		RMQ();
		ans = 0;
		slove(1, n);
		printf("%lld\n", ans );
	}
	return 0;
}