已老实,求调线段树
查看原帖
已老实,求调线段树
727556
wangziwenhk楼主2024/6/16 10:03
#include <bits/stdc++.h>
using namespace std;
struct Node{
    long long val=0,ls=0,rs=0;
    Node *lp=nullptr,*rp=nullptr;
};
unordered_map<long long,long long>dp;
vector<long long>vec;
vector<long long>sum;
void build(Node* cur,int l,int r){
    if(l==r){
        cur->ls = l;
        cur->rs = r;
        cur->val = 0;
        return;
    }
    int mid = (l+r)>>1;
    cur->ls = l;
    cur->rs = r;
    cur->lp = new Node;
    cur->rp = new Node;
    build(cur->lp,l,mid);
    build(cur->rp,mid+1,r);
    cur->val = max(cur->lp->val,cur->rp->val);
}
void update(Node* cur,int pos,long long value){
    if(cur->rs == cur->ls){
        cur->val = value;
        return;
    }
    int mid = (cur->ls+cur->rs)>>1;
    if(pos<=mid) update(cur->lp,pos,value);
    if(pos>mid) update(cur->rp,pos,value);
    cur->val = max(cur->lp->val, cur->rp->val);
    return;
}
long long query(Node* cur,int l,int r){
    if(cur->ls == l && cur->rs == r || cur->ls == cur->rs){
        return cur->val;
    }
    int mid = (cur->rs+cur->ls)>>1,result;
    if(r<=mid)result = query(cur->lp,l,mid);
    else if(l>mid)result = query(cur->rp,mid+1,r);
    else result = max(query(cur->lp,l,mid),query(cur->rp,mid+1,r));
    return result;
}
int main(){
    Node* root = new Node;
    long long n,k;
    cin>>n>>k;
    vec.resize(n+2);
    sum.resize(n+2);
    for(int i=1;i<=n;i++){
        cin>>vec[i];
    }
    n++,vec[n]=0;
    build(root,0,n);
    for(int i=1;i<=n;i++){
        sum[i] = sum[i-1]+vec[i];
    }
    update(root,1,dp[1] - sum[1]);
    for(int i=2;i<=n;i++){
        int L = max(i-k,1ll),R=i;
        dp[i]=max(dp[i], sum[i-1]+query(root,L-1,R-1));
        update(root,i,dp[i]-sum[i]);
    }
    cout<<dp[n];
    delete root;
}
2024/6/16 10:03
加载中...