← 返回题目列表

Codeforces · 1864/F

F. 奇异查询

中文机器翻译题面 查看原题

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 \le j \leq m$$$、$$$z_j \ge 0$$$ 和 $$$1 \le x_j \le y_j \leq n$$$ (这里 $$$[x_j, y_j]$$$ 对应于序列的片段);
- 对于任何 $$$1 \le j < k \le 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}]=\var什么都没有$$$;
- 对于任何 $$$1 \le i \le n$$$,使得 $$$l \le a_i \leq r$$$,$$$$$${\large a_i = \sum\limits_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j 成立。 }$$$$$$

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\le n,q\le 10^6$$$)。

第二行包含 $$$n$$$ 整数整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。

接下来的 $$$q$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1\le l\le r\le n$$$),代表一个查询。

输出

对于每个查询,在单独的行上输出该查询的答案。

示例

输入 #1

10 8
1 6 2 3 2 6 3 10 1 2
1 10
2 2
3 3
2 3
1 3
3 6
4 6
5 5

输出 #1

8
1
1
3
5
3
1
0

输入 #2

3 1
1 3 2
1 3

输出 #2

3

注意

在第一个测试用例中,考虑第二个查询,当 $$$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)\}$$$ 无效,因为两个线段相交,但都不包含在另一个线段内。