D - Petya and Array（树状数组，二分）

思路：对于 a l + . . a r a_l+..a_r al​+..ar​这种区间和问题一般都要考虑前缀差，然后问题就转化为了求 s u m [ r ] − s u m [ l − 1 ] < t sum[r]-sum[l-1]<t sum[r]−sum[l−1]<t,对等式移项 s u m [ r ] − t < s u m [ l ] sum[r]-t<sum[l] sum[r]−t<sum[l]，然后又发现是要查询有几个前缀大于当前的前缀减去t，所以用树状数组把前序的前缀存起来，这里数据是1e9，所以判断大小不能直接比大小，用到排序，比较相对大小。还有就是注意树状数组查询和添加要搞到n+1.

const int N = 2e5 + 5;
ll p[N],b[N];
ll a[N];
ll n, k;
ll tree[N];
void add(int k, int num) 
{
	for (int i = k;i <= n+1; i += i & -i)
		tree[i] += num;
 
}
ll read(int k) 
{
	ll sum = 0;
	for (int i = k;i > 0; i -= i & -i)
		sum += tree[i];
	return sum;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	int x;
	while (cin >> n >> k)
	{
 
		f(i, 1, n)scanf("%lld", &a[i]);
		f(i, 1, n)p[i] = p[i - 1] + a[i], b[i] = p[i];
		sort(p, p + 1 + n);
		ll ans = 0;
		f(i, 1, n)
		{
			int idx2 = upper_bound(p, p + 1 + n, b[i-1]) - p;
			add(idx2, 1);
			int idx = upper_bound(p, p + 1 + n, b[i] - k) - p;
			ans += read(n+1) - read(idx);//查询前序比当前大的/
		}
		cout << ans << endl;
	}
	return 0;
}