线段树100uac
  • 板块P1725 琪露诺
  • 楼主oberzhang
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/1/27 11:37
  • 上次更新2025/1/27 15:55:51
查看原帖
线段树100uac
952913
oberzhang楼主2025/1/27 11:37
#include<bits/stdc++.h>
using namespace std;
#define int long long

const int INF=-(1<<32);
const int N=2e5+10;

int n,L,R,a[N],f[N];

struct tree{
	int p,dat,l,r;
}t[N<<2];

void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;
	if(l==r){
		t[p].dat=f[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}

int ask(int p,int l,int r){
	if(t[p].l>=l && t[p].r<=r){
		return t[p].dat;
	}
	int ans=INF;
	int mid=(t[p].l+t[p].r)/2;
	if(l<=mid)ans=max(ans,ask(p*2,l,r));
	if(r>mid)ans=max(ans,ask(p*2+1,l,r));
	return ans;
}

void update(int p,int x,int k){
	if(t[p].l==t[p].r){
		t[p].dat=k;
		return;
	}
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid){
		update(p*2,x,k);
	}else{
		update(p*2+1,x,k);
	}
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>L>>R;
	for(int i=0;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=2*n;i++)f[i]=INF;
	build(1,0,n*2);
	for(int i=L;i<=n;i++){
		int d=ask(1,max(0ll,i-R),max(0ll,i-L))+a[i];
		f[i]=d;
		update(1,i,f[i]);
	}
	cout<<ask(1,n-R+1,n);
	return 0;
}

2025/1/27 11:37
加载中...