萌新求问这个动态开点的权值线段树怎么就RE了
查看原帖
萌新求问这个动态开点的权值线段树怎么就RE了
39863
引领天下魔酸楼主2020/10/27 20:25
#include<bits/stdc++.h>
using namespace std;
template<class _Tp>class Segment_Tree{
	private:
		int tot=0,ls[13600005],rs[13600005];
		_Tp s[13600005];
	public:
		int root=0;
		void insert(int&i,_Tp x,_Tp k=_Tp(1),_Tp l=_Tp(-(1<<30)),_Tp r=_Tp(1<<30)){
			if(!i)i=++tot;
//			if(tot>13600000)return;
			if(l==r){s[i]+=k;return;}
			_Tp mid=l+r>>1;
			if(x<=mid)insert(ls[i],x,k,l,mid);
			else insert(rs[i],x,k,mid+1,r);
			s[i]=s[ls[i]]+s[rs[i]];
		}
		_Tp ask(int&i,_Tp nl,_Tp nr,_Tp l=_Tp(-(1<<30)),_Tp r=_Tp(1<<30)){
			if(!i)i=++tot;
//			if(tot>13600000)return;
			if(nl<=l&&r<=nr)return s[i];
			_Tp res=0,mid=l+r>>1;
			if(nl<=mid)res+=ask(ls[i],nl,nr,l,mid);
			if(nr>mid)res+=ask(rs[i],nl,nr,mid+1,r);
			return res;
		}
		inline void clear(){memset(ls,0,sizeof(ls));memset(rs,0,sizeof(rs));memset(s,0,sizeof(s));}
};
Segment_Tree<int>t;
int n,a,l,r;
long long ans,s;
int main(){
	scanf("%d%d%d",&n,&l,&r);
	for(int i=1;i<=n;i++){
		scanf("%d",&a);
		t.insert(t.root,s);
		s+=a;
		ans+=t.ask(t.root,s-r,s-l);
	}
	printf("%lld",ans);
	return 0;
}

RE成80分,实在是不知道哪里写锅掉了

2020/10/27 20:25
加载中...