← 返回题目列表

Codeforces · 1946/F

F. 不需要任何人

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

Oleg 收到了长度为 $$$n$$$ 的排列 $$$a$$$ 作为生日礼物。

Oleg 的朋友 Nechipor 问 Oleg $$$q$$$ 问题,每个问题由两个数字 $$$l$$$ 和 $$$r$$$ 来表征,在回答问题时,Oleg 必须说出任意长度 $$$k \ge 1$$$ 的索引集 $$$(t_1, t_2, \ldots, t_k)$$$ 的数量,使得:

- $$$l \le t_i \le r$$$ 对于从 $$$1$$$ 到 $$$k$$$ 的每个 $$$i$$$。
- $$$t_i < t_{i+1}$$$ 对于从 $$$1$$$ 到 $$$k-1$$$ 的每个 $$$i$$$。
- 对于从 $$$1$$$ 到 $$$k-1$$$ 的每个 $$$i$$$,$$$a_{t_{i+1}}$$$ 可被 $$$a_{t_i}$$$ 整除。

帮助奥列格并回答 Nechipor 的所有问题。

输入

每个测试由多组输入数据组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) - 输入数据的组数。输入数据组的描述如下。

每组输入数据的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 10^6$$$) - 排列的长度和 Nechipor 的问题数量。

每组输入数据的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 排列 $$$a$$$ 本身。

在每组输入数据的接下来的 $$$q$$$ 行中,有两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) - Nechipor 的下一个问题。

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

输出

对于每组输入数据,输出 Nechipor 的所有问题的答案。

示例

输入 #1

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

输出 #1

20 15 18 12 5 5 1 3
1
2 3 2
27

注意

第一组输入数据中的所有合适数组:($$$1$$$)、($$$2$$$)、($$$3$$$)、($$$4$$$)、($$$5$$$)、($$$6$$$)、($$$7$$$)、($$$8$$$)、($$$1, 3$$$)、 ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 6, 7$$$), ($$$2, 3$$$), ($$$2, 4$$$), ($$$2, 5$$$), ($$$2, 6$$$), ($$$2, 7$$$), ($$$2, 8$$$), ($$$2, 6, 7$$$), ($$$6, 7$$$)。

第四组输入数据中的所有合适数组:($$$1$$$)、($$$2$$$)、($$$3$$$)、($$$4$$$)、($$$5$$$)、($$$6$$$)、($$$7$$$)、($$$8$$$)、($$$1, 2$$$)、 ($$$1, 3$$$), ($$$1, 4$$$), ($$$1, 5$$$), ($$$1, 6$$$), ($$$1, 7$$$), ($$$1, 8$$$), ($$$1, 2, 4$$$), ($$$1, 2, 6$$$), ($$$1, 2, 8$$$), ($$$1, 2, 4, 8$$$), ($$$1, 3, 6$$$), ($$$1, 4, 8$$$), ($$$2, 4$$$), ($$$2, 6$$$), ($$$2, 8$$$), ($$$2, 4, 8$$$), ($$$3, 6$$$), ($$$4, 8$$$)。