AdditionalFile5625.zip

#5625. 「KTSC 2026 R2」观测塔

标签: 传统 | 时间限制: 6000 ms | 内存限制: 2048 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "tower.h"。

题目描述

题目译自 2026년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T4 「관측탑」

现按顺序安装了从 $0$ 号到 $N-1$ 号共 $N$ 座观测塔。对于 $0 \leq i \leq N-1$，$i$ 号观测塔的高度为 $H[i]$。此外，每座观测塔都有一个观测分值 $S[i]$，初始时所有观测分值均为 $0$。

对于满足 $0 \leq i < j \leq N-1$ 的 $i$ 和 $j$，$i$ 号观测塔能够观测到 $j$ 号观测塔，当且仅当对于所有满足 $i \leq k \leq j-1$ 的 $k$，都有 $H[k] < H[j]$。请注意，满足 $j \leq i$ 的观测塔是不可被观测的。

当某座观测塔进行一次“观测”时，该观测塔能够观测到的所有观测塔的观测分值都会增加 $1$。 现在发生了 $Q$ 个事件，每个事件属于以下三种类型之一：

• 观测：对于满足 $0 \leq I \leq N-2$ 的 $I$，由 $I$ 号观测塔进行一次观测。
• 测量：对于满足 $0 \leq L \leq R \leq N-1$ 的 $L$ 和 $R$，计算从 $L$ 号观测塔到 $R$ 号观测塔的观测分值之和，即计算 $S[L] + \cdots + S[R]$。
• 地壳变动：对于满足 $0 \leq L \leq R \leq N-1$ 的 $L$、 $R$ 以及数值 $V$，将从 $L$ 号观测塔到 $R$ 号观测塔的每座观测塔的高度改变 $V$，即在 $H[L], \ldots, H[R]$ 的值上分别加上 $V$。

观测事件可以用数组 $[I]$ 表示，测量事件可以用数组 $[L, R]$ 表示，地壳变动事件可以用数组 $[L, R, V]$ 表示。请注意，由于每种事件对应的数组大小不同，你可以根据数组的大小来区分事件的具体类型。

所有事件按从 $0$ 号到 $Q-1$ 号的顺序依次发生，其中第 $i$ 号事件为 $E[i]$。 设总的测量事件个数为 $K$，并将这些测量事件按发生顺序依次称为第 $0$ 号测量事件到第 $K-1$ 号测量事件。你需要计算出所有测量事件的结果，即从第 $0$ 号测量事件到第 $K-1$ 号测量事件的计算值。

实现细节

你需要实现以下函数：

vector<long long> tower_events(vector<int> H, vector<vector<int>> E)

• $H$：大小为 $N$ 的整数数组。
• $E$：由数组组成的数组，大小为 $Q$。其中的每个数组代表一个事件。
• 该函数应返回一个大小为 $K$ 的整数数组 $X$。$X[i]$ 应为第 $i$ 号测量事件的结果（$0 \leq i \leq K-1$）。
• 该函数仅会被调用一次。

样例 1

考虑如下调用：

tower_events([1, 2, 3, 4, 5], [[0], [1, 3], [1, 2, 1], [1], [0, 4]])

直译样例解释：

• 第一个事件（观测 $0$）发生后，$H=[1,2,3,4,5], S=[0,1,1,1,1]$。
• 第二个事件是第 $0$ 号测量事件，其结果为 $S[1]+S[2]+S[3]=3$。
• 第三个事件（地壳变动 $[1, 2, 1]$）发生后，$H=[1,3,4,4,5], S=[0,1,1,1,1]$。
• 第四个事件（观测 $1$）发生后，$H=[1,3,4,4,5], S=[0,1,2,1,2]$。
• 最后一个事件是第 $1$ 号测量事件，其结果为 $S[0]+\cdots+S[4]=6$。

因此，函数应返回 $[3, 6]$。

样例 2

考虑如下调用：

tower_events([7, 7, 9, 5, 8, 10, 2, 9, 2, 2], [[1], [6, 8, 6], [1], [1, 9], [3], [8], [2, 4], [5], [1, 1, 7], [1], [0, 9]])

函数应返回 $[5, 3, 10]$。

数据范围与提示

对于所有输入数据，满足：

• $5 \leq N \leq 1000000$
• $1 \leq Q \leq 250000$
• $1 \leq H[i] \leq 10^{9}$ $(0 \leq i \leq N-1)$
• 对于每个观测事件，$0 \leq I \leq N-2$。
• 对于每个测量事件，$0 \leq L \leq R \leq N-1$。
• 对于每个地壳变动事件，$0 \leq L \leq R \leq N-1$。
• 对于每个地壳变动事件，$-10^{9} \leq V \leq 10^{9}$。
• 在每次地壳变动事件后，所有观测塔的高度均不小于 $1$，即 $1 \leq H[i]$ $(0 \leq i \leq N-1)$。
• 测量事件至少会发生一次。

详细子任务附加限制及分值如下表所示。

示例评测程序

示例评测程序的输入格式如下：

• 第一行：$N \ Q$
• 第二行：$H[0] \ H[1] \ \ldots \ H[N-1]$
• 对于所有 $0 \leq i \leq Q-1$：
  • 第 $3+i$ 行：$|E[i]| \ E[i][0] \ \ldots \ E[i][|E[i]|-1]$

示例评测程序按以下格式输出答案：

• 对于所有 $0 \leq i \leq K-1$：
  • 第 $1+i$ 行：$X[i]$