我们有一个长度为 $n$ 的数组 $a$，需要支持 $m$ 次区间加操作，每次操作后询问最长的"山峰"子数组的长度。

山峰定义：存在 $k \in [l, r]$，使得：

a l < a l + 1 < ⋯ < a k

a k + 1

⋯

a r a l ​ <a l+1 ​ <⋯<a k ​

a k+1 ​ ⋯>a r ​

即先严格递增，再严格递减（允许只有递增或只有递减）。

关键转化

1. 差分数组的引入 定义差分数组 $d_i = a_{i+1} - a_i$，其中 $1 \le i < n$。

区间加操作 $[l, r]$ 加上 $d$ 对差分的影响：

$d_{l-1}$ 增加 $d$（如果 $l > 1$）

$d_r$ 减少 $d$（如果 $r < n$）

其他 $d_i$ 不变

因此，区间加操作转化为差分数组上的单点修改。

2. 山峰与差分符号的关系 对于子数组 $a_l, a_{l+1}, \dots, a_r$ 是山峰：

如果 $l < k$，则 $d_l, d_{l+1}, \dots, d_{k-1} > 0$（严格递增段）

如果 $k < r$，则 $d_k, d_{k+1}, \dots, d_{r-1} < 0$（严格递减段）

$d_k$ 可以是任意值（因为 $a_k$ 是峰值）

因此，山峰对应差分数组中的一段连续子数组，其符号模式为：

若干个 $+1$（正数）

接着若干个 $-1$（负数）

中间不能有 $0$（因为要求严格）

定义符号函数：

s i g n ( x )

