TopCoder

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

53.9% (55/102)

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

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

Sample Output

1
1
3

Hints

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

Problem Source

原TIOJ1694 / ABCLS Contest, Problem D

Subtasks

For Testdata: 0 ~ 0, Score: 5
For Testdata: 1 ~ 1, Score: 5
For Testdata: 2 ~ 2, Score: 5
For Testdata: 3 ~ 3, Score: 5
For Testdata: 4 ~ 4, Score: 5
For Testdata: 5 ~ 5, Score: 5
For Testdata: 6 ~ 6, Score: 5
For Testdata: 7 ~ 7, Score: 5
For Testdata: 8 ~ 8, Score: 5
For Testdata: 9 ~ 9, Score: 5
For Testdata: 10 ~ 10, Score: 5
For Testdata: 11 ~ 11, Score: 5
For Testdata: 12 ~ 12, Score: 5
For Testdata: 13 ~ 13, Score: 5
For Testdata: 14 ~ 14, Score: 5
For Testdata: 15 ~ 15, Score: 5
For Testdata: 16 ~ 16, Score: 5
For Testdata: 17 ~ 17, Score: 5
For Testdata: 18 ~ 18, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 5000 65536
1 5000 65536
2 5000 65536
3 5000 65536
4 5000 65536
5 5000 65536
6 5000 65536
7 5000 65536
8 5000 65536
9 5000 65536
10 5000 65536
11 5000 65536
12 5000 65536
13 5000 65536
14 5000 65536
15 5000 65536
16 5000 65536
17 5000 65536
18 5000 65536