← 返回题目列表

Codeforces · 2210/F

F. 一个简单的问题

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

对于长度为 $$$m$$$ 的数组 $$$b$$$,定义 $$$f(b)$$$ 如下:

  • 考虑长度为 $$$m$$$ 的数组 $$$c$$$ 美丽 当且仅当对于每个 $$$1 \le i \le m$$$,$$$c_i$$$ 等于 $$$\max(b_1,b_2,\ldots,b_i)$$$ 或 $$$\min(b_1,b_2,\ldots,b_i)$$$。然后,$$$f(b)$$$ 被定义为所有漂亮数组上的最大反转次数$$$^{\text{*}}$$$。

给你一个排列$$$^{\text{†}}$$$ $$$p$$$,长度为$$$n$$$。您需要回答 $$$q$$$ 查询,其中每个查询包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$)。对于每个查询,请计算 $$$f([p_l,p_{l+1},\ldots,p_{r}])$$$。

$$$^{\text{*}}$$$长度为$$$n$$$的数组$$$a$$$的反转次数被定义为整数对$$$(i,j)$$$的数量,使得$$$1 \le i \lt j \le n$$$和$$$a_i \gt a_j$$$。

$$$^{\text{†}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数$$$n$$$和$$$q$$$ ($$$1 \le n,q \le 10^6$$$),分别代表$$$p$$$的长度和查询的数量。

第二行包含 $$$n$$$ 不同的整数 $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$),表示排列 $$$p$$$。

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

保证所有测试用例的$$$n$$$总和和$$$q$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出 $$$q$$$ 个整数,其中第 $$$i$$$ 个整数表示第 $$$i$$$ 个查询的答案。

示例

输入
复制

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

输出
复制

0
0
1
2
2
11
31
2
11
13
0

注意

在第一个示例测试用例中:

  • 对于第二个查询,子数组是 $$$[1,2]$$$。您可以采用 $$$c=[\min(1),\min(1,2)]=[1,1]$$$,其中有 $$$0$$$ 反转。可以证明,这是您可以在所有漂亮数组上获得的最大反转次数。

在第四个示例测试用例中:

  • 对于第三个查询,子数组为 $$$[3,6,4,9]$$$。您可以采用 $$$c=[\max(3),\max(3,6),\min(3,6,4),\min(3,6,4,9)]=[3,6,3,3]$$$,这将给出总共 $$$2$$$ 的反转。可以证明,这是您可以在所有漂亮数组上获得的最大反转次数。