气死我了,改了一个小时硬是看不出问题
查看原帖
气死我了,改了一个小时硬是看不出问题
1267585
zhouyoujia2024楼主2025/1/13 21:45
#include<bits/stdc++.h>
using namespace std;
long long n,minn,maxx,ans,t;
const long long INF=1e10+10;
struct node {
	int l,r,val;
}edge[100000005];
long long a[100010];
long long L=-INF,R=INF;
void pushup(int x) {
	edge[x].val=edge[edge[x].l].val+edge[edge[x].r].val;
}
void update(int &u,long long l,long long r,long long x) {
	if(!u) u=++t;
	if(l==r) {
		edge[u].val+=1;
		return;
	}
	long long mid=l+r>>1;
	if(x<=mid) update(edge[u].l,l,mid,x);
	if(x>mid) update(edge[u].r,mid+1,r,x);
	pushup(u);
}
int ask(int u,int l,int r,int x,int y) {
	if(!u) return 0;
	if(x<=l&&y>=r) return edge[u].val;
	long long mid=l+r>>1;
	long long res=0;
	if(x<=mid) res+=ask(edge[u].l,l,mid,x,y);
	if(y>mid) res+=ask(edge[u].r,mid+1,r,x,y);
	return res;
}
int main() {
	cin>>n>>minn>>maxx;
	for(int i=1; i<=n; i++) {
		cin>>a[i];
		a[i]+=a[i-1];
	}
	int root=++t;
	update(root,L,R,0);
	for(int i=1; i<=n; i++) {
		ans+=ask(root,L,R,a[i]-maxx,a[i]-minn);
		update(root,L,R,a[i]);
	}
	cout<<ans;
	return 0;
}
2025/1/13 21:45
加载中...