回到过去 $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();
	}
}

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

确实大差不差

二分解法：

#include<stdio.h>

long long a[200010];
long long h[200010];

int main()
{
	int n;
	long long mi, mx, ans = 0;
	scanf("%d %lld %lld", &n, &mi, &mx);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		h[i] = h[i - 1] + a[i];//前缀和计算
	}
	for(int i = 1; i <= n; i++)
	{
		int l1 = i, r1 = n;
		if(h[r1] - h[i - 1] >= mi)
		{
			while(l1 < r1)//二分查大于等于最小边界值有多少个区间
			{
				int miid = (l1 + r1) / 2;
				if(h[miid] - h[i - 1] >= mi)
					r1 = miid;
				else
					l1 = miid + 1;
			}
			ans += n - l1 + 1;//ans加上这些区间个数
			l1 = i, r1 = n;
			if(h[r1] - h[i - 1] > mx)
			{
				while(l1 < r1)//二分查大于最大边界值有多少个区间
				{
					int miid = (l1 + r1) / 2;
					if(h[miid] - h[i - 1] > mx)
						r1 = miid;
					else
						l1 = miid + 1;
				}
				ans -= n - l1 + 1;//ans减去这些超出最大值的区间个数
			}
		}
	}
	printf("%lld", ans);
	return 0;
}