今日的每日一题有点难,新生就别写了
今天的每日一题属于是线段数+dp,我一开始也不会:(
在看完题解后才勉强写出,这里当作分享一个jiangly哥哥的板子,由 github@hh2038整理.
详细题解自行观看leetcode题解
/** 线段树（SegmentTree+Info 区间加+单点修改）
* 2023-09-13: https://qoj.ac/submission/178310
**/
struct SegmentTree {
int n;
std::vector<int> tag;
std::vector<Info> info;
SegmentTree(int n_) : n(n_), tag(4 * n), info(4 * n) {}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void add(int p, int v) {
tag[p] += v;
info[p].max += v;
}
void push(int p) {
add(2 * p, tag[p]);
add(2 * p + 1, tag[p]);
tag[p] = 0;
}
Info query(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return {};
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
}
Info query(int x, int y) {
return query(1, 0, n, x, y);
}
void rangeAdd(int p, int l, int r, int x, int y, int v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
return add(p, v);
}
int m = (l + r) / 2;
push(p);
rangeAdd(2 * p, l, m, x, y, v);
rangeAdd(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeAdd(int x, int y, int v) {
rangeAdd(1, 0, n, x, y, v);
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int x, const Info &v) {
modify(1, 0, n, x, v);
}
};
我的题解
/*
* @lc app=leetcode.cn id=3165 lang=cpp
*
* [3165] 不包含相邻元素的子序列的最大和
*/
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution {
using i64 = long long;
struct Info {
Info() {}
Info(i64 v) : sum11(v) {}
i64 sum00 = 0, sum01 = 0, sum10 = 0, sum11 = 0, mx = 0;
friend struct SegmentTree;
friend Info operator+(const Info &a, const Info &b) {
Info temp;
temp.sum00 = max(a.sum01 + b.sum00, a.sum00 + b.sum10);
temp.sum01 = max(a.sum01 + b.sum01, a.sum00 + b.sum11);
temp.sum10 = max(a.sum10 + b.sum10, a.sum11 + b.sum00);
temp.sum11 = max(a.sum11 + b.sum01, a.sum10 + b.sum11);
temp.mx = max(temp.sum00, max(temp.sum01, max(temp.sum10, temp.sum11)));
return temp;
}
};
// jiangly哥哥的线段数模板orz
template <class Info, class Merge = std::plus<Info>>
struct SegmentTree {
const int n;
const Merge merge;
std::vector<Info> info;
SegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)) {}
SegmentTree(std::vector<Info> init) : SegmentTree(init.size()) {
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) { info[p] = merge(info[2 * p], info[2 * p + 1]); }
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) { modify(1, 0, n, p, v); }
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
return merge(rangeQuery(2 * p, l, m, x, y),
rangeQuery(2 * p + 1, m, r, x, y));
}
Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); }
};
public:
const int mod = 1e9 + 7;
int maximumSumSubsequence(vector<int> &nums, vector<vector<int>> &queries) {
int n = nums.size();
vector<Info> info(n);
for (int i = 0; i < n; i++) info[i] = Info(nums[i]);
SegmentTree<Info> tree(info);
i64 ans = 0;
for (auto q : queries) {
tree.modify(q[0], Info(q[1]));
ans = (ans + max((i64)0, tree.rangeQuery(0, n).sum11)) % mod;
}
return ans;
}
};
// @lc code=end