{ 1 x

0 − 1 x < 0 0 x

0 sign(x)= ⎩ ⎨ ⎧ ​

1 −1 0 ​

x>0 x<0 x=0 ​

那么山峰对应一段连续的 $sign$ 序列，其模式为：若干个 $1$ 后跟若干个 $-1$。

3. 问题转化 原问题转化为：

维护差分数组 $d$ 和其符号数组 $s$

支持单点修改（更新 $d$ 和 $s$）

每次询问最长的连续子数组，其符号序列为：$1,1,\dots,1,-1,-1,\dots,-1$（允许全 $1$ 或全 $-1$）

数据结构设计 使用线段树维护差分数组的符号信息。每个节点存储：

cpp struct Node { int len; // 区间长度（差分数组的长度） int pre_inc; // 从左边开始的最长连续正段长度 int pre_dec; // 从左边开始的最长连续负段长度 int suf_inc; // 从右边结束的最长连续正段长度 int suf_dec; // 从右边结束的最长连续负段长度 int best; // 区间内最长山峰长度（差分段的长度） int lsign, rsign; // 左右端点的符号 }; 合并操作 对于两个子节点 left 和 right，合并得到 res：

基本信息：

res.len = left.len + right.len

res.lsign = left.lsign

res.rsign = right.rsign

前缀信息：

res.pre_inc = left.pre_inc

如果 left.pre_inc == left.len 且 left.rsign == 1 且 right.lsign == 1： 则 res.pre_inc = left.len + right.pre_inc

类似地处理 res.pre_dec

后缀信息：

对称地处理 res.suf_inc 和 res.suf_dec

最优答案：

res.best = max(left.best, right.best)

如果 left.rsign == 1 且 right.lsign == -1： 则 res.best = max(res.best, left.suf_inc + right.pre_dec)

叶子节点 对于单个差分值 $d$：

如果 $d > 0$（符号为 $1$）：

text pre_inc = suf_inc = 1 pre_dec = suf_dec = 0 best = 1 如果 $d < 0$（符号为 $-1$）：

text pre_inc = suf_inc = 0 pre_dec = suf_dec = 1 best = 1 如果 $d = 0$（符号为 $0$）：

text pre_inc = suf_inc = 0 pre_dec = suf_dec = 0 best = 0 算法流程 初始化 读入 $n$ 和数组 $a$

计算差分数组 $d_i = a_{i+1} - a_i$（$1 \le i < n$）

计算符号数组 $s_i = sign(d_i)$

建线段树（如果 $n = 1$，没有差分数组）

处理每个操作 对于操作 $(l, r, d)$：

如果 $l > 1$：

$d_{l-1} \leftarrow d_{l-1} + d$

更新 $s_{l-1}$

更新线段树位置 $l-1$

如果 $r < n$：

$d_r \leftarrow d_r - d$

更新 $s_r$

更新线段树位置 $r$

查询答案：

如果 $n = 1$，答案恒为 $1$

否则，答案 $= \max(1, tree[1].best + 1)$ （因为差分段长度 $best$ 对应 $best+1$ 个塔）

复杂度分析 建树：$O(n)$

每次操作：$O(\log n)$（最多两次单点更新）

总复杂度：$O((n + m) \log n)$

对于 $n, m \le 3 \times 10^5$，完全可行。

代码实现 cpp #include <bits/stdc++.h> using namespace std;

const int MAXN = 300005;

struct Node { int len; // 区间长度 int pre_inc; // 最长前缀正段 int pre_dec; // 最长前缀负段 int suf_inc; // 最长后缀正段 int suf_dec; // 最长后缀负段 int best; // 区间内最长山峰 int lsign, rsign; // 左右端点符号 };

int n, m; long long a[MAXN]; long long diff[MAXN]; int sign[MAXN]; Node tree[MAXN * 4];

int get_sign(long long x) { if (x > 0) return 1; if (x < 0) return -1; return 0; }

Node merge(Node left, Node right) { if (left.len == 0) return right; if (right.len == 0) return left;

Node res;
res.len = left.len + right.len;
res.lsign = left.lsign;
res.rsign = right.rsign;

// 前缀
res.pre_inc = left.pre_inc;
if (left.pre_inc == left.len && left.rsign == 1 && right.lsign == 1) {
    res.pre_inc = left.len + right.pre_inc;
}

res.pre_dec = left.pre_dec;
if (left.pre_dec == left.len && left.rsign == -1 && right.lsign == -1) {
    res.pre_dec = left.len + right.pre_dec;
}

// 后缀
res.suf_inc = right.suf_inc;
if (right.suf_inc == right.len && right.lsign == 1 && left.rsign == 1) {
    res.suf_inc = right.len + left.suf_inc;
}

res.suf_dec = right.suf_dec;
if (right.suf_dec == right.len && right.lsign == -1 && left.rsign == -1) {
    res.suf_dec = right.len + left.suf_dec;
}

// 最优答案
res.best = max(left.best, right.best);
if (left.rsign == 1 && right.lsign == -1) {
    res.best = max(res.best, left.suf_inc + right.pre_dec);
}

return res;

}

void build(int id, int l, int r) { if (l == r) { int sgn = sign[l]; tree[id].len = 1; tree[id].lsign = tree[id].rsign = sgn; if (sgn == 1) { tree[id].pre_inc = tree[id].suf_inc = 1; tree[id].pre_dec = tree[id].suf_dec = 0; tree[id].best = 1; } else if (sgn == -1) { tree[id].pre_inc = tree[id].suf_inc = 0; tree[id].pre_dec = tree[id].suf_dec = 1; tree[id].best = 1; } else { tree[id].pre_inc = tree[id].suf_inc = 0; tree[id].pre_dec = tree[id].suf_dec = 0; tree[id].best = 0; } return; } int mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); tree[id] = merge(tree[id * 2], tree[id * 2 + 1]); }

void update(int id, int l, int r, int pos) { if (l == r) { int sgn = sign[pos]; tree[id].lsign = tree[id].rsign = sgn; if (sgn == 1) { tree[id].pre_inc = tree[id].suf_inc = 1; tree[id].pre_dec = tree[id].suf_dec = 0; tree[id].best = 1; } else if (sgn == -1) { tree[id].pre_inc = tree[id].suf_inc = 0; tree[id].pre_dec = tree[id].suf_dec = 1; tree[id].best = 1; } else { tree[id].pre_inc = tree[id].suf_inc = 0; tree[id].pre_dec = tree[id].suf_dec = 0; tree[id].best = 0; } return; } int mid = (l + r) / 2; if (pos <= mid) update(id * 2, l, mid, pos); else update(id * 2 + 1, mid + 1, r, pos); tree[id] = merge(tree[id * 2], tree[id * 2 + 1]); }

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

cin >> n;
for (int i = 1; i <= n; i++) {
    cin >> a[i];
}

// 构建差分数组
for (int i = 1; i < n; i++) {
    diff[i] = a[i + 1] - a[i];
    sign[i] = get_sign(diff[i]);
}

// 建树
if (n > 1) {
    build(1, 1, n - 1);
}

cin >> m;
while (m--) {
    int l, r;
    long long d;
    cin >> l >> r >> d;
    
    // 更新差分数组
    if (l > 1) {
        diff[l - 1] += d;
        sign[l - 1] = get_sign(diff[l - 1]);
        update(1, 1, n - 1, l - 1);
    }
    
    if (r < n) {
        diff[r] -= d;
        sign[r] = get_sign(diff[r]);
        update(1, 1, n - 1, r);
    }
    
    // 查询答案
    int ans = 1;  // 至少一个塔
    if (n > 1) {
        ans = max(ans, tree[1].best + 1);
    }
    cout << ans << "\n";
}

return 0;

} 关键点总结 差分转化：将区间加操作转化为单点修改，大大简化了问题

符号维护：只关心差分的正负，不关心具体数值

线段树设计：维护前缀、后缀和跨区间的最优组合

合并策略：只有"正+负"的跨区间组合才是合法的山峰

答案计算：差分段长度 $+1$ 即为塔的数量

这个解法充分利用了差分数组的性质和线段树的区间合并能力，是处理此类动态区间问题的经典方法。