還記得你嗎?並不是房屋銷售員那個你,而是烏龜國的那個你(*)。
話說21年前,你在海上遇到了烏龜國王──小明。
「小明……你怎麼變成烏龜國王了?」
『我才要問你,你怎麼在這裡?』士別三日,小明的聲音變得很老成。
「沒有啊,老朋友一場,來聊個天吧。」你被他的聲音所懾,一時語無倫次。
『聊個天?那為什麼你手上拿著西瓜刀?』小明疑惑著望著你。
「……因為要把你抓去給RK!!」你陡然躍起,大刀一揮往小明身上劈去。
然後你就掉進海裡去了。
「……不,我是主角,我不會這麼容易淹死的……」你想著,奮力往上游。
然後你就死了。
原來死掉是這種感覺啊,就這樣出師未捷身先死了,而且不像遊戲中幾十秒後還可以再生。
你越想越不開心,哪有主角這麼容易翹掉的故事!你決定去找死神理論。
死神看了你一眼,咬了口蘋果:『你想要復活也可以,但是……』它把蘋果核吐在你身上。
『你要幫我做一點事。』它說著把你帶到一個廣場。
『這個廣場是一條直線,每個位置都有一個高度。每次我們要復活一個靈魂時要選擇一個區域,
算出它的《阻礙值》多大,之後就需要付出這麼多的靈力來復活那個靈魂。』
它又拿起了另一顆蘋果,繼續說道:『你只要幫我計算阻礙值我就可以把你復活,
一個區域[L, R]的阻礙值就是有多少數對(i, j)符合L ≤ i < j ≤ R並且i的高度比j的高度還高。』
你為了回到烏龜國,只好接下了這個任務。
第一行有兩個正整數N、Q,表示廣場長度為N且有Q個靈魂要復活。
第二行有N個正整數Hi,依序表示每個位置的高度。1 ≤ Hi ≤ N、任兩個位置高度不相等。
接下來有Q行,每行有兩個數字Lj、Rj。表示該個靈魂的復活儀式區域。
對於所有測試測資,N ≤ 23,000 、Q ≤ 200,000,1 ≤ L ≤ R ≤ N。
輸出Q行,代表對每個靈魂復活區域的阻礙值。
這個死神姓名絕對不是路X或X克、它也絕對不喜歡亂丟筆記本。
原TIOJ1694 / ABCLS Contest, Problem D
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 |