题解：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

CPP

// 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 ;
}

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

文章操作

Solution

Code

相关推荐

评论

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