Description：

给一个 $n$ 的排列，如果不存在 $x\in(i,j),\min(a_i,a_j)<a_x$ ，那么这对点 $a_i,a_j$ 贡献 $p1$ 的价值，如果存在 $x\in(i,j)$ $,\min(a_i,a_j)<a_x<\max(a_i,a_j)$ ，那么这对点贡献 $p2$ 的价值，多次询问区间内所有点贡献的价值之和。

$1\leqslant n\leqslant 200000$

Solution：

首先解释一下这两种贡献就是对于一个区间，如果两端点分别是最大值和次大值。那么有 $p1$ 贡献，如果有一个是最大值另一个不是次大值，那么会有 $p2$ 贡献。

感觉想到这这题就解决了一半了，考虑枚举某个位置，那么考虑第一种贡献的情况，那他作为区间第三大值就会产生一个区间的贡献，这个区间就是他左右第一个比它大的位置，这个可以用单调栈求出，设其为 $lef[i],rig[i]$ 。

再考虑第二种贡献，那么对于所有左端点在 $lef[i]+1\sim i-1$ ，右端点在 $rig[i]$ 的所有区间都是符合条件的，对于所有左端点在 $lef[i]$ ，右端点在 $i+1\sim rig[i]-1$ 的所有区间也都是符合条件的，那么可以区间 $[l,r]$ 抽象成二维空间中的一个点 $(l,r)$ ，然后就可以把这三个区间的集合抽象成三个矩形，第一个矩形只有一个点 $lef[i],rig[i]$ ，那么询问就是询问矩形 $x\in[l,r],y\in[l,r]$ 中点的权值之和，然而并不会，但是发现所有的矩形不是长是一就是宽是一，而且询问的是一个关于直线 $y=x$ 对称的正方形，那么可以把长为一的矩形反转一下，也就是说只有很多竖着的宽为一的矩形，那么就可以用扫描线 $+$ 线段树统计了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,p1,p2;

#define MAXN 200010

int v[MAXN];

int lef[MAXN],rig[MAXN];

int st[MAXN],top = 0;

#define INF 0x3f3f3f3f

typedef long long ll;

ll ans[MAXN];

struct scan

{

	int type,pos,top,bot,val;

}s[MAXN * 3 * 2 + MAXN * 2];

bool cmp_x(scan a,scan b)

{

	if(a.pos == b.pos)return (abs(a.type) <= abs(b.type));

	else return a.pos < b.pos;

}

int tot = 0;

bool check(int x){return (1 <= x && x <= n);}

void addscan(int x1,int x2,int y1,int y2,int type,int val)

{

	if(!check(x1) || !check(x2) || !check(y1) || !check(y2))return;

	if(x1 > x2 || y1 > y2)return;

	if(type == 0)

	{

		s[++tot] = (scan){-1,x1 - 1,y2,y1,val};

		s[++tot] = (scan){1,x2,y2,y1,val};

	}

	else

	{

		s[++tot] = (scan){0,x1,y2,y1,val};

	}

	return;

}

struct node

{

	int lc,rc;

	ll sum,tag,siz;

	node(){sum = tag = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	t[rt].siz = r - l + 1;

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void pushdown(int rt)

{

	t[t[rt].lc].sum += t[rt].tag * t[t[rt].lc].siz;

	t[t[rt].lc].tag += t[rt].tag;

	t[t[rt].rc].sum += t[rt].tag * t[t[rt].rc].siz;

	t[t[rt].rc].tag += t[rt].tag;

	t[rt].tag = 0;

	return;

}

void add(int rt,int L,int R,ll k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].sum += k * t[rt].siz;

		t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	return;

}

ll query(int rt,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rt].sum;

	ll res = 0;

	pushdown(rt);

	if(L <= mid)res += query(t[rt].lc,L,R,l,mid);

	if(R > mid)res += query(t[rt].rc,L,R,mid + 1,r);

	return res;

}

int main()

{

	scanf("%d%d%d%d",&n,&m,&p1,&p2);

	for(int i = 1;i <= n;++i)v[i] = rd();

	v[0] = v[n + 1] = INF;

	st[++top] = 0;

	for(int i = 1;i <= n;++i)

	{

		while(top >= 1 && v[st[top]] < v[i])--top;

		lef[i] = st[top];

		st[++top] = i;

	}

	top = 0;

	st[++top] = n + 1;

	for(int i = n;i >= 1;--i)

	{

		while(top >= 1 && v[st[top]] < v[i])--top;

		rig[i] = st[top];

		st[++top] = i;

	}

	for(int i = 1;i <= n;++i)

	{

		addscan(rig[i],rig[i],lef[i],lef[i],1,p1);

		addscan(rig[i],rig[i],lef[i] + 1,i - 1,1,p2);

		addscan(lef[i],lef[i],i + 1,rig[i] - 1,1,p2);

	}

	for(int i = 1;i < n;++i)addscan(i,i,i + 1,i + 1,1,p1); 

	int l,r;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&l,&r);

		addscan(l,r,l,r,0,i);

	}

	sort(s + 1,s + 1 + tot,cmp_x);

	build(root,1,n);

	for(int i = 1;i <= tot;++i)

	{

		if(s[i].type == 0)

		{

			add(root,s[i].bot,s[i].top,s[i].val,1,n);

		}

		else

		{

			ans[s[i].val] += s[i].type * query(root,s[i].bot,s[i].top,1,n);

		} 

	}

	for(int i = 1;i <= m;++i)printf("%lld\n",ans[i]);

	return 0;

}