Problem : 362 - 1C. 歷史研究

Problem Statistics

Solved Member: 12　　Submission: 77　　User Tried: 13

Statement:

為了做歷史研究，考古學家記錄了某段時間連續 N 天發生的事情。

他將這 N 天每天發生的事情寫成依照重要程度寫成一個序列 X。第 i 天發生的事前用數列中第 i 個數字 X_i 表示。並且他會重複分析下列的事情：

1. 在這 N 天中挑選連續的一個區間
2. 事件 t 的重要度定義為： t * (t在這個期間內發生幾次)
3. 將所有事件的重要性計算以後，計算最大的重要度

Input:Output:

這題會有多筆測資，請輸入到EOF為止

每一筆測資中：
第一行有兩個整數 N,Q，代表數列的長度和詢問的次數。
第二行有 N 個整數 X₁, X₂, ..., X_N，代表每天發生的事件。
接下來 Q 行，每行有兩個數字 A_i, B_i，代表詢問第 A_i 天到第 B_i 天之間重要度最大事件的重要度為何。

限制：
1 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ X_i ≤ 1000000000
1 ≤ A_i ≤ B_i ≤ N

Subtask 1：(5分)
N ≤ 100
Q ≤ 100
每個輸入檔只有 1 筆測資

Subtask 2：(10分)
N ≤ 5000
Q ≤ 5000
每個輸入檔只有 1 筆測資

Subtask 3：(25分)
不存在滿足 A_i ≤ A_j ≤ B_j ≤ B_i 的兩筆詢問
輸入檔有 20 筆測資

Subtask 4：
輸入檔有 25 筆測資

輸出 Q 行，代表每一筆詢問最大的重要度。

Sample Input:Sample Output:

SAMPLE A:
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4

SAMPLE B:
8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8
8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8

SAMPLE C:
12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8

SAMPLE A:
9
8
8
16
16

SAMPLE B:
27
18
19
19
27
18
19
19

SAMPLE C:
18
18
9
30
18
15
17
30
18
15
18
16
30
15
15

HINT:

SAMPLE A 中

詢問4：
事件 7 的重要性為：7*1 = 7
事件 8 的重要性為：8*2 = 16
事件 9 的重要性為：9*1 = 9
因此輸出 16

詢問5：
事件 7 的重要性為：7*1 = 7
事件 8 的重要性為：8*2 = 16
事件 9 的重要性為：9*0 = 0
因此輸出 16

Source:

2013/2014 JOI 合宿 1模（日本IOI國手考）

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	500ms	524288kb
0-2	500ms	524288kb
0-3	500ms	524288kb
1-1	500ms	524288kb	5
1-2	500ms	524288kb
1-3	500ms	524288kb
1-4	500ms	524288kb
1-5	500ms	524288kb
1-6	500ms	524288kb
1-7	500ms	524288kb
1-8	500ms	524288kb
1-9	500ms	524288kb
1-10	500ms	524288kb
1-11	500ms	524288kb
1-12	500ms	524288kb
1-13	500ms	524288kb
1-14	500ms	524288kb
1-15	500ms	524288kb
2-1	1000ms	524288kb	10
2-2	1000ms	524288kb
2-3	1000ms	524288kb
2-4	1000ms	524288kb
2-5	1000ms	524288kb
2-6	1000ms	524288kb
2-7	1000ms	524288kb
2-8	1000ms	524288kb
2-9	1000ms	524288kb
2-10	1000ms	524288kb
2-11	1000ms	524288kb
2-12	1000ms	524288kb
2-13	1000ms	524288kb
2-14	1000ms	524288kb
2-15	1000ms	524288kb
2-16	1000ms	524288kb
2-17	1000ms	524288kb
2-18	1000ms	524288kb
2-19	1000ms	524288kb
2-20	1000ms	524288kb
3	60000ms	524288kb	25
4	180000ms	524288kb	60