计蒜之道2020 D 染色（困难） 线段树优化DP

题目链接：https://nanti.jisuanke.com/t/48303
题目大意：


思路：
区间可能重叠，普通的DP是不可行的。按B.染色（简单）是有问题的。给个样例：

7 3
6 1 -7 -2 -2 9 -4 
7 -3 -3 -5 1 1 -6 
2 2 4 0
1 4 6 7
1 2 5 5
正确的是14
2 1 1 1 1 1 1

我们用f[i]:染完前i个能够得到的最大代价。
用两棵线段树来维护区间[L, i]涂黑/白色的最大贡献。
Ta：mx[L]:区间[L+1, i]全部涂黑的最大贡献。那么每到一个i。[0, i-1]的所有情况都应该加上b[i]。add(0, i-1, b[i])。对于特殊的区间[k, i]那么[0, k-1]都可以得到贡献c[i]。Tb同理。因为线段树的下标从1开始，我们处理时区间端点都+1就可以了。

#include <bits/stdc++.h>
#define LL long long
#define F first
#define S second
#define pii pair<int, int>
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;

struct Tree {
    LL mx[2000005], laz[2000005];
    void BT(int i, int l, int r) {
        mx[i]=laz[i]=0;
        if(l==r)
            return ;
        int mid=l+r>>1;
        BT(i<<1, l, mid), BT(i<<1|1, mid+1, r);
    }
    void up_down(int i) {
        mx[i<<1]+=laz[i];
        laz[i<<1]+=laz[i];
        mx[i<<1|1]+=laz[i];
        laz[i<<1|1]+=laz[i];
        laz[i]=0;
    }
    void up_data(int i, int l, int r, int L, int R, LL val) {
        if(R<L) return ;
        if(l==L&&r==R) {
            mx[i]+=val;
            laz[i]+=val;
            return ;
        }
        up_down(i);
        int mid=l+r>>1;
        if(R<=mid)
            up_data(i<<1, l, mid, L, R, val);
        else if(L>mid)
            up_data(i<<1|1, mid+1, r, L, R, val);
        else
            up_data(i<<1, l, mid, L, mid, val), up_data(i<<1|1, mid+1, r, mid+1, R, val);
        mx[i]=max(mx[i<<1], mx[i<<1|1]);
    }
    LL query(int i, int l, int r, int L, int R) {
        if(l==L&&r==R) {
            return mx[i];
        }
        up_down(i);
        int mid=l+r>>1;
        if(R<=mid)
            return query(i<<1, l, mid, L, R);
        else if(L>mid)
            return query(i<<1|1, mid+1, r, L, R);
        else
            return max(query(i<<1, l, mid, L, mid), query(i<<1|1, mid+1, r, mid+1, R));
    }
} Ta, Tb;

LL b[300005], w[300005], f[300005];
vector<pii> qa[300005], qb[300005];
int main() {

    int n, m; scanf("%d%d", &n, &m);
    Ta.BT(1, 1, n+5); Tb.BT(1, 1, n+5);
    for(int i=1; i<=n; i++) {
        scanf("%lld", &b[i]);//黑
    }
    for(int i=1; i<=n; i++) {
        scanf("%lld", &w[i]);
    }
    for(int i=1; i<=m; i++) {
        int t, l, r, c;
        scanf("%d%d%d%d", &t, &l, &r, &c);
        if(t==1){
            qa[r].push_back({l, c});
        }
        else{
            qb[r].push_back({l, c});
        }
    }
    for(int i=1; i<=n; i++){
        Ta.up_data(1, 1, n+5, 1, i, b[i]);
        Tb.up_data(1, 1, n+5, 1, i, w[i]);
        for(auto x: qa[i]){
            int l=x.F, w=x.S;
            Ta.up_data(1, 1, n+5, 1, l, w);
        }
        for(auto x: qb[i]){
            int l=x.F, w=x.S;
            Tb.up_data(1, 1, n+5, 1, l, w);
        }
        f[i]=max(Ta.query(1, 1, n+5, 1, i), Tb.query(1, 1, n+5, 1, i));
        Ta.up_data(1, 1, n+5, i+1, i+1, f[i]);
        Tb.up_data(1, 1, n+5, i+1, i+1, f[i]);
    }
    printf("%lld\n", f[n]);

    return 0;
}