使用mid=(l+r)>>1:

https://www.luogu.com.cn/record/152253983

使用mid=(l+r)/2:

https://www.luogu.com.cn/record/152253865

有没有人能解释下这是为什么。。。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int arr[100005],S[100005],cnt;
struct node{
	int cnt,l,r;
}t[6800005];
void pushup(int p){
	t[p].cnt=t[t[p].l].cnt+t[t[p].r].cnt;
}
void add(int &p,int l,int r,int val){
	if(!p) p=++cnt;
	if(l==r){
		t[p].cnt++;
		return;
	}
	int mid=(l+r)>>1;
  //mid=(l+r)/2
	if(mid>=val){
		add(t[p].l,l,mid,val);
	}else{
		add(t[p].r,mid+1,r,val);
	}
	pushup(p);
	return;
}
int query(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return t[p].cnt;
	}
	int mid=(l+r)>>1,res=0;
  //mid=(l+r)/2
	if(mid>=L&&t[p].l){
		res+=query(t[p].l,l,mid,L,R);
	}
	if(mid<R&&t[p].r){
		res+=query(t[p].r,mid+1,r,L,R);
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,l,r,rt=0,ans=0;
	cin>>n>>l>>r;
//	n=100000;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
//		arr[i]=i;
		S[i]=S[i-1]+arr[i];
	}
	add(rt,-1e10,1e10,0);
	for(int i=1;i<=n;i++){//l<=s[i]-x<=r
		int L=S[i]-r,R=S[i]-l;
		ans+=query(rt,-1e10,1e10,L,R);
		add(rt,-1e10,1e10,S[i]);
//		cout<<i<<" "<<cnt<<endl;
	}
	cout<<ans<<endl;
}