RT

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[100010];
int f[100010];
int ans=0;
int n,lf,rt;
void merge(int l,int r)
{
	if(l==r)
	{
		if(lf<=a[l]-a[l-1]&&a[l]-a[l-1]<=rt)
		{
			ans++;
		}
		return ;
	}
	int mid=(l+r)/2;
	merge(l,mid);
	merge(mid+1,r);
	for ( int i = l ; i <= mid ; i++ )
	{
//		printf("x\n");
		int rl=mid+1,rr=r;
		while(rl<rr)
		{
//			printf("y\n"); 
			int rmid=(rl+rr+1)/2;
			if(a[rmid]-a[i-1]<=rt)
			{
				rl=mid;
			}else{
				rr=mid-1;
			}
		}
		int ansr=rl;
		rl=mid+1;
		rr=r;
		while(rl<rr)
		{
			int rmid=(rl+rr)/2;
			if(a[rmid]-a[i-1]<lf)
			{
				rl=mid+1;
			 } else{
			 	rr=mid;
			 }
		}
		int ansl=rl;
		if(((a[ansr]-a[i-1])>rt)||((a[ansl]-a[i-1])<lf))
		{
			continue;
		}
		ans+=ansr-ansl+1;
	}
//	sort(a+l,a+r);
	int top=0;
	int top1=l,top2=mid+1;
	while(top1<=mid&&top2<=r){
//		printf("1\n");
		if(a[top1]<a[top2])
		{
			f[top++]=a[top1++];
		}else{
			f[top++]=a[top2++];
		}
	}
	while(top1<=mid)
	{
//		printf("2\n");
		f[top++]=a[top1++];
	}
	while(top2<=r)
	{
//		printf("3\n");
		f[top++]=a[top2++];
	}
	for ( int i = l ; i <= r ; i++ )
	{
		a[i]=f[i-l];
	}
//	printf("end\n");
}
signed main()
{
	cin >> n>>lf>>rt;
	if(lf>rt)
	{
		cout << 0;
		return 0;
	}
	for ( int i = 1 ; i <= n ;i++ )
	{
		cin >> a[i];
		a[i]+=a[i-1];
	}
	merge(1,n);
	cout << ans;
//	for( int i = 1 ; i <= n ; i++ )
//	{
//		cout << a[i] << " ";
//	}
	return 0;
 } 

个人认为这是nlogn*logn的代码，不知道为什么超时

链接：https://www.luogu.com.cn/record/114160548