「JOI 2017 Final」焚风现象

思路是：

每次修改实际上对于区间内部和区间的非相邻格子没有影响，只对其相邻的两个格子有影响

因此我们可以先对于最开始的区间进行暴力计算，然后对于修改使用线段树维护，然后暴力计算每次修改的变化

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define ll long long
#define re register
#define for_(i,a,b) for(int i=(a);i<=(b);i++)
#define _for(i,a,b) for(int i=(a);i>=(b);i--)
#define lc(q) ((q)<<1)
#define rc(q) ((q)<<1|1)
#define mid(l,r) (((l)+(r))>>1)

using namespace std;

namespace IO {
    inline int read() {
        char ch = getchar();
        int s = 0, f = 1;
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -1;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * f;
    }

    inline void write(int x) {
        if (x < 0) {
            putchar('-');
            x = -x;
        }
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }

    inline void writeln(int x) {
        write(x);
        putchar('\n');
    }
}

using namespace IO;

const int N=0x66CCFF;
const int INF=LLONG_MAX;

int a[N],n,q,s,t,sum;
class SegTree{
 public:
    int l,r,val,lazy;
}T[N];
inline void push_up(int q){
    T[q].val=T[lc(q)].val+T[rc(q)].val;
}
inline void Build(int q,int l,int r){
    T[q].l=l;T[q].r=r;
    if(T[q].l==T[q].r){
        T[q].val=a[l];
        return;
    }
    Build(lc(q),l,mid(l,r));
    Build(rc(q),mid(l,r)+1,r);
    push_up(q);
}
inline void push_down(int q){
    if(T[q].lazy){
        T[lc(q)].lazy+=T[q].lazy;
        T[rc(q)].lazy+=T[q].lazy;
        T[lc(q)].val+=T[q].lazy*(T[lc(q)].r-T[lc(q)].l+1);
        T[rc(q)].val+=T[q].lazy*(T[rc(q)].r-T[rc(q)].l+1);
        T[q].lazy=0;
    }
}
inline void change(int q,int l,int r,int x){
    if(T[q].r<l||T[q].l>r) return;
    if(T[q].l<=l&&T[q].r>=r){
        T[q].val +=(T[q].r-T[q].l+1)*x;
        T[q].lazy+=x;
        return;
    }
    if(T[q].lazy) push_down(q);
    change(lc(q),l,r,x);
    change(rc(q),l,r,x);
    push_up(q);
}
inline int ask(int q,int l,int r){
    if(T[q].r<l||T[q].l>r) return 0;
    if(T[q].l<=l&&T[q].r>=r){
        return T[q].val;
    }
    if(T[q].lazy) push_down(q);
    return ask(lc(q),l,r)+ask(rc(q),l,r); 
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin >> n >> q >> s >> t;
    for_(i,1,n+1){
        cin >> a[i];
    }
    Build(1,1,n+1);
    for_(i,2,n+1){
        if(a[i] < a[i-1])
            sum += (a[i-1]-a[i])*t;
        else 
            sum -= (a[i]-a[i-1])*s;
    }
    for_(i,1,q){
        int l,r,x;
        cin >> l >> r >> x;
        l += 1;r += 1;
        if(ask(1,l,l)>ask(1,l-1,l-1))
            sum += (ask(1,l,l) - ask(1,l-1,l-1)) * s;
        else
            sum -= (ask(1,l-1,l-1) - ask(1,l,l)) * t;
        if(ask(1,r,r)<ask(1,r+1,r+1))
            sum += (ask(1,r+1,r+1) - ask(1,r,r)) * s;
        else
            sum -= (ask(1,r,r) - ask(1,r+1,r+1)) * t;
        change(1,l,r,x);
        if(ask(1,l,l)>ask(1,l-1,l-1))
            sum += (ask(1,l,l) - ask(1,l-1,l-1)) * s;
        else
            sum -= (ask(1,l-1,l-1) - ask(1,l,l)) * t;
        if(ask(1,r,r)<ask(1,r+1,r+1))
            sum += (ask(1,r+1,r+1) - ask(1,r,r)) * s;
        else
            sum -= (ask(1,r,r) - ask(1,r+1,r+1)) * t;
        writeln(sum);        
    }

}