题解：P7402 [COCI 2020/2021 #5] Sjeckanje

Solution

CF484D 的带修版本。

关键观察：最优方案里，划分完的每个区间一定是单调的。证明是显然的。那么，划分点一定在每个波峰和波谷。

考虑原数组的差分序列，则单调区间就转化成了同号区间，答案就是区间和的绝对值。对于修改，我们要做的是单点修改和查询全局答案。

考虑线段树，pushup 如何合并两个区间？若两个子区间合起来是单调的，答案显然就是他们的和；若不是，就要讨论一下波峰和波谷选不选了。于是我们定义 $\text{sum}_{x, \space 0/1, \space 0/1}$，表示区间 $x$ 左端点不选或选，右端点不选或选的答案，合并的时候讨论一下左儿子的右端点和右儿子的左端点选不选，取个 $\max$ 就行了。

注意一个 corner case：$n = 1$ 时如果写 $O(n)$ 建树会 RE，原因是会构建一个 $[2, 1]$ 的区间。特判一下就行。

Code

// Problem: P7402 [COCI 2020/2021 #5] Sjeckanje
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7402
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long 
#define pii pair<int,int>
#define pb push_back
#define endl '\n'
#define rep(i, a, b) for(int (i) = (a); (i) <= (b); (i) ++)
#define per(i, a, b) for(int (i) = (a); (i) >= (b); (i) --)
#define ls x << 1
#define rs x << 1 | 1

using namespace std;

const int maxn = 2e5 + 5 ;

int n, q, a[maxn] ; 
ll d[maxn] ;

struct sgt {
    #define maxn (maxn << 2)
    int l[maxn], r[maxn] ;
    ll sum[maxn][2][2] ;
    #undef maxn
    void pushup(int x, int mid) {
        rep(i, 0, 1) {
            rep(j, 0, 1) {
                if((d[mid] >= 0 && d[mid + 1] >= 0) || (d[mid] <= 0 && d[mid + 1] <= 0)) {
                    sum[x][i][j] = sum[ls][i][1] + sum[rs][1][j] ;
                }
                else {
                    sum[x][i][j] = max(sum[ls][i][0] + sum[rs][1][j], sum[ls][i][1] + sum[rs][0][j]) ;
                }
            }
        }
    }
    void build(int x, int L, int R) {
        l[x] = L, r[x] = R ;
        if(l[x] == r[x]) {
            sum[x][1][1] = llabs(d[L]) ;
            return ;
        }
        int mid = (L + R) >> 1 ; 
        build(ls, L, mid) ;
        build(rs, mid + 1, R) ;
        pushup(x, mid) ;
    }
    void add(int x, int pos) {
        if(l[x] == r[x]) {
            sum[x][1][1] = llabs(d[l[x]]) ;
            return ;
        }
        int mid = (l[x] + r[x]) >> 1 ;
        if(pos <= mid) add(ls, pos) ;
        if(pos > mid) add(rs, pos) ;
        pushup(x, mid) ;
    }
} t ;

void solve(){
    cin >> n >> q ;
    rep(i, 1, n) {
        cin >> a[i] ;
        d[i] = a[i] - a[i - 1] ;
    }
    if(n == 1) {
        while(q -- ) {
            int l, r, x ; cin >> l >> r >> x ;
            cout << 0 << endl ;
        }
        return ;
    }
    t.build(1, 2, n) ;
    while(q -- ) {
        int l, r, x ; cin >> l >> r >> x ;
        if(l >= 2) {
            d[l] += x ;
            t.add(1, l) ;
        }
        if(r + 1 <= n) {
            d[r + 1] -= x ;
            t.add(1, r + 1) ;
        }
        cout << t.sum[1][1][1] << endl ;
    }
    return ;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T = 1 ; 
//    cin >> T ;
    while(T -- ){
        solve() ;
    }
    return 0 ;
} 

---

• 分类： OI
• 标签： 无标签