LeeCode 3165 线段树

题意

传送门 LeeCode 3165 不包含相邻元素的子序列的最大和

题解

考虑不含相邻子序列的最大和，在不带修改的情况下容易想到，以最后一个元素是否被选取为状态进行DP。从线性递推的角度难以处理待修改的情况。

从分治的角度考虑，使用线段树维护区间内包含或不包含边界元素的信息，即可快速维护答案。总时间复杂度$O(m\log n)$。

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr long long INF = 1e15;
struct SegmentTree {struct Node {array<long long, 4> a;Node() : a{-INF, -INF, -INF, -INF} {}Node operator+(Node& rhs) {Node res;auto _max = [](auto& x, auto y) {x = max(x, y);};for (int i = 0; i < 4; ++i) {for (int j = 0; j < 4; ++j) {if(a[i] == -INF || rhs.a[j] == -INF) {continue;}int i1 = i / 2, i2 = i % 2;int j1 = j / 2, j2 = j % 2;if (i2 == j1 && i2 == 1) {continue;}int k1 = i1, k2 = j2;_max(res.a[k1 * 2 + k2], a[i] + rhs.a[j]);}}return res;}long long get() {long long res = -INF;for (auto x : a) {res = max(res, x);}return res;}};vector<Node> dat;SegmentTree(vector<int>& a) {int n = a.size();int k = 1;while (k < n) {k *= 2;}k *= 2;dat.resize(k);function<void(int, int, int)> init = [&](int p, int l, int r) {if (r - l == 1) {dat[p].a = {0, -INF, -INF, a[l]};return;}int m = (l + r) / 2;int chl = p * 2 + 1, chr = p * 2 + 2;init(chl, l, m);init(chr, m, r);dat[p] = dat[chl] + dat[chr];};init(0, 0, n);}void update(int a, int b, int x, int p, int l, int r) {if (a <= l && r <= b) {dat[p].a = {0, -INF, -INF, x};return;}if (r <= a || b <= l) {return;}int m = (l + r) / 2;int chl = p * 2 + 1, chr = p * 2 + 2;update(a, b, x, chl, l, m);update(a, b, x, chr, m, r);dat[p] = dat[chl] + dat[chr];}
};class Solution {public:int maximumSumSubsequence(vector<int>& nums, vector<vector<int>>& queries) {int n = nums.size();SegmentTree tr(nums);int m = queries.size();long long res = 0;for (int i = 0; i < m; ++i) {int j = queries[i][0], x = queries[i][1];tr.update(j, j + 1, x, 0, 0, n);res += tr.dat[0].get();res %= MOD;}return (res + MOD) % MOD;}
};