MvemiY @ 2023-08-10 21:49:52
#include<bits/stdc++.h>
#define lc(x) x << 1
#define rc(x) x << 1 | 1
using namespace std;
const int MAXN = 2e5 + 5;
int n, L, R, a[MAXN], f[MAXN], ans = INT_MIN, SGT[4*MAXN], id[MAXN];
inline bool in(int tL, int tR, int l, int r){
return l <= tL && tR <= r;
}
inline bool out(int tL, int tR, int l, int r){
return l > tR || r < tL;
}
inline void pushup(int u){
SGT[u] = max(SGT[lc(u)], SGT[rc(u)]);
}
void build(int u, int tL, int tR){
if(tL == tR){
SGT[u] = f[tL];
id[tL] = u;
return ;
}
int mid = (tL+tR) >> 1;
build(lc(u), tL, mid);
build(rc(u), mid+1, tR);
pushup(u);
}
void update(int x, int k){
int u = id[x];
SGT[u] = k;
u >>= 1;
while(u){
pushup(u);
u >>= 1;
}
}
int query(int u, int tL, int tR, int l, int r){
if(in(tL, tR, l, r))
return SGT[u];
if(out(tL, tR, l, r))
return -0x3f3f3f3f;
int mid = (tL+tR) >> 1;
return max(query(lc(u), tL, mid, l, r), query(rc(u), mid+1, tR, l, r));
}
int main(){
memset(f, -0x3f, sizeof(f));
cin >> n >> L >> R;
for(int i = 0; i <= n; i++)
cin >> a[i];
f[0] = 0;
build(1, 0, n);
for(int i = L; i <= n; i++){
int k = query(1, 1, n, max(0, i-R), i-L);
if(f[i] < k + a[i]){
f[i] = k + a[i];
update(i, k+a[i]);
}
}
for(int i = n - R + 1; i <= n; i++)
ans = max(ans, f[i]);
cout << ans;
return 0;
} 用单调队列打完觉得可以用线段树做，但是爆灵（
有没有大佬知道哪里写挂了嘛
by ___A__ @ 2023-08-31 14:55:13
@Birdly 线段树下标只能从1开始 集体偏移罢
by ___A__ @ 2023-08-31 14:56:00
您这个写法我是确实没看懂 可以参考一下我的 自认为还是写的很便于理解的
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+50;
int a[N],l,r,dp[N],n,inf;
struct segtree{
int l,r,num;
}t[N*4];
void build(int x,int l,int r){
t[x].l=l,t[x].r=r;
if(l==r){
return;
}
int mid=(l+r)/2;
build(x*2,l,mid),build(x*2+1,mid+1,r);
}
int query(int x,int l,int r){
if(l>r){
return inf;
}
if(t[x].l>=l&&t[x].r<=r){
return t[x].num;
}
int mid=(t[x].l+t[x].r)/2,ret=inf;
if(l<=mid){
ret=max(ret,query(x*2,l,r));
}
if(r>mid){
ret=max(ret,query(x*2+1,l,r));
}
return ret;
}
void modify(int x,int idx,int num){
if(t[x].l==t[x].r){
t[x].num=num;
return;
}
int mid=(t[x].l+t[x].r)/2;
if(idx<=mid){
modify(x*2,idx,num);
}
else{
modify(x*2+1,idx,num);
}
t[x].num=max(t[x*2].num,t[x*2+1].num);
}
int main(){
cin>>n>>l>>r;
for(int i=1;i<=n+1;i++){
cin>>a[i];
}
memset(dp,128,sizeof(dp));
inf=dp[1],dp[1]=0;
build(1,1,n+r+1);
for(int i=2;i<=n+r+1;i++){
dp[i]=query(1,max(1,i-r),i-l)+a[i],modify(1,i,dp[i]);
}
cout<<*max_element(dp+n+2,dp+n+r+2);
}