【DS，性质题】P5069 [Ynoi2015] 纵使日薄西山
super蒟蒻
·
·
题解
提供一个线段树的做法。
首先 a_{x-1}-1,a_x-1,a_{x+1}-1 不会改变三者的大小关系， a_x 依然是这三个数中最大的，因此左右两边必不会选到，要让 a_x=0 只能对着 x 操作 a_x 次（然后它左右两边顺理成章的也变成了零）。
所以原题实际上是要维护一个被减的数的集合，这些数在原序列互不相邻且符合操作的要求，然后输出这些数的和。
考虑用线段树维护这个集合的和。
首先叶子的答案是本身，然后我们考虑合并两个区间。
发现如果 左区间的右端点没有被选 或者 右区间的左端点没有被选，这两个区间是互不影响的，答案直接相加即可。
但是像下面的两个区间：（ X 表示被选进集合中）
[1 3 4] + [5 5 4] -> [X . X] + [X . X] -> [. X . X . X]
因为 X 互不相邻，合并的时候要强制一个区间的端点不选（即当它不存在）。
因此我们要计算四个值。
同时为了辅助合并，还要记 $lm(l,r,0/1/2/3)$ 表示 $[l,r]$ 这个区间在 $0/1/2/3$ 这四种情况下左端点有没有被选， $rm(l,r,0/1/2/3)$ 右端点同理。
分类讨论维护即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
char ch = getchar();
int x = 0, pd = 0;
while (ch < '0' || ch > '9') pd |= ch == '-', ch = getchar();
while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
return pd ? -x : x;
}
const int maxn = 100005;
int n, m, a[maxn];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define lson ls,l,mid
#define rson rs,mid+1,r
bool lm[maxn << 2][4], rm[maxn << 2][4];
ll s[maxn << 2][4];
void pushup(int o, int l, int r) {
int mid = (l + r) >> 1;
if (rm[ls][0] && lm[rs][0]) {
if (a[mid] >= a[mid + 1]) {
lm[o][0] = lm[ls][0], rm[o][0] = rm[rs][1];
s[o][0] = s[ls][0] + s[rs][1];
} else{
lm[o][0] = lm[ls][2], rm[o][0] = rm[rs][0];
s[o][0] = s[ls][2] + s[rs][0];
}
} else lm[o][0] = lm[ls][0], rm[o][0] = rm[rs][0], s[o][0] = s[ls][0] + s[rs][0];
if (rm[ls][1] && lm[rs][0]) {
if (a[mid] >= a[mid + 1]) {
rm[o][1] = rm[rs][1];
s[o][1] = s[ls][1] + s[rs][1];
} else {
rm[o][1] = rm[rs][0];
s[o][1] = s[ls][3] + s[rs][0];
}
} else rm[o][1] = rm[rs][0], s[o][1] = s[ls][1] + s[rs][0];
if (rm[ls][0] && lm[rs][2]) {
if (a[mid] >= a[mid + 1]) {
lm[o][2] = lm[ls][0];
s[o][2] = s[ls][0] + s[rs][3];
} else {
lm[o][2] = lm[ls][2];
s[o][2] = s[ls][2] + s[rs][2];
}
} else lm[o][2] = lm[ls][0], s[o][2] = s[ls][0] + s[rs][2];
if (rm[ls][1] && lm[rs][2]) {
if (a[mid] >= a[mid + 1]) s[o][3] = s[ls][1] + s[rs][3];
else s[o][3] = s[ls][3] + s[rs][2];
} else s[o][3] = s[ls][1] + s[rs][2];
}
void build(int o, int l, int r) {
if (l == r) {
s[o][0] = a[l] = read();
lm[o][0] = rm[o][0] = 1;
return;
}
int mid = (l + r) >> 1;
build(lson), build(rson), pushup(o, l, r);
}
void upd(int o, int l, int r, int x) {
if (l == r) { s[o][0] = a[l]; return; }
int mid = (l + r) >> 1;
if (x <= mid) upd(lson, x);
else upd(rson, x);
pushup(o, l, r);
}
int main() {
n = read();
build(1, 1, n);
m = read();
while (m--) {
int x = read(), y = read();
a[x] = y, upd(1, 1, n, x);
printf("%lld\n", s[1][0]);
}
return 0;
}
```