Description：

给一个有正有负的数列 $a_i$ ，求有多少个子区间和 $\le t$ 。

$1\le n \le 200000$

Solution：

由于数组有负数，所以区间右端点没有单调性，不能直接双指针做，怎么把没有单调性的变成有的，本题可以考虑分治，对于区间 $[l,r]$ ，求出所有 $i\in[l,mid]$ 到 $mid$ 的后缀和以及所有 $i\in[mid+1,r]$ 到 $mid+1$ 的前缀和丢进两个数组中排序，然后这样就有了单调性可以在两个数组中双指针扫一遍就行了。

时间复杂度 $O(n\log^2n)$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

inline ll read()

{

	register ll res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

ll m;

#define MAXN 200010

ll a[MAXN];

ll s1[MAXN],s2[MAXN];

ll ans = 0;

void solve(int l,int r) 

{

	if(l == r)

	{

		if(a[l] < m)++ans;

		return;

	}

	int mid = ((l + r) >> 1);

	ll tot = 0;

	int cur1 = 0,cur2 = 0;

	for(int i = mid;i >= l;--i)

	{

		tot += a[i];

		s1[++cur1] = tot;

	}

	sort(s1 + 1,s1 + 1 + cur1);

	tot = 0;

	for(int i = mid + 1;i <= r;++i)

	{

		tot += a[i];

		s2[++cur2] = tot;

	}

	sort(s2 + 1,s2 + 1 + cur2);

	for(int i = 1,j = cur2;i <= cur1;++i)

	{

		while(j >= 1 && s1[i] + s2[j] >= m)--j;

		ans += j;

	}

	solve(l,mid);solve(mid + 1,r);

	return;

}

int main()

{

	scanf("%d",&n);m = read();

	for(int i = 1;i <= n;++i)a[i] = read();

	solve(1,n);

	cout << ans << endl;

	return 0;

}