CF115E Linear Kingdom Races 线段树优化DP

题意：

戳这里

分析：

线段树优化DP

转移式很好推，如下

(f_i=max(f_j+w(j,i)-cst(j,i))=max(f_j+w(j,i)+cst_{j})-cst_i)

因为以下几条错误，一道水题让我我调了好久

tip:

1. 允许从 (0) 转移
2. 转移式还需要和上一个位置取 (max) 即 f[i]=max(f[i],f[i-1])

代码：

#include<bits/stdc++.h>
#define inl inline
#define lc rt<<1
#define rc rt<<1|1
#define pll pair<long long,long long> 
#define mk(x,y) make_pair(x,y)
#define pb push_back
#define fir first
#define sec second

using namespace std;

namespace zzc
{
    typedef long long ll;
    inl ll read()
    {
        ll x=0,f=1;char ch=getchar();
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
        return x*f;
    }
    
    const ll maxn = 2e5+5;
    const ll inf = 0x3f3f3f3f3f3f3f3f;
    ll n,m;
    ll cst[maxn],val[maxn<<2],f[maxn],tag[maxn<<2];
    vector<pll> r[maxn];

    void pushup(ll rt)
    {
        val[rt]=max(val[lc],val[rc]);    
    }
	
	void pushdown(int rt)
	{
		if(tag[rt])
		{
			tag[lc]+=tag[rt];
			val[lc]+=tag[rt];
			tag[rc]+=tag[rt];
			val[rc]+=tag[rt];
			tag[rt]=0;
		}
	}
	
    void modify(int rt,int l,int r,int ql,int qr,ll x)
    {
        if(ql<=l&&r<=qr)
        {
            val[rt]+=x;
            tag[rt]+=x;
            return ;
        }
        pushdown(rt);
        ll mid=(l+r)>>1;
        if(ql<=mid) modify(lc,l,mid,ql,qr,x);
        if(qr>mid) modify(rc,mid+1,r,ql,qr,x);
        pushup(rt);
    }

    ll query(int rt,int l,int r,int ql,int qr)
    {
        if(ql<=l&&r<=qr) return val[rt];
        pushdown(rt);
        ll mid=(l+r)>>1,res=-inf;
        if(ql<=mid) res=max(res,query(lc,l,mid,ql,qr));
        if(qr>mid) res=max(res,query(rc,mid+1,r,ql,qr));
        return res;
    }

    void work()
    {
        ll a,b,c;
        n=read();m=read();
        for(ll i=1;i<=n;i++) cst[i]=cst[i-1]+read();
        for(ll i=1;i<=m;i++) 
        {
            a=read();b=read();c=read();
            r[b].pb(mk(a,c));
        }
        for(int i=1;i<=n;i++)
        {
            for(auto x:r[i]) modify(1,0,n,0,x.fir-1,x.sec);	
            f[i]=max(query(1,0,n,0,i-1),cst[i])-cst[i];
            f[i]=max(f[i],f[i-1]);
            modify(1,0,n,i,i,f[i]+cst[i]);
        }
        printf("%lld
",f[n]);
    }

}


int main()
{
    zzc::work();
    return 0;
}