权值线段树做的,为什么要开64倍空间才能做?
查看原帖
权值线段树做的,为什么要开64倍空间才能做?
1025259
Kopicy_sama楼主2023/8/25 18:04
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ri register int
const ll N=1e5+5;

ll len=N*N;

ll a[N],n,L,R,cnt=1,sum[N<<6];
int ls[N<<6],rs[N<<6],rt;

void insert(int &p,ll l,ll r,ll x){
	if(!p) p=++cnt;
	sum[p]++;
	if(l==r) return ;
	ll mid=l+r>>1;
	if(x<=mid) insert(ls[p],l,mid,x);
	else insert(rs[p],mid+1,r,x);
}

ll query(int &p,ll l,ll r,ll nl,ll nr){
	if(!p) p=++cnt;
	if(nl<=l&&r<=nr){
		return sum[p];
	}
	ll ans=0,mid=l+r>>1;
	if(nl<=mid) ans+=query(ls[p],l,mid,nl,nr);
	if(nr>mid) ans+=query(rs[p],mid+1,r,nl,nr);
	return ans;
}

int main(){
	std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>L>>R;
	for(ri i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
	ll res=0;
	for(ri i=1;i<=n;i++){
		insert(rt,-len,len,a[i-1]);
		ll l=a[i]-R,r=a[i]-L;
		res+=query(rt,-len,len,l,r);
		//cout<<query(rt,-len,len,l,r)<<endl;
	}
	cout<<res;
}

N*64插入的节点也就N,开两倍问题是会挂

2023/8/25 18:04
加载中...