CodeForces - 115E：Linear Kingdom Races （DP+线段树+lazy）

pro： 从左到有有N个车道，都有一定程度损坏，所以有不同的修理费a[]； 有M场比赛，每场比赛的场地是[Li,Ri]，即如果这个区间的车道都被修理好，则可以举办这个比赛，并且收益是Pi。问最多得到多少收益。N,M<2e5；

sol： 比较明显的右端点排序，求最大DP问题。  dp[i]表示只考虑修前i条路的最大收益，那么dp[i]=max(dp[j]+P(j+1,i)-a(j+1,i)）;

P(i,j)表示这个区间的收益，a(i,j)表示这个区间的修理费。 考虑无后效性，我们按右端点排序，然后从1到N模拟修路，每个点的左边区间减去修理费，遇到比赛的右端点，在左区间加上收益。 一直更新即可。

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

struct in{

    int L,R,P;

    friend bool operator <(in w,in v){ return w.R<v.R; }

}s[maxn];

ll a[maxn],lazy[maxn<<],mx[maxn<<],dp[maxn];

void pushdown(int Now)

{

    if(lazy[Now]) {

        lazy[Now<<]+=lazy[Now];

        lazy[Now<<|]+=lazy[Now];

        mx[Now<<]+=lazy[Now];

        mx[Now<<|]+=lazy[Now];

        lazy[Now]=;

    }

}

void add(int Now,int L,int R,int l,int r,ll val)

{

    if(l<=L&&r>=R){

        mx[Now]+=val; lazy[Now]+=val;

        return ;

    }

    pushdown(Now);

    int Mid=(L+R)>>;

    if(l<=Mid) add(Now<<,L,Mid,l,r,val);

    if(r>Mid) add(Now<<|,Mid+,R,l,r,val);

    mx[Now]=max(mx[Now<<],mx[Now<<|]);

}

ll query(int Now,int L,int R,int l,int r)

{

    if(l<=L&&r>=R) return mx[Now];

    int Mid=(L+R)>>; ll res=; pushdown(Now);

    if(l<=Mid) res=max(res,query(Now<<,L,Mid,l,r));

    if(r>Mid) res=max(res,query(Now<<|,Mid+,R,l,r));

    mx[Now]=max(mx[Now<<],mx[Now<<|]);

    return res;

}

int main()

{

    int N,M;

    scanf("%d%d",&N,&M);

    rep(i,,N) scanf("%d",&a[i]);

    rep(i,,M) scanf("%d%d%d",&s[i].L,&s[i].R,&s[i].P);

    sort(s+,s+M+);

    int p=;

    rep(i,,N) {

        add(,,N,,i-,-a[i]);

        while(p+<=M&&s[p+].R<=i) p++,add(,,N,,s[p].L-,s[p].P);

        dp[i]=max(query(,,N,,i-),dp[i-]);

        add(,,N,i,i,dp[i]);

    }

    printf("%lld\n",dp[N]);

    return ;

}