unac100求调

P1725 琪露诺

114514xxx @ 2024-10-09 14:43:19

线段树写法求调

#include<bits/stdc++.h>
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int N=4e5+25;
int f[N],a[N];
int n,l,r;
struct SegmentTree{
    int l,r,maxn;
}t[N*4];
inline void build(int l,int r,int p){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].maxn=f[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,ls);
    build(mid+1,r,rs);
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
inline void modify(int l,int r,int p,int k){
    if(t[p].l==t[p].r&&t[p].l==l){
        t[p].maxn=k;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid)modify(l,r,ls,k);
    if(r>mid)modify(l,r,rs,k);
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
inline int query(int l,int r,int p){
    int res=INT_MIN;
    if(t[p].l>=l&&t[p].r<=r)return t[p].maxn;
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid)res=max(res,query(l,r,ls));
    if(r>mid)res=max(res,query(l,r,rs));
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
    return res;
}
int main(){
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++)
        cin>>a[i];
    build(0,n,1);
    int ans=INT_MIN;
    for(int i=l;i<=r;i++){
        f[i]=max(query(0,i-l,1)+a[i],f[i]);
        modify(i,i,1,f[i]);
    }
    for(int i=r+1;i<=n+r;++i){
        f[i]=max(f[i],query(i-r,i-l,1)+a[i]);
        modify(i,i,1,f[i]);
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    cout<<ans;
}

by 114514xxx @ 2024-10-09 14:50:56

贴错代码了

#include<bits/stdc++.h>
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int N=4e5+25;
int f[N],a[N];
int n,l,r;
struct SegmentTree{
    int l,r,maxn;
}t[N*4];
inline void build(int l,int r,int p){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].maxn=f[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,ls);
    build(mid+1,r,rs);
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
inline void modify(int l,int r,int p,int k){
    if(t[p].l==t[p].r&&t[p].l==l){
        t[p].maxn=k;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid)modify(l,r,ls,k);
    if(r>mid)modify(l,r,rs,k);
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
inline int query(int l,int r,int p){
    int res=INT_MIN;
    if(t[p].l>=l&&t[p].r<=r)return t[p].maxn;
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid)res=max(res,query(l,r,ls));
    if(r>mid)res=max(res,query(l,r,rs));
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
    return res;
}
int main(){
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++)
        cin>>a[i];
    build(0,n+r+1,1);
    int ans=INT_MIN;
    for(int i=1;i<=n;i++)
        f[i]=INT_MIN;
    for(int i=l;i<=r;i++){
        f[i]=max(query(0,i-l,1)+a[i],f[i]);
        modify(i,i,1,f[i]);
    }
    for(int i=r+1;i<=n+r;++i){
        f[i]=max(f[i],query(i-r,i-l,1)+a[i]);
        modify(i,i,1,f[i]);
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,f[i]);
    cout<<ans;
}

by Elysialr @ 2024-10-09 15:06:04

        while(left<=right&&f[i-l]>f[q[right]]) right--;
        right++;q[right]=i-l;
        while(left<=right&&q[left]+r<i) left++;
        f[i]=f[q[left]]+a[i];

单调队列

by jade1695 @ 2024-10-09 17:25:53

@114514xxx ```

include<bits/stdc++.h>

define ls 2*p

define rs 2*p+1

using namespace std; const int N=4e5+25; int f[N],a[N]; int n,l,r; struct SegmentTree{ int l,r,maxn; }t[N*4]; inline void build(int l,int r,int p){ t[p].l=l,t[p].r=r; if(l==r){ t[p].maxn=f[l]; return; } int mid=(l+r)/2; build(l,mid,ls); build(mid+1,r,rs); t[p].maxn=max(t[ls].maxn,t[rs].maxn); } inline void modify(int l,int r,int p,int k){ if(t[p].l==t[p].r&&t[p].l==l){ t[p].maxn=k; return; } int mid=(t[p].l+t[p].r)/2; if(l<=mid)modify(l,r,ls,k); if(r>mid)modify(l,r,rs,k); t[p].maxn=max(t[ls].maxn,t[rs].maxn); } inline int query(int l,int r,int p){ int res=INT_MIN; if(t[p].l>=l&&t[p].r<=r)return t[p].maxn; int mid=(t[p].l+t[p].r)/2; if(l<=mid)res=max(res,query(l,r,ls)); if(r>mid)res=max(res,query(l,r,rs)); t[p].maxn=max(t[ls].maxn,t[rs].maxn); return res; } int main(){ cin>>n>>l>>r; for(int i=0;i<=n;i++) cin>>a[i],f[i]=INT_MIN; for(int i=n;i<=n+r;i++)f[i]=INT_MIN; f[0]=0; build(0,n+r,1); int ans=INT_MIN; for(int i=l;i<=r;i++){ f[i]=max(query(0,i-l,1)+a[i],f[i]); modify(i,i,1,f[i]); } for(int i=r+1;i<=n+r;++i){ f[i]=max(f[i],query(i-r,i-l,1)+a[i]); modify(i,i,1,f[i]); } for(int i=n;i<=n+r;i++) // cout<<f[i]<<endl, ans=max(ans,f[i]); cout<<ans; }


过了

by jade1695 @ 2024-10-09 17:26:14

#include<bits/stdc++.h>
#define ls 2*p
#define rs 2*p+1
using namespace std;
const int N=4e5+25;
int f[N],a[N];
int n,l,r;
struct SegmentTree{
    int l,r,maxn;
}t[N*4];
inline void build(int l,int r,int p){
    t[p].l=l,t[p].r=r;
    if(l==r){
        t[p].maxn=f[l];
        return;
    }
    int mid=(l+r)/2;
    build(l,mid,ls);
    build(mid+1,r,rs);
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
inline void modify(int l,int r,int p,int k){
    if(t[p].l==t[p].r&&t[p].l==l){
        t[p].maxn=k;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid)modify(l,r,ls,k);
    if(r>mid)modify(l,r,rs,k);
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
}
inline int query(int l,int r,int p){
    int res=INT_MIN;
    if(t[p].l>=l&&t[p].r<=r)return t[p].maxn;
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid)res=max(res,query(l,r,ls));
    if(r>mid)res=max(res,query(l,r,rs));
    t[p].maxn=max(t[ls].maxn,t[rs].maxn);
    return res;
}
int main(){
    cin>>n>>l>>r;
    for(int i=0;i<=n;i++)
        cin>>a[i],f[i]=INT_MIN;
    for(int i=n;i<=n+r;i++)f[i]=INT_MIN;
    f[0]=0;
    build(0,n+r,1);
    int ans=INT_MIN;
    for(int i=l;i<=r;i++){
        f[i]=max(query(0,i-l,1)+a[i],f[i]);
        modify(i,i,1,f[i]);
    }
    for(int i=r+1;i<=n+r;++i){
        f[i]=max(f[i],query(i-r,i-l,1)+a[i]);
        modify(i,i,1,f[i]);
    }
    for(int i=n;i<=n+r;i++)
//      cout<<f[i]<<endl,
        ans=max(ans,f[i]);
    cout<<ans;
}