#1172. 「AHOI / HNOI 2017」影魔

「AHOI / HNOI 2017」影魔

题目描述

影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。

每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。

奈文摩尔有 nn 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 11nn。第 ii 个灵魂的战斗力为 kik_i,灵魂们以点对的形式为影魔提供攻击力,对于灵魂对 i,j(i<j)i, j(i<j) 来说,若不存在 ks(i<s<j)k_s(i<s<j) 大于 kik_i 或者 kjk_j,则会为影魔提供 p1p_1 的攻击力(可理解为:当 j=i+1j = i + 1 时,因为不存在满足 i<s<ji < s < jss,从而 ksk_s 不存在,这时提供 p1p_1 的攻击力;当 j>i+1j > i + 1 时,若 max{ksi<s<j}min(ki,kj)\max\{k_s | i < s < j\}\le \min(k_i, k_j),则提供 p1p_1 的攻击力);另一种情况,令 ccki+1,ki+2,,kj1k_{i + 1}, k_{i + 2}, \cdots, k_{j -1} 的最大值,若 cc 满足:ki<c<kjk_i < c < k_j,或者 kj<c<kik_j < c < k_i,则会为影魔提供 p2p_2 的攻击力,当这样的 cc 不存在时,自然不会提供这 p2p_2 的攻击力;其他情况的点对,均不会为影魔提供攻击力。

影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任意一段区间 [a,b][a,b],位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑所有满足 ai<jba\le i<j\le b 的灵魂对 i,ji, j 提供的攻击力之和。

顺带一提,灵魂的战斗力组成一个 11nn 的排列:k1,k1,,knk_1, k_1, \cdots, k_n

输入格式

第一行四个整数 n,m,p1,p2n,m,p_1,p_2
第二行 nn 个整数数:k1,k2,,knk_1, k_2,\cdots, k_n
接下来 mm 行,每行两个数 a,ba,b,表示询问区间 [a,b][a,b] 中的灵魂对会为影魔提供多少攻击力。

输出格式

共输出 mm 行,每行一个答案,依次对应 mm 个询问。

样例

10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
30
39
4
13
16

数据范围与提示

对于 30%30\% 的数据,1n,m5001\le n, m\le 500
另有 30%30\% 的数据,p1=2p2p_1 = 2p_2
对于 100%100\% 的数据,1n,m200000,1p1,p210001\le n,m\le 200000, 1\le p_1, p_2\le 1000