2019牛客多校 第三场 G.Removing Stones

对于已知长度为n的数组选取一个区间，所有的区间的选法为n*(n+1)/2。

这是我们所有能过选取的区间个数，对于所有点区间我们固定其端点为i为最大，右端点为r，对于不满足的即为ans -= (r-i+1) ,即为区间i-i ,i-i+1,......,i-r。均为不满足的区间。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 300005
int n,m;
ll a[maxn];
  
int main()
{
    int t;
    ll sum;
    ll l,r;
    ll ans;
    scanf("%d",&t);
    while(t--){
    	scanf("%d",&n);
    	ans= (ll)n*(n+1)/2;
    	for(int i=1;i<=n;i++){
    		scanf("%lld",a+i);
		}
		for(int i=1;i<=n;i++){
			sum=0,l=r=i;
			while(l>1 && a[i] > sum + a[l-1])  l--,sum+=a[l];
			while(l<=i){
				while(r<n && a[i] > sum + a[r+1]) r++,sum+=a[r];
				ans -= (r-i+1);
				sum -=a [l];
				l++;
			}
		}
		printf("%lld\n",ans);
	} 
}