TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

88.9% (16/18)

Submission's AC Ratio

49.4% (42/85)

Tags

CDQ

Description

「吚~~」

門打開了,

沒有魔法陣,沒有石頭,沒有燈泡,沒有柱子,一片空曠,只剩對面有著一扇門。看來那門...就是終點了呢?

四周甚至都是岩塊...很明顯是臨時加工出來的...基地?堡壘?最後決戰舞台?妁艷不知道...

妁艷雖然覺得這整件事情不太對勁...但他感覺的到他的目的快達成了...

他感覺的到就在那扇門後面,

就在那扇門後面,他的妹妹就在那邊...

妁艷抱著楓音,在他耳邊輕輕地說「楓音,我要過去囉...」

「恩...」楓音有點勉強的說了出口,陪著妁艷踏向那道門的第一步

一陣攻擊忽然襲來,妁艷還來不及反應,楓音就用了全身的力量展開了魔法防護盾

這波攻擊來的又快,威力又強,楓音一瞬間消耗了過多的魔力,不停的喘息...

「哼哼,滿有兩把刷子的嗎...」

抬頭一看,只看到了一個小蘿莉浮在半空中...身旁展著連妁艷都沒見過的魔法陣...

沒有什麼壓迫感,但妁艷跟楓音都知道這魔法陣...不是普通的強大,兩人合體是否有辦法勝利都不確定...

「那麼,我們開始吧!」

蘿莉很迅速的就開始了那不停歇的攻擊...一波接著一波

妁艷將他的武器拿了出來,幾乎費盡了全力將這些攻擊給擋了下來

然而妁艷用盡了全力,大魔王似乎只是在玩弄他們而已,毫無認真性可言

「看來...不動點真格你是不會屈服的囉~」魔王奸笑著,將所有的魔法陣集中在一起,發出了更為強悍的攻擊

妁艷很清楚的知道這個攻擊,他...絕對不能正面面對...能做的事情只有迴避...

可是這個攻擊卻是潑散性的,閃躲了主要的攻擊,還是會被攻擊力比較弱的潑散攻擊給攻擊到。

「妁艷~~」楓音了解了情況的嚴重性,將他身上的魔力給散了出來,落在了妁艷的身旁...

只要站在這些魔力區上,這些魔力就能把主要攻擊以及潑散攻擊給抵消掉,

但有個缺點就是,魔王的攻擊能藉由吸收這些魔力揮發掉的能量來增強!從而導致一發攻擊中可能會有好幾波的能量!

而且楓音實在太虛弱了,所以這些魔力並不均勻,每個魔力區都有個魔力值,代表他所能抵銷的攻擊量

我們可以將這些魔力區畫成一直線,而魔王攻擊發射的位置在位置 $0$ 上面(最左邊)。

理所當然的,距離攻擊初始位置越遠的地方,攻擊的威力會越弱,而攻擊吸收到的能量也會相對的減少。

現在給你直線上每個魔力區的魔力值,想請問你在每個魔力區(魔力值為 $A_i$)左邊有多少區魔力值 $A_j$ 太大會被吸收進而導致妁艷站在那邊會被傷害

以及在其右邊又有多少區會因魔力值太小而被魔王攻擊吸收的這格魔力值(即為 $A_i$)而使得妁艷也會被傷害

所以簡單的來說,當兩個位置 $A_i, A_j$ 的魔力值分別是 $B_i, B_j$ 時,當 $A_i > A_j$ 且 $B_i < B_j$ 時,就會導致這格變得有「殺傷力」

事情那麼容易嗎?大魔王的攻擊難道就這麼容易被解決嗎?並不是。

大魔王每次的攻擊都會針對某個魔力值,而魔力區的魔力值會一瞬間化為虛無,導致妁艷不能站在那邊,否則會被潑散攻擊給波及到

現在妁艷想知道的是,在每次大魔王的攻擊「之前」,他究竟有多少區域是不能站的呢?

Input Format

第一行會有兩個數字 $N, M$ 分別代表總共有 $N$ 個位置以及魔王會攻擊 $M$ 次。
$1 \le M \le N \le 10 ^ 5$,且魔力值 $A$ 中 $1 \sim N$ 恰各出現一次。
第二行則會有 $N$ 個數字分別代表每個位置的魔力值
第 $3 \sim 3+M$ 行每行則會有一個數字,代表魔王要攻擊哪個魔力值

Output Format

對每一個 $M$ 輸出當前總共的殺傷力

Sample Input 1

10 5
1 2 4 3 9 8 10 7 5 6
9
3
10
5
6

Sample Output 1

13
9
8
5
3

Hints

一開始殺傷力為 $13$,而 $M=9$,所以魔王這輪攻擊完妁艷能移動到的魔力區變成 1 2 4 3 8 10 7 5 6
此時的殺傷力為 $9$ ,而 $M=3$,所以魔王這輪攻擊完妁艷能移動到的魔力區變成 1 2 4 8 10 7 5 6
...
...
...
最後一波攻擊避開了之後,妁艷其實也不必再知道殺傷力有多少了...所以是輸出 $M$ 行噢!

Problem Source

原TIOJ1771 / problem setter:jeremy89183
2022.02.11 Update: Added $\LaTeX$ &輸入格式修正 by FHVirus

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 15000 65536 262144 1
1 15000 65536 262144 2
2 15000 65536 262144 3
3 15000 65536 262144 4
4 15000 65536 262144 5