线段树跌丝袜

#include<bits/stdc++.h>
using namespace std;

// 定义线段树节点结构体，存储四种状态的最大产奶量
struct SegTreeNode {
long long f00; // 左右端点都不选
long long f01; // 左端点不选，右端点选
long long f10; // 左端点选，右端点不选
long long f11; // 左右端点都选
SegTreeNode() : f00(0), f01(0), f10(0), f11(0) {}
};

vector<SegTreeNode> segTree; // 线段树数组
vector<int> M; // 存储每台挤奶机的产奶量

// 合并左右子节点的状态
SegTreeNode merge(const SegTreeNode& left, const SegTreeNode& right) {
SegTreeNode res;
// 计算f00：左区间右端点不选，右区间左端点不选
res.f00 = max(left.f00 + right.f00, left.f01 + right.f00);
res.f00 = max(res.f00, left.f00 + right.f10);

// 计算f01：左区间右端点不选，右区间左端点选
res.f01 = max(left.f00 + right.f01, left.f00 + right.f11);
res.f01 = max(res.f01, left.f01 + right.f01);

// 计算f10：左区间右端点选，右区间左端点不选
res.f10 = max(left.f10 + right.f00, left.f10 + right.f10);
res.f10 = max(res.f10, left.f11 + right.f00);

// 计算f11：左区间右端点选，右区间左端点选
res.f11 = max(left.f10 + right.f01, left.f10 + right.f11);
res.f11 = max(res.f11, left.f11 + right.f01);
return res;

}

// 构建线段树
void build(int node, int start, int end) {
if (start == end) {
// 叶子节点初始化
segTree[node].f00 = 0; // 不选当前节点
segTree[node].f01 = -1e18; // 不可能的状态
segTree[node].f10 = -1e18; // 不可能的状态
segTree[node].f11 = M[start]; // 选当前节点
} else {
int mid = (start + end) / 2;
build(2 * node + 1, start, mid); // 构建左子树
build(2 * node + 2, mid + 1, end); // 构建右子树
segTree[node] = merge(segTree[2 * node + 1], segTree[2 * node + 2]); // 合并左右子树
}
}

// 更新线段树中某个节点的值
void update(int node, int start, int end, int idx, int val) {
if (start == end) {
M[idx] = val; // 更新产奶量
segTree[node].f00 = 0;
segTree[node].f01 = -1e18;
segTree[node].f10 = -1e18;
segTree[node].f11 = val;
} else {
int mid = (start + end) / 2;
if (idx <= mid) {
update(2 * node + 1, start, mid, idx, val); // 更新左子树
} else {
update(2 * node + 2, mid + 1, end, idx, val); // 更新右子树
}
segTree[node] = merge(segTree[2 * node + 1], segTree[2 * node + 2]); // 合并更新后的子树
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);

int N, D;
cin >> N >> D; // 输入挤奶机数量和天数
M.resize(N);
for (int i = 0; i < N; ++i) {
    cin >> M[i]; // 输入每台挤奶机的初始产奶量
}

// 计算线段树的大小
int size = 1;
while (size < N) size <<= 1;
segTree.resize(2 * size - 1);
build(0, 0, N - 1); // 构建线段树

long long total = 0;
for (int d = 0; d < D; ++d) {
    int i, m;
    cin >> i >> m; // 输入每天更新的挤奶机编号和新的产奶量
    --i; // 转换为0-based索引
    update(0, 0, N - 1, i, m); // 更新线段树
    SegTreeNode root = segTree[0]; // 获取根节点
    long long max_day = max({root.f00, root.f01, root.f10, root.f11}); // 计算当天最大产奶量
    total += max_day; // 累加到总产奶量
}
cout << total << '\n'; // 输出总产奶量

return 0;

}