CF1864F Exotic Queries

AquaMoon 给了 RiverHamster 一个整数序列 $a_1, a_2, \dots, a_n$，RiverHamster 又给了你 $q$ 个询问。每个询问由两个整数 $l$ 和 $r$ 表示。 对于每个询问，你可以对序列的任意连续区间多次（也可以不操作）选择一个非负整数，从该区间的所有数中减去相同的值。你不能选择两个相交但不包含关系的区间。你的目标是将所有初始值在 $[l, r]$ 范围内的数变为 $0$，并且操作次数最少。 请注意，每个询问是独立的，数组在每次询问后都会恢复到初始状态。 形式化地，对于每个询问，你需要找到最小的 $m$，使得存在一个序列 $\{(x_j, y_j, z_j)\}_{j=1}^{m}$ 满足以下条件： - 对于任意 $1 \leq j \leq m$，有 $z_j \geq 0$ 且 $1 \leq x_j \leq y_j \leq n$（其中 $[x_j, y_j]$ 表示区间）； - 对于任意 $1 \leq j < k \leq m$，要么 $[x_j, y_j] \subseteq [x_k, y_k]$，要么 $[x_k, y_k] \subseteq [x_j, y_j]$，要么 $[x_j, y_j] \cap [x_k, y_k] = \varnothing$； - 对于任意 $1 \leq i \leq n$，如果 $l \leq a_i \leq r$，则有 $a_i = \sum\limits_{\substack {1 \leq j \leq m \\ x_j \leq i \leq y_j}} z_j$。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示一个询问。

对于每个询问，输出该询问的答案，每行一个。

在第一个测试点中，考虑第二个询问，$l = 2$，$r = 2$。需要操作的元素为 $[a_3, a_5, a_{10}] = [2, 2, 2]$。只需执行操作序列 $\{(2, 10, 2)\}$。 再看第四个询问，$l = 2$，$r = 3$。需要操作的元素为 $[a_3, a_4, a_5, a_7, a_{10}] = [2, 3, 2, 3, 2]$。可以执行操作序列 $\{(1, 10, 2), (4, 4, 1), (7, 7, 1)\}$。 在第二个测试点中，注意操作序列 $\{(1, 2, 1), (2, 3, 2)\}$ 是不合法的，因为两个区间相交但没有包含关系。 由 ChatGPT 4.1 翻译