题意：
Description
影魔,奈文摩尔,据说有着一个诗人的灵魂。事实上,他吞噬的诗人灵魂早已成千上万。千百年来,他收集了各式各样的灵魂,包括诗人、牧师、帝王、乞丐、奴隶、罪人,当然,还有英雄。每一个灵魂,都有着自己的战斗力,而影魔,靠这些战斗力提升自己的攻击。奈文摩尔有 n 个灵魂,他们在影魔宽广的体内可以排成一排,从左至右标号 1 到 n。第 i个灵魂的战斗力为k[i],灵魂们以点对的形式为影魔提供攻击力,对于灵魂对 i,j(i<j)来说,若不存在 k[s](i<s<j)大于 k[i]或者 k[j],则会为影魔提供 p1 的攻击力(可理解为:当 j=i+1 时,因为不存在满足 i<s<j 的 s,从而 k[s]不存在,这时提供 p1 的攻击力;当 j>i+1 时,若max{k[s]|i<s<j}=min{k[i],k[j]} , 则 提 供 p1 的 攻 击 力 ); 另一种情况 , 令 c 为k[i+1],k[i+2],k[i+3]......k[j-1]的最大值,若 c 满足:k[i]<c<k[j],或者 k[j]<c<k[i],则会为影魔提供 p2 的攻击力,当这样的 c 不存在时,自然不会提供这 p2 的攻击力;其他情况的点对,均不会为影魔提供攻击力。影魔的挚友噬魂鬼在一天造访影魔体内时被这些灵魂吸引住了,他想知道,对于任意一段区间a,b],1<=a<b<=n,位于这些区间中的灵魂对会为影魔提供多少攻击力,即考虑 所有满足a<=i<j<=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 <= n,m <= 200000;1 <= p1,p2 <= 1000
Output
共输出 m 行,每行一个答案,依次对应 m 个询问。
题解：
场上推出来了但是不会写……悲伤辣么大QAQ
题目中攻击力的计算方式如下：
$max\{k[s]|i<s<j\}\leq min\{k[i],k[j]\}$则会产生$p1$的贡献；
$min\{k[i],k[j]\}<max\{k[s]|i<s<j\}<max\{k[i],k[j]\}$则会产生$p2$的贡献；
即区间端点若是整个区间的最大值和次大值则会产生$p1$的贡献，若只有其中一个是最大值则会产生$p2$的贡献，特别地，区间$[i,i+1]$也会产生$p1$的贡献；
反过来考虑$i$对哪些点对有贡献，明显当且仅当$k[i]$是整个区间$[l,r]$的最大值时才会对点对$(l-1,r+1)$产生贡献。
题目中给出了关键条件是$k$数组是1~n的一个排列，所以不会有重复的数；
那么可以用单调栈求出$i$左边第一个比它大的位置$L[i]$和右边第一个位置$R[i]$，显然$k[i]$就是区间$[L[i]+1,R[i]-1]$中的最大值；
此时点对$(L[i],R[i])$会产生$p1$的贡献，点对$(L[i],x)(i<x<R[i])$和$(x,R[i])(L[i]<x<i)$会产生$p2$的贡献；
把点对看成二维平面上的点，这就变成了二维平面上某一个矩形内求和的问题，可以离线排序后用扫描线+树状数组解决。
但是考场上我不会写这个东西。。。下午去学了一发才会。。。
听说主席树也能做，但是我不会差分。。。
代码：
（不要在意里面的奇怪东西和卡榜用优读）
//大不列颠帝国尊贵的骑士王，圣剑Excalibur的持有者——阿尔托利亚·潘德拉贡 Arturia Pendragon
//永远是我的老婆，不接受反驳 #include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define inf 2147483647
#define eps 1e-9
#define lb(x) (x&-x)
using namespace std;
typedef long long ll;
struct task{
int id,z,l,r,v;
friend bool operator <(task a,task b){
return a.z<b.z;
}
}q1[],q2[];
int n,m,p1,p2,l,r,nw1=,nw2=,top=,tot1=,tot2=,num[],st[],L[],R[];
ll ans[],t1[],t2[];
char buffer[],*hd,*tl;
inline char Getchar(){
if(hd==tl){
int len=fread(buffer,,,stdin);
hd=buffer,tl=hd+len;
if(hd==tl)
return EOF;
}
return *hd++;
}
inline int rd(){
register int x=;
char c;
do c=Getchar();
while(!isdigit(c));
do{
x=(x<<)+(x<<)+(c^);
c=Getchar();
}while(isdigit(c));
return x;
}
void add(ll u,ll x){
ll uu=u;
for(;u<=n;u+=lb(u)){
t1[u]+=x;
t2[u]+=x*uu;
}
}
ll query(ll u){
ll ret=,uu=u;
for(;u;u-=lb(u)){
ret+=(uu+)*t1[u]-t2[u];
}
return ret;
}
int main(){
//scanf("%d%d%d%d",&n,&m,&p1,&p2);
n=rd(),m=rd(),p1=rd(),p2=rd();
num[]=num[n+]=inf;
st[top=]=;
for(int i=;i<=n;i++){
//scanf("%d",&num[i]);
num[i]=rd();
while(num[i]>num[st[top]])R[st[top--]]=i;
L[i]=st[top];
st[++top]=i;
}
while(top)R[st[top--]]=n+;
for(int i=;i<=m;i++){
//scanf("%d%d",&l,&r);
l=rd(),r=rd();
q1[++tot1]=(task){i,l-,l,r,-};
q1[++tot1]=(task){i,r,l,r,};
ans[i]=(ll)p1*(r-l);
}
for(int i=;i<=n;i++){
if(L[i]&&R[i]!=n+)q2[++tot2]=(task){,R[i],L[i],L[i],p1};
if(L[i]&&R[i]>i+)q2[++tot2]=(task){,L[i],i+,R[i]-,p2};
if(L[i]<i-&&R[i]!=n+)q2[++tot2]=(task){,R[i],L[i]+,i-,p2};
}
sort(q1+,q1+tot1+);
sort(q2+,q2+tot2+);
while(!q1[nw1].z)nw1++;
for(int i=;i<=n;i++){
for(;nw2<=tot2&&q2[nw2].z==i;nw2++){
add(q2[nw2].r+,-q2[nw2].v);
add(q2[nw2].l,q2[nw2].v);
}
for(;nw1<=tot1&&q1[nw1].z==i;nw1++){
ans[q1[nw1].id]+=(ll)q1[nw1].v*(query(q1[nw1].r)-query(q1[nw1].l-));
}
if(nw1>tot1)break;
}
for(int i=;i<=m;i++){
printf("%lld\n",ans[i]);
}
return ;
}