TopCoder

8e7
$\huge X語言專家 $(TIOJ 1269)

User's AC Ratio

80.0% (12/15)

Submission's AC Ratio

52.1% (38/73)

Tags

Description

最近流行一款新推出的遊戲《糖豆人:終極淘汰賽》(Fall Guys: Ultimate Knockout),這是一款大型派對遊戲,遊戲中會有許多不同種類的關卡,每一輪的關卡都是隨機決定的,而在一輪中會淘汰數量不等的玩家,玩家需要一步步晉級闖關直到留下最後一名獲勝者。

一場遊戲會有很多輪,在每一輪遊戲開始時,所有的玩家會排成一排,每一位玩家都會有一個能力值,不會有任兩個玩家的能力值重複。而雪花菈米發現了遊戲的一個小訣竅,當一個人的能力值比自己相鄰玩家的能力值都還要高的話,那麼該玩家就會晉級,否則該玩家就會被淘汰。

現在給你一整排 $N$ 位遊戲玩家的排列方式,並且進行 $Q$ 場遊戲,第 $i$ 場遊戲會挑出區間 $[l_i,r_i]$ 的玩家進行遊戲,而在遊戲完成後,玩家無論是否被淘汰都會回到原本的位置(也就是說,每場遊戲獨立)。請問對於每一場遊戲,要進行幾輪遊戲才可以有人獲勝?

Input Format

首行輸入兩個正整數 $N,Q$,代表這場遊戲有幾個玩家。
接下來一行有 $N$ 個正整數 $p_i$,代表一開始遊戲玩家的排列方式。
接下來 $Q$ 行,每一行有兩個正整數 $l_i,r_i$,代表第 $i$ 場遊戲決定要挑出區間 $[l_i,r_i]$ 的玩家進行遊戲。

Output Format

輸出 $Q$ 行,第 $i$ 行一個整數,代表第 $i$ 場遊戲要獲勝所需的場數(淘汰到剩下最後一人所需的場數)。

Sample Input 1

5 3
9 5 10 1 6
1 5
2 3
2 5

Sample Output 1

2
1
2

Sample Input 2

10 4
7 2 19 13 18 6 16 3 9 17
1 1
1 10
1 8
1 2

Sample Output 2

0
3
2
1

Hints

測資限制:

  • $1\le N, Q\leq 5\times 10^ 5$。
  • $1\le p_i\leq 10^ 9$。
  • 不會有任兩個玩家的能力值重複。

本題共有 $4$ 組測試題組,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

  1. ($8\%$) $N,Q\le 3000$。
  2. ($31\%$) $l_i=1$。
  3. ($25\%$) $N,Q\le 10^ 5$。
  4. ($36\%$) 無額外限制。

Problem Source

2021 板中TOI模考模擬賽

Subtasks

No. Testdata Range Constraints Score
1 2~15 $N,Q\le 3000$。 8
2 16~27 $l_i=1$。 31
3 2~15, 28~41 $N,Q\le 10^ 5$。 25
4 0~55 無額外限制。 36

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 4
1 3000 524288 65536 4
2 3000 524288 65536 1 3 4
3 3000 524288 65536 1 3 4
4 3000 524288 65536 1 3 4
5 3000 524288 65536 1 3 4
6 3000 524288 65536 1 3 4
7 3000 524288 65536 1 3 4
8 3000 524288 65536 1 3 4
9 3000 524288 65536 1 3 4
10 3000 524288 65536 1 3 4
11 3000 524288 65536 1 3 4
12 3000 524288 65536 1 3 4
13 3000 524288 65536 1 3 4
14 3000 524288 65536 1 3 4
15 3000 524288 65536 1 3 4
16 3000 524288 65536 2 4
17 3000 524288 65536 2 4
18 3000 524288 65536 2 4
19 3000 524288 65536 2 4
20 3000 524288 65536 2 4
21 3000 524288 65536 2 4
22 3000 524288 65536 2 4
23 3000 524288 65536 2 4
24 3000 524288 65536 2 4
25 3000 524288 65536 2 4
26 3000 524288 65536 2 4
27 3000 524288 65536 2 4
28 3000 524288 65536 3 4
29 3000 524288 65536 3 4
30 3000 524288 65536 3 4
31 3000 524288 65536 3 4
32 3000 524288 65536 3 4
33 3000 524288 65536 3 4
34 3000 524288 65536 3 4
35 3000 524288 65536 3 4
36 3000 524288 65536 3 4
37 3000 524288 65536 3 4
38 3000 524288 65536 3 4
39 3000 524288 65536 3 4
40 3000 524288 65536 3 4
41 3000 524288 65536 3 4
42 3000 524288 65536 4
43 3000 524288 65536 4
44 3000 524288 65536 4
45 3000 524288 65536 4
46 3000 524288 65536 4
47 3000 524288 65536 4
48 3000 524288 65536 4
49 3000 524288 65536 4
50 3000 524288 65536 4
51 3000 524288 65536 4
52 3000 524288 65536 4
53 3000 524288 65536 4
54 3000 524288 65536 4
55 3000 524288 65536 4