UOJ Logo Universal Online Judge

UOJ

#749. 【UNR #6】稳健型选手

附件下载 统计

下山市是一个卧虎藏龙的地方。这天 hehe 蚤在公园散步的时候,就遇到了一位真正的卡牌大师 —— QAQ 蚤。

卡牌一共 $n$ 张,垒成了一摞,从上到下用 $1$ 到 $n$ 编号。此外,第 $i$ 张牌上还写着一个整数 $a_i$。

QAQ 蚤和 hehe 蚤一共会进行 $q$ 局卡牌游戏。其中,第 $i$ 局卡牌游戏流程如下:

  1. QAQ 蚤抽出编号在 $l_i$ 到 $r_i$ 的卡牌,以同样的顺序垒成一摞。

  2. QAQ 蚤和 hehe 蚤轮流行动,每次取走剩余卡牌中的任意一张,直到牌全部被取完。其中 QAQ 蚤为先手。

  3. 两人的得分分别是各自得到的卡牌上的整数之和。

  4. 最后,QAQ 蚤把牌按原来的顺序放回牌堆。

hehe 蚤是一位稳健型选手。由于牌都是背面朝上,hehe 蚤无法知道卡牌上的整数,也不会尝试记忆那些曾经抽到过的卡。

因此 hehe 蚤取卡牌时,总会使用一个非常稳健的策略——取走剩余卡牌中编号最小的一张

但 QAQ 蚤早就记下了所有卡牌上的整数。并且他绝顶聪明,早就看出了 hehe 蚤是一位稳健型选手,每次只会拿走编号最小的卡。

在知晓上述信息的情况下,QAQ 蚤会设计策略,最大化自己的得分。

当然,作为一位真正的卡牌大师,QAQ 蚤提前算出了自己每局的得分。然而他发现你在一旁看热闹,于是要求你也算出这些得分,来验证自己算出的结果。

输入格式

第一行两个数 $n,q$,表示牌堆大小和游戏次数。

第二行 $n$ 个数 $a_i$,表示每张卡牌上的整数。

然后 $q$ 行,每行两个数,$l_i,r_i$,表示第 $i$ 局游戏抽出牌的编号区间。

输出格式

输出 $q$ 行,每行一个整数,表示第 $i$ 局 QAQ 蚤的得分。

样例一

input

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

output

5
9
11

explanation

考虑第三局游戏。

第一轮 QAQ 蚤取 $a_2 = 4$,hehe 蚤取 $a_1 = 3$,

第二轮 QAQ 蚤取 $a_4 = 2$,hehe 蚤取 $a_3 = 1$,

第三轮 QAQ 蚤取 $a_5 = 5$。

QAQ 蚤取的总和为 $4+2+5=11$,可以证明不存在更优方案。

样例二

见附加文件中 ex_game2.inex_game2.ans,该组样例满足子任务 1,2,4,5 的性质。

样例三

见附加文件中 ex_game3.inex_game3.ans,该组样例满足子任务 3 的性质。

样例四

见附加文件中 ex_game4.inex_game4.ans,该组样例满足子任务 5 的性质。

限制与约定

对于 $100\%$ 数据,$1\le n,q\le 2\times10^5,1\le a_i\le 10^9,1\le l_i\le r_i\le n$。

子任务编号 数据范围 分值
$1$ $n\le 20,q\le 20$ $10$
$2$ $n\le 500,q\le 500$ $10$
$3$ $n\le 2\times10^5,q=1,l_1=1,r_1=n$ $20$
$4$ $n,q\le 5\times10^4$ $30$
$5$ $n,q\le 2\times 10^5$ $30$

时间限制:$3\texttt{s}$

空间限制:$512\texttt{MB}$