此题做法与回到过去2的主要差别在于加入了递归的思想。若还未完全理解二分的写法请跳转回到过去2的题解，先充分理解 $wanan$ giegie讲的二分的思想再继续。

本题直接二分查找的话由于加入了负数，故不能保证后面的区间都满足条件。不妨先取区间中间值：

由此把子区间 $[ l, r ]$ 分为以下三类：

1. $L \leq l \leq r \leq Mid$

   

2. $Mid < l \leq r \leq R$

   

3. $L \leq l \leq Mid, Mid < r \leq R$

   

先忽略1、2类区间，重点考虑如何快速解决第三类区间。

预先求出前缀和，方便区间求和：

scanf("%d %lld", &n, &k);
for(int i = 1; i <= n; i++)
{
	scanf("%lld", &a[i]);
	h[i] = h[i - 1] + a[i];//预处理前缀和
}

将第三类区间以 $Mid$ 为界分成左右两个区间，此时只需将所有的右区间全部求和后排序：

int cth = 0;
for(int i = mid + 1; i <= r; i++)
	rh[cth++] = h[i] - h[mid];//记录右半部分和
sort(rh, rh + cth);//排序

再遍历左区间起点 $l$ ，每次经过一左区间时先计算出左区间和，由此得出欲满足条件则右侧区间最小的和，在记录右侧区间和的数组中二分查询即可求出起点为 $l$ 且满足条件的区间个数。第三类区间解决。

for(int i = l - 1; i < mid; i++)
{
	long long lh = h[mid] - h[i];//左半部分和
	long long fd = k - lh;//满足条件的右侧部分最小和
	int l1 = 0, r1 = cth - 1;
	if(rh[r1] >= fd)//确保存在大于fd的元素
	{
		while(l1 < r1)//二分查找第一个大于fd的元素下标
		{
			int miid = (l1 + r1) / 2;
			if(rh[miid] >= fd)
				r1 = miid;
			else
				l1 = miid + 1;
		}
		ans += cth - l1;//满足条件的区间个数
	}
}

余下的第1、2类区间可以通过递归的方式解决

完整代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int n;
long long k, ans;
long long a[200010];//原数组
long long h[200010];//前缀和数组
long long rh[200010];//记录数组

void solve(int l, int r)
{
	if(l == r)//单点判断后返回
	{
		if(a[l] >= k)
			ans++;
		return;
	}
	int mid = (l + r) / 2;
	solve(l, mid);//递归解决左侧区间
	solve(mid + 1, r);//递归解决右侧区间
	int cth = 0;
	for(int i = mid + 1; i <= r; i++)
		rh[cth++] = h[i] - h[mid];//记录右半部分和
	sort(rh, rh + cth);//先排序后二分
	for(int i = l - 1; i < mid; i++)
	{
		long long lh = h[mid] - h[i];//左半部分和
		long long fd = k - lh;//满足条件的右侧部分最小和
		int l1 = 0, r1 = cth - 1;
		if(rh[r1] >= fd)//确保存在大于fd的元素
		{
			while(l1 < r1)//二分查找第一个大于fd的元素下标
			{
				int miid = (l1 + r1) / 2;
				if(rh[miid] >= fd)
					r1 = miid;
				else
					l1 = miid + 1;
			}
			ans += cth - l1;//满足条件的区间个数
		}
	}
}

int main()
{
	ans = 0;//初始化ans
	scanf("%d %lld", &n, &k);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		h[i] = h[i - 1] + a[i];//预处理前缀和
	}
	solve(1, n);//从整个区间开始
	printf("%lld", ans);
	return 0;
}