TopCoder

User's AC Ratio

95.0% (57/60)

Submission's AC Ratio

43.9% (145/330)

Tags

Description

還記得你嗎?並不是房屋銷售員那個你,而是烏龜國的那個你(*)。
話說21年前,你在海上遇到了烏龜國王──小明。

「小明……你怎麼變成烏龜國王了?」
『我才要問你,你怎麼在這裡?』士別三日,小明的聲音變得很老成。
「沒有啊,老朋友一場,來聊個天吧。」你被他的聲音所懾,一時語無倫次。
『聊個天?那為什麼你手上拿著西瓜刀?』小明疑惑著望著你。
「……因為要把你抓去給RK!!」你陡然躍起,大刀一揮往小明身上劈去。

然後你就掉進海裡去了。

「……不,我是主角,我不會這麼容易淹死的……」你想著,奮力往上游。

然後你就死了。

原來死掉是這種感覺啊,就這樣出師未捷身先死了,而且不像遊戲中幾十秒後還可以再生。
你越想越不開心,哪有主角這麼容易翹掉的故事!你決定去找死神理論。

死神看了你一眼,咬了口蘋果:『你想要復活也可以,但是……』它把蘋果核吐在你身上。
『你要幫我做一點事。』它說著把你帶到一個廣場。

『這個廣場是一條直線,每個位置都有一個高度。每次我們要復活一個靈魂時要選擇一個區域,
算出它的《阻礙值》多大,之後就需要付出這麼多的靈力來復活那個靈魂。』
它又拿起了另一顆蘋果,繼續說道:『你只要幫我計算阻礙值我就可以把你復活,
一個區域[L, R]的阻礙值就是有多少數對(i, j)符合L ≤ i < j ≤ R並且i的高度比j的高度還高。』

你為了回到烏龜國,只好接下了這個任務。

Input Format

第一行有兩個正整數N、Q,表示廣場長度為N且有Q個靈魂要復活。
第二行有N個正整數Hi,依序表示每個位置的高度。1 ≤ Hi ≤ N、任兩個位置高度不相等。
接下來有Q行,每行有兩個數字Lj、Rj。表示該個靈魂的復活儀式區域。

對於所有測試測資,N ≤ 23,000 、Q ≤ 200,000,1 ≤ L ≤ R ≤ N。

Output Format

輸出Q行,代表對每個靈魂復活區域的阻礙值。

Sample Input 1

6 3
1 3 2 6 4 5
1 3
2 4
1 6

Sample Output 1

1
1
3

Hints

這個死神姓名絕對不是路X或X克、它也絕對不喜歡亂丟筆記本。

Problem Source

原TIOJ1694 / ABCLS Contest, Problem D

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 5
19 18 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 3
3 5000 65536 262144 4
4 5000 65536 262144 5
5 5000 65536 262144 6
6 5000 65536 262144 7
7 5000 65536 262144 8
8 5000 65536 262144 9
9 5000 65536 262144 10
10 5000 65536 262144 11
11 5000 65536 262144 12
12 5000 65536 262144 13
13 5000 65536 262144 14
14 5000 65536 262144 15
15 5000 65536 262144 16
16 5000 65536 262144 17
17 5000 65536 262144 18
18 5000 65536 262144 19