Mountains

题目描述

注意：本题时间限制为 5s，是默认值的 2.5 倍。内存限制是默认值的 2 倍。 在 Farmer John 的农场边缘有一排 $N$（$1 \leq N \leq 2000$）座等间距的山。它们可以表示为高度数组 $h_1,h_2,\dots,h_N$。 对于一座山 $i$，如果从山 $i$ 的山顶看向另一座山 $j$ 的山顶的视线不会被更高的山挡住，那么山 $i$ 就能看到山 $j$。形式化地，对于两座山 $i < j$，当且仅当不存在 $k$ 使得 $i < k < j$ 且点 $(k, h_k)$ 位于连接 $(i, h_i)$ 与 $(j, h_j)$ 的线段之上时，它们互相可见。 有 $Q$（$1 \leq Q \leq 2000$）次更新操作，每次会使某一座山的高度增加。请在每次更新后，求互相可见的山的无序对总数。

输入格式

第 $1$ 行包含 $N$。 第 $2$ 行包含 $N$ 个高度 $h_1,h_2,\dots,h_N$（对每个 $i$，$0 \leq h_i \leq 10^9$）。 第 $3$ 行包含 $Q$。 第 $4$ 行到第 $3+Q$ 行包含 $x$、$y$（$1 \leq x \leq N$，$1 \leq y$），其中 $x$ 是山的下标，$y$ 是高度增加的量。保证更新后该山的新高度至多为 $10^9$。

输出格式

输出 $Q$ 行，每行表示对应更新之后，互相可见的山的无序对总数。

5
2 4 3 1 5
3
4 3
1 3
3 2

7
10
7

提示

起初，以下山对互相可见：$(1, 2)$、 $(2, 3)$、$(2, 5)$、$(3, 4)$、$(3, 5)$、$(4, 5)$，共计 $6$ 对。 第一次更新后，山 $4$ 的高度变为 $4$，这不会挡住任何可见性，但会使得 $4$ 现在可以看到 $2$，因此新答案为 $7$。 第二次更新后，山 $1$ 的高度变为 $5$，这不会挡住任何可见性，但会使得 $1$ 现在可以看到 $3$、$4$ 和 $5$，因此新答案为 $10$。 第三次更新后，山 $3$ 的高度变为 $5$，这会阻挡山 $1$ 看到山 $4$，阻挡山 $2$ 看到山 $4$ 和 $5$，并且它自身并不会看到更多山，因为它已经能看到所有山，因此新答案为 $7$。 SCORING: 测试点 2-5 满足 $N, Q\le 100$。 测试点 6-11 满足 $Q \leq 10$。 测试点 12-21 没有额外限制。 题目来源：Joe Li 和 Larry Xing

标签: USACO|2022|Gold

来源

USACO|2022|Gold