CF1572F Stations

有 $n$ 个城市排成一排，编号从 $1$ 到 $n$。 这些城市将建设广播站。第 $i$ 个城市的广播站高度为 $h_i$，广播范围为 $w_i$。如果满足以下条件，广播站可以向城市 $j$ 发送信息： - $i \le j \le w_i$，并且 - 对于所有满足 $i < k \le j$ 的 $k$，都有 $h_k < h_i$。 换句话说，第 $i$ 个城市的广播站可以向城市 $j$ 发送信息，当且仅当 $j \ge i$，$j$ 在第 $i$ 个广播站的广播范围内，并且在区间 $[i, j]$ 内，第 $i$ 个城市的高度严格大于其他所有城市（包括 $j$）。 一开始，每个城市 $i$ 的 $h_i = 0$，$w_i = i$。 接下来会有 $q$ 个事件。第 $i$ 个事件有以下两种可能： - 城市 $c_i$ 会重建其广播站，使其高度严格高于所有广播站，并将 $w_{c_i}$ 设为 $g_i$。 - 询问：对于每个城市 $j$，$b_j$ 表示有多少个广播站可以向城市 $j$ 发送信息。请输出所有满足 $l_i \le j \le r_i$ 的 $b_j$ 之和。 你的任务是处理所有事件，并对所有询问输出答案。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$），表示城市数量和事件数量。 接下来 $q$ 行，每行描述一个事件。第 $i$ 行以一个整数 $p_i$（$p_i = 1$ 或 $p_i = 2$）开头。 如果 $p_i = 1$，表示重建广播站，接下来两个整数 $c_i$ 和 $g_i$（$1 \le c_i \le g_i \le n$），表示在哪个城市重建广播站以及新的广播范围。 如果 $p_i = 2$，表示一次询问，接下来两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示询问的城市区间。

对于每个询问，输出一行，表示在给定区间内所有 $b_j$ 的和。

在第一个测试用例中，重建前后，只有第 $1$ 个广播站能覆盖城市 $1$。 在第二个测试用例中，每次重建后，数组 $b$ 如下： 1. $[1, 1, 1, 2, 1]$； 2. $[1, 2, 2, 3, 2]$； 3. $[1, 2, 2, 1, 2]$； 4. $[1, 1, 2, 1, 2]$； 5. $[1, 1, 2, 1, 1]$。 由 ChatGPT 4.1 翻译