题解：P15589 [KTSC 2026] 瞭望塔 / Observation Tower
题目传送门
P15589 [KTSC 2026] 瞭望塔 / Observation Tower
题意
每一个塔它都有一个高度，和一个分数。 我们定义一个严格上升的子序列成为一个塔能被另一个塔瞭望到。 题目给给定了三个操作：
- 瞭望：在
I塔上执行一次瞭望操作，即将后面的一个最长的严格上升子序列的位置的瞭望分数都加一。 - 测量：求一段区间的区间和。
- 平移：对一段区间进行区间加操作。
思路讲解
看见这样的区间操作，我们的第一反应就是线段树。
既然我们考虑到了线段树，就要考虑我们要用线段树维护哪些信息。我们首先可以知道要维护一个区间加的懒标记和区间和，因为要求任意区间的相对于一个数的严格上升的最长子序列，自然就要维护一个最大值。我们定义一个 cmx 表示在当前这个节点下，在左端点的左边界不受到任何限制的情况下，即这个区间的最多的能被瞭望到的塔的数目，还有维护对于可被瞭望的点进行延迟处理的懒标记。
设想一个函数 pushtag：
它的含义是：在左边界外部有一个最大高度为 maxn，现在我们要给当前区间内所有“大于 maxn 且能突破遮蔽”的点，把 S 加上 v。
-
情况 A：如果
tree[id].mx <= maxn，说明当前区间所有的塔都被外部那个高度为maxn的塔挡住了，一个都看不到，直接return。 -
情况 B：如果
tree[L].mx <= maxn，即左子区间的最大值都被挡住了。那么整个左子区间都不可见，可见点全在右子区间。我们直接递归去更新右子区间，并且右子区间的遮蔽限制依然是maxn。 -
情况 C：如果
tree[L].mx >= maxn，说明左子区间有部分点可见。此时对于右子区间来说，它受到的限制变成了左子区间的最大值（因为可见链必须严格递增）。所以此时需要先下放标记，递归更新左子区间，并打上标记，然后更新右子区间，最后合并信息。
Coding
#include <bits/stdc++.h>
using std::cin; using std::cout;
using std::min; using std::max;
using std::vector;
#define LL long long
const int N = 1e6 + 10;
// 线段树节点
struct node {
LL sum; // S 的区间和
LL mx; // H 的区间最大值
int cmx; // 内部可见链长度（严格后缀最大值个数）
LL add_tag; // H 的加法标记
LL cmx_tag; // 可见点 S 的加法标记
} static tree[N << 2];
// 给节点 id 的高度整体加上 w
static inline void pushadd(int id, LL w) {
tree[id].mx += w; // 最大值整体加 w
tree[id].add_tag += w; // 累积懒标记
}
// 在外部遮挡限制为 maxn 时，区间内还能被看到的点数
static inline int calc(int id, int L, int R, LL maxn) {
if (tree[id].mx <= maxn) return 0; // 全被挡住
if (L == R) return 1; // 叶子且未被挡，可见
int lc = id << 1, rc = lc | 1;
if (tree[id].add_tag != 0) { // 下放高度标记保证 mx 真实
LL t = tree[id].add_tag;
pushadd(lc, t);
pushadd(rc, t);
tree[id].add_tag = 0;
}
int mid = (L + R) >> 1;
if (tree[lc].mx <= maxn) // 左子全被挡，只看右边
return calc(rc, mid + 1, R, maxn);
else // 左子部分可见
return calc(lc, L, mid, maxn) + (tree[id].cmx - tree[lc].cmx);
}
// 由左右子树合并当前节点信息
static inline void push_up(int id, int L, int R) {
int mid = (L + R) >> 1;
int lc = id << 1, rc = lc | 1;
LL mxl = tree[lc].mx, mxr = tree[rc].mx;
tree[id].mx = mxl > mxr ? mxl : mxr; // 取最大高度
tree[id].sum = tree[lc].sum + tree[rc].sum; // 合并 S 之和
if (mxr <= mxl) {
tree[id].cmx = tree[lc].cmx; // 右边全被左边挡住
} else {
tree[id].cmx = tree[lc].cmx + calc(rc, mid + 1, R, mxl); // 右边有突破
}
}
// 建树
static inline void build_tree(int id, int L, int R, const vector<int> &H) {
if (L == R) {
tree[id].sum = 0; // 初始 S 为 0
tree[id].mx = H[L]; // 叶子高度
tree[id].cmx = 1; // 叶子单独可见
return ;
}
int mid = (L + R) >> 1;
build_tree(id << 1, L, mid, H); // 建左子树
build_tree(id << 1 | 1, mid + 1, R, H); // 建右子树
push_up(id, L, R); // 合并
}
// 在遮挡限制 maxn 下，把可见点的 S 加 v
static inline void push_tag(int id, int L, int R, LL maxn, LL v) {
if (tree[id].mx <= maxn) return ; // 情况 A：全被挡
if (L == R) { // 叶子可见，直接更新
tree[id].sum += v * tree[id].cmx;
tree[id].cmx_tag += v;
return ;
}
int lc = id << 1, rc = lc | 1;
if (tree[id].add_tag != 0) { // 下放高度标记
LL t = tree[id].add_tag;
pushadd(lc, t);
pushadd(rc, t);
tree[id].add_tag = 0;
}
int mid = (L + R) >> 1;
if (tree[lc].mx <= maxn) { // 情况 B：左子全被挡
LL old = tree[rc].sum;
push_tag(rc, mid + 1, R, maxn, v);
tree[id].sum += tree[rc].sum - old; // 用差值更新 sum
} else { // 情况 C：左子部分可见
tree[id].cmx_tag += v; // 右子突破部分整体加
tree[id].sum += v * (tree[id].cmx - tree[lc].cmx); // O(1) 更新
LL old = tree[lc].sum;
push_tag(lc, L, mid, maxn, v); // 递归左子
tree[id].sum += tree[lc].sum - old; // 用差值更新 sum
}
}
// 下放懒标记
static inline void push_down(int id, int L, int R) {
int mid = (L + R) >> 1;
int lc = id << 1, rc = lc | 1;
if (tree[id].add_tag != 0) { // 高度标记直接下放
LL t = tree[id].add_tag;
pushadd(lc, t);
pushadd(rc, t);
tree[id].add_tag = 0;
}
if (tree[id].cmx_tag != 0) { // S 标记只传给右子树
LL t = tree[id].cmx_tag;
push_tag(rc, mid + 1, R, tree[lc].mx, t); // 右子受左子最大高度限制
tree[id].cmx_tag = 0;
}
}
// 区间加高度
static inline void add_h(int id, int L, int R, int l, int r, LL v) {
if (r < L || R < l) return ; // 无交集
if (l <= L && R <= r) { // 完全覆盖
pushadd(id, v); // 直接打高度标记
return ;
}
push_down(id, L, R); // 下放
int mid = (L + R) >> 1;
add_h(id << 1, L, mid, l, r, v); // 左
add_h(id << 1 | 1, mid + 1, R, l, r, v); // 右
push_up(id, L, R); // 合并
}
// 处理瞭望操作，mx 随区间最大值动态更新
static inline void add_op(int id, int L, int R, int l, int r, LL &mx) {
if (r < L || R < l) return ; // 无交集
if (l <= L && R <= r) { // 完全覆盖
push_tag(id, L, R, mx, 1); // 遮挡限制 mx，S 加 1
if (tree[id].mx > mx) mx = tree[id].mx; // 更新遮挡限制
return ;
}
push_down(id, L, R);
int mid = (L + R) >> 1;
add_op(id << 1, L, mid, l, r, mx); // 先左后右保证链式更新
add_op(id << 1 | 1, mid + 1, R, l, r, mx);
push_up(id, L, R);
}
// 区间求和 S
static inline LL ask(int id, int L, int R, int l, int r) {
if (r < L || R < l) return 0; // 无交集
if (l <= L && R <= r) return tree[id].sum; // 完全覆盖直接返回
push_down(id, L, R); // 下放
int mid = (L + R) >> 1;
return ask(id << 1, L, mid, l, r) + ask(id << 1 | 1, mid + 1, R, l, r);
}
// 单点查高度
static inline LL get(int id, int L, int R, int x) {
if (L == R) return tree[id].mx; // 叶子直接返回
push_down(id, L, R); // 下放后才能得到真实值
int mid = (L + R) >> 1;
if (x <= mid) return get(id << 1, L, mid, x);
else return get(id << 1 | 1, mid + 1, R, x);
}
// 交互主函数
vector<long long> tower_events(vector<int> H, vector<vector<int>> E) {
int n = (int)H.size();
if (n > 0) build_tree(1, 0, n - 1, H); // 建树
vector<long long> ans;
for (const auto &e : E) {
int siz = (int)e.size();
if (siz == 1) { // 瞭望事件
int I = e[0];
LL mx = get(1, 0, n - 1, I); // 先取塔 I 的高度
if (I + 1 <= n - 1)
add_op(1, 0, n - 1, I + 1, n - 1, mx); // 更新右侧可见点
} else if (siz == 2) { // 测量事件
ans.push_back(ask(1, 0, n - 1, e[0], e[1])); // 区间求和
} else if (e[2] != 0) { // 平移事件，V=0 跳过
add_h(1, 0, n - 1, e[0], e[1], e[2]); // 区间加高度
}
}
return ans;
}