Description:


影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。

奈文摩尔有n个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 1 到 n。第i个灵魂的战斗力为k[i],灵魂们以点对的形式为影魔提供攻击力,对于灵魂对i,j( \(i\lt j\) )来说,若不存在k[s]( \(i\lt s\lt j\) )大于k[i]或者k[j],则会为影魔提供 p1的攻击力(可理解为:当j=i+1时,因为不存在满足 \(i\lt s\lt j\) 的s,从而k[s]不存在,这时提供p1的攻击力;当 \(j\gt i+1\) 时,若 \(max\) { \( k[s]|i\lt s\lt j\) } \( \le min\) { \( k[i],k[j]\) } , 则提供p1的攻击力); 另一种情况,令c为k[i+1],k[i+2],k[i+3]......k[j-1]的最大值,若c满足: \(k[i]\lt c\lt k[j]\) ,或者 \(k[j]\lt c\lt k[i]\) ,则会为影魔提供p2的攻击力,当这样的c不存在时,自然不会提供这p2的攻击力;其他情况的点对,均不会为影魔提供攻击力。

影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任意一段区间[a,b], \(1\le a\lt b\le n\) ,位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑 所有满足 \(a\le i\lt j\le b\) 的灵魂对i,j提供的攻击力之和。顺带一提,灵魂的战斗力组成一个1到n的排列:k[1],k[2],...,k[n]。

Input:


第一行n,m,p1,p2
第二行n个数:k[1],k[2],...,k[n]
接下来m行,每行两个数 a,b,表示询问区间[a,b]中的灵魂对会为影魔提供多少攻击力。
\(1\le n,m\le 200000\) ; \(1\le p1,p2 \le 1000\)

Output:


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

Sample Input:


Sample Output:


题解:


关于二维数点貌似查不到什么东西。
实际上就是维护一下什么二维平面上的矩形和,可以利用题目性质,并不一定要树套树什么的。
我们首先处理一下i位置前第一个大于k[i]的数的位置L[i],以及i位置后第一个大于k[i]的数的位置R[i]。
这个可以用单调栈来搞,然而我考场用的是二分加RMQ(强行上了 \(log_2^2 n\) )
我们对于每一个i分别考虑含有i的区间。

  1. 只有区间 \([L[i], R[i]]\) 贡献为p1
  2. 区间 \([j, R[i]], j\in (L[i], i)\) 贡献为p2
  3. 区间 \([L[i], j], j\in (i, R[i])\) 贡献为p2

然后这里没有考虑形如 \((i, i+1)\) 的区间,所以最后要加上。
我们把每一个区间 \([x, y]\) 抽象为平面上的一个点 \((x, y)\)
那么对于一个询问 \([a, b]\) ,就是要求平面上以点 \((a, b)\) 为左上角以 \((n, 1)\) 为右下角的矩形内的权值和。
由于这个矩形的右下角恒为 \((n, 1)\) ,所以我们可以用扫描线+线段树。

时间复杂度 \(O(n\log_2 n)\)