样例能过10pts求调玄关
查看原帖
样例能过10pts求调玄关
1470997
xpigeon楼主2025/7/3 17:47

用的主席树,主席树部分应该没问题(

#include<bits/stdc++.h>
#define ili inline
#define pb push_back
using namespace std;
template <typename T>
ili void rd(T&x){
	int f=1;x=0;
	char c=getchar();
	while(c<'0' || c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0' && c<='9'){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	x=f*x;
}
template <typename T,typename ...Args>
ili void rd(T &x,Args&...args){
	rd(x),rd(args...);
}
template <typename T>
void wr(T x){
	if(x<0) putchar('-'),x=-x;
	if(x<10) putchar(x+'0');
	else wr<T>(x/10),putchar(x%10+'0');
}
const int N=5e5+5;
const int LG=20;
int n,k,L,R;
int a[N],sum[N],b[N],idx;
struct node{
	int ans,r,tim;
};
bool operator <(node a,node b){
	return a.ans<b.ans;
}
priority_queue<node> q;
int P=1,DEP,t[N*3+N*LG],son[N*3+N*LG][2],OST,rt[N];
int ans;
ili void update(int i,int ver,int l,int k){
	int tl=l+P;
	int v=rt[ver];
	rt[i]=l=++OST;
	t[l]=t[v]+k;
	for(int dep=DEP-1;dep>=0;dep--){
		if((tl>>dep)&1) son[l][0]=son[v][0],son[l][1]=++OST,v=son[v][1];
		else son[l][1]=son[v][1],son[l][0]=++OST,v=son[v][0];
		l=OST,t[l]=t[v]+k;
	}
}
ili int query(int l,int r,int k){
	l=rt[l],r=rt[r];
	int tl=1;
	for(int dep=DEP;dep;dep--){
		int num=t[son[r][0]]-t[son[l][0]];
		if(num>=k){
			l=son[l][0];
			r=son[r][0];
			tl=tl<<1;
		}else{
			k-=num;
			l=son[l][1];
			r=son[r][1];
			tl=tl<<1|1;
		}
	}
	return tl-P;
}
ili void zkw(){
	rt[0]=1;
	while(P<=idx+1) P<<=1,++DEP;
	OST=(P<<1)-1;
	for(int i=P-1;i;i--) son[i][0]=i<<1,son[i][1]=i<<1|1;
	for(int i=1;i<=n;i++){
		update(i,i-1,a[i],1);
	}
}
ili void xpigeon(){
	rd(n,k,L,R);
	for(int i=1;i<=n;i++){
		rd(a[i]);
		sum[i]=a[i]+sum[i-1];
		b[i]=sum[i];
	}
	sort(b+1,b+n+1);
	idx=unique(b+1,b+n+1)-(b+1);
	for(int i=1;i<=n;i++){
		a[i]=lower_bound(b+1,b+idx+1,sum[i])-b;
	}
	zkw();
	for(int r=L;r<=n;r++){
		int u=max(r-R,1);
		int v=r-L;
		if(r-R<=0&&b[query(0,v,1)]>0) q.push((node){sum[r],r,1});
		else{
			q.push((node){sum[r]-b[query(u-1,v,1)],r,1});
		}
	}
	for(int i=1;i<=k;i++){
		node tmp=q.top();
		q.pop();
		ans+=tmp.ans;
		//cout<<tmp.ans<<" "<<tmp.r<<" "<<tmp.tim<<'\n';
		int u=max(tmp.r-R,1);
		int v=tmp.r-L;
		if(u+tmp.tim>v) continue;
		if(tmp.r-R<=0 && b[query(0,v,tmp.tim+1)]>0) q.push((node){sum[tmp.r],tmp.r,tmp.tim+1});
		else{
			q.push((node){sum[tmp.r]-b[query(u+tmp.tim-1,v,1)],tmp.r,tmp.tim+1 });
		}
		
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	xpigeon();
	return 0;
}
2025/7/3 17:47
加载中...