回到过去 $4$ 与回到过去 $2$ 其实大差不差

題解 - 回到过去2 - 南阳理工学院OJ (nyist.edu.cn)

双指针解法 $:$

区别是版本 $2$ 只维护了一个 $l$ ，但在 $4$ 中，由于多了一个边界，所以要维护两个 $l$ 和 $r$。 细节看代码。

#include<stdio.h>

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

long long sum[N];//前缀和，要开long long 
void solve()
{
	int n, st, ed;
	scanf("%d%d%d",&n,&st,&ed);
	
	for(int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d",&x);
		sum[i] = sum[i - 1] + x;
	}
	
	long long ans = 0;
	
	int l = 1;
	int r = 1;
	for(int i = 1; i <= n; i++)
	{
		if(l < i) l = i; //因为从第i个数开始找 l 和 r,所以 l 一定要大于 i ,这个很关键 
		while(sum[l] - sum[i - 1] < st && l <= n) l++;//维护l 
		
		if(l > r) r = l; //和上面同理，r 是要 大于 l 的 
		while(sum[r] - sum[i - 1] >= st && sum[r + 1] - sum[i - 1] <= ed && r < n) r++;//维护r 
		
		if(r > n) break; //找不到，跳出 
		
		if((sum[r] - sum[i - 1]) >= st && (sum[r] - sum[i - 1]) <= ed)
		ans += (r - l + 1);//更新答案 
	}
	
	printf("%lld\n",ans);
}


int main()
{
	int t = 1;
	
	while(t--)
	{
		solve();
	}
}

要理解每一步为什么这样做，有问题可以评论。