MLE 80求助
查看原帖
MLE 80求助
523864
paradoxxd楼主2022/4/8 11:24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define push_back emplace_back
#define ull unsigned long long
#define pii pair<int,int>
/*
 * theFileCreatedAt_2022-04-08_10:31_ *
 * 只有结束的时候才会结束
 */
ll read(){
	ll w=1,q=0;
	char ch=' ';
	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
	if(ch=='-') w=-1,ch=getchar();
	while(ch>='0'&&ch<='9') q=(ll)q*10+ch-'0',ch=getchar();
	return (ll)w*q;
}
const int maxn=1e5+19;
long long s[maxn];
//multiset<long long>mts;
struct{
	int l,r,val;
}st[maxn*40];
int cnt;
inline void pushup(int rt){
	st[rt].val=st[st[rt].l].val+st[st[rt].r].val;
}
int update(int rt,long long l,long long r,long long s){
	if(l==r){
		if(rt==0){
			st[++cnt].val=1;
			return cnt;
		}
		else{
			st[rt].val++;
			return rt;
		}
	}
	int m=l+r>>1;
	int now=rt;
	if(now==0)
		now=++cnt;
	if(s<=m) st[now].l=update(st[rt].l,l,m,s);
	else st[now].r=update(st[rt].r,m+1,r,s);
	pushup(now);
	return now;
}
long long query(int rt,long long l,long long r,long long s){
	if(s<=l)return st[rt].val;
	if(r<s)return 0;
	long long m=l+r>>1;
	return query(st[rt].l,l,m,s)+query(st[rt].r,m+1,r,s);
}
void solve(){
	int n,l,r;
	cin>>n>>l>>r;
	int tmp;
	long long mx=0,mi=0;
	for(int i=1;i<=n;i++){
		cin>>tmp;
		s[i]=s[i-1]+tmp;
		mx=max(s[i],mx);
		mi=min(s[i],mi);
	}
	long long ans=0;
	long long xl,xr;
	int rt=update(rt,mi,mx,0);
	for(int i=1;i<=n;i++){
		xl=query(rt,mi,mx,s[i]-r);
		xr=query(rt,mi,mx,s[i]-l+1);
		ans+=xl-xr;
		rt=update(rt,mi,mx,s[i]);
	}
	cout<<ans<<endl;
}
int main(){
	#ifndef LOCAL
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	#endif
	int t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}

2022/4/8 11:24
加载中...