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

首先发出题目链接：
链接：https://ac.nowcoder.com/acm/contest/883/G
来源：牛客网
涉及：ST表，分治

点击这里回到2019牛客暑期多校训练营解题—目录贴

题目如下


代码如下

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3e5+5;
int st[maxn][25];
int n, cas;
ll ans = 0;
ll a[maxn], sum[maxn];
int lg[300005] = {-1};
void init(){for(int i = 1; i <= n; i++){st[i][0] = i;} for(int j = 1; (1 << j) <= n; j++){for(int i = 1; i + (1 << (j-1)) <= n; i++){st[i][j] = (a[st[i][j-1]] > a[st[i+(1<<(j-1))][j-1]])? st[i][j-1]: st[i+(1<<(j-1))][j-1];}}
}
int query_max_place(int l, int r){int k = lg[r-l+1];return (a[st[l][k]] > a[st[r-(1<<k)+1][k]])? st[l][k]: st[r-(1<<k)+1][k];
}
void dfs(int L, int R){if(L >= R)   return;int k = query_max_place(L, R);if(R + L > 2 * k){for(int i = L; i <= k; i++){if(a[k] > ((sum[R] - sum[i-1]) >> 1))  break;int l = k, r = R;while(l < r){int mid = (l + r) >> 1;if(a[k] > ((sum[mid] - sum[i-1]) >> 1)){l = mid + 1;}else    r = mid;}ans += 1ll * (R - l + 1);}}else{ for(int i = R; i >= k; i--){if(a[k] > ((sum[i] - sum[L-1]) >> 1))  break;int l = L, r = k;while(l < r){int mid = (l + r + 1) >> 1;if(a[k] > ((sum[i] - sum[mid-1]) >> 1)){r = mid - 1;}else    l = mid;}ans += 1ll * (l - L + 1);}}dfs(L, k-1);dfs(k+1, R);return;
} 
int main(){for(int i = 1; i <= 300005; i++) lg[i] = lg[i/2] + 1;cin >> cas;while(cas--){ans = 0;scanf("%d", &n);for(int i = 1; i <= n; i++){scanf("%d", &a[i]);sum[i] = sum[i-1] + a[i];} init();dfs(1, n);cout << ans << endl;}return 0;
}