线段树优化dp——牛客多校第一场I（好题）

浅浅的花香味﹌ 2023-10-11 09:10 44阅读 0赞

和两天做了两道数据结构优化dp的题，套路还是差不多的

题解链接！ https://www.cnblogs.com/kls123/p/11221471.html

一些补充

其实这道题的dp\[i\]维护的不是每个点，而是每个离散化的y，也可以理解为当前折线停留在纵坐标为y的答案

从左往右，从上往下进行遍历点，对于每个点p\[i\]考虑三种情况：

1.折线经过这个点，那么这条折线必定从小于等于p\[i\].y的地方折上来的，所以查询一段区间的极值即可

2.折线在这个点上面，那么通过这个点去更新那些在其上面的折线值即可

3.折线在点下面，和2同理

此外，由于折线可能是直接从y=0折上来的，所以必须增加y=0的点来进行第1种转移，不加是错误的，等于少了这种情况！

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long 
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define mid ll m = (l + r) >> 1
    
    const int M = 1e5+10;
    ll mx[M<<2],lazy[M<<2];
    void up(ll rt){
        mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
    }
    
    void pushdown(ll rt){
        if(lazy[rt]){
            lazy[rt<<1] += lazy[rt];
            lazy[rt<<1|1] += lazy[rt];
            mx[rt<<1] += lazy[rt];
            mx[rt<<1|1] += lazy[rt];
            lazy[rt] = 0;
        }
    }
    
    void build(ll l,ll r,ll rt){
        lazy[rt] = 0; mx[rt] = 0;
        if(l == r){
            return ;
        }
        mid;
        build(lson); build(rson);
    }
    
    void update(ll p,ll c,ll l,ll r,ll rt){
        if(l == r){
            mx[rt] = max(mx[rt],c);
            return ;
        }
        pushdown(rt);
        mid;
        if(p <= m) update(p,c,lson);
        else update(p,c,rson);
        up(rt);
    }
    
    void update1(ll L,ll R,ll c,ll l,ll r,ll rt){
        if(L > R) return ;  //会出现L > R的情况，需要判下
        if(L <= l&&R >= r){
            mx[rt] += c;
            lazy[rt] += c;
            return ;
        }
        pushdown(rt);
        mid;
        if(L <= m) update1(L,R,c,lson);
        if(R > m) update1(L,R,c,rson);
        up(rt);
    }
    
    ll query(ll L,ll R,ll l,ll r,ll rt){
        if(L > R) return 0;
        if(L <= l&&R >= r){
            return mx[rt];
        }
        pushdown(rt);
        mid;
        ll ret = 0;
        if(L <= m) ret = max(ret,query(L,R,lson));
        if(R > m) ret = max(ret,query(L,R,rson));
        return ret;
    }
    
    struct node{
        ll x,y,a,b;
    }v[M];
    bool cmp(node aa,node bb){
        if(aa.x == bb.x) return aa.y > bb.y;
        return aa.x < bb.x;
    }
    ll t[M];
    int main()
    {
        ll n;
        while(scanf("%lld",&n)!=EOF){
            ll cnt = 0;
            for(ll i = 1;i <= n;i ++){
                scanf("%lld%lld%lld%lld",&v[i].x,&v[i].y,&v[i].a,&v[i].b);
                t[++cnt] = v[i].y;
            }
            sort(t+1,t+1+cnt);
            sort(v+1,v+1+n,cmp);
            ll m = unique(t+1,t+1+cnt)-t-1;
            for(ll i = 1;i <= n;i ++)
                v[i].y = lower_bound(t+1,t+1+m,v[i].y)-t+1; //离散化时点都向后移一位
            m ++;  //点后移了一位，长度要+1;
            build(1,m,1);
            for(ll i = 1;i <= n;i ++){
                ll ans = query(1,v[i].y,1,m,1);
                update1(v[i].y+1,m,v[i].b,1,m,1);
                update1(1,v[i].y-1,v[i].a,1,m,1);
                update(v[i].y,ans+v[i].b,1,m,1);
            }
            printf("%lld\n",mx[1]);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11285257.html