# 星星灰暗着。

### [AH/HNOI2017]影魔

posted on 2018-04-12 11:00:11 | under 题解 |

UPD：原来的解释有点错误，修正一下。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define neko 200010
#define chkmax(a,b) ((a)>(b)?(a):(b))
#define f(i,a,b) for(register int i=(a);i<=(b);i=-(~i))
#define rf(i,a,b) for(register int i=(a);i>=(b);i=~(-i))
struct node
{
int l,r,id;
}q[neko];
int n,m;
typedef long long ll;
using namespace std;
namespace Seg
{
#define ori tagl,tagr
#define mid ((l+r)>>1)
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define pushup(root) Sum[root]=Sum[root<<1]+Sum[root<<1|1]
void pushdown(int root,int l,int r)
{
{
}
}
ll query(int root,int l,int r,int tagl,int tagr)
{
if(l>=tagl&&r<=tagr)return Sum[root];
pushdown(root,l,r);
ll tmp=0;
if(tagl<=mid)tmp+=query(lson,ori);
if(tagr>mid)tmp+=query(rson,ori);
return tmp;
}
void update(int root,int l,int r,int tagl,int tagr,int x)
{
pushdown(root,l,r);
if(tagl<=mid)update(lson,ori,x);
if(tagr>mid)update(rson,ori,x);
pushup(root);
}
#undef ori
#undef mid
#undef lson
#undef rson
}
namespace Cons
{
using namespace Seg;
bool cmp(node a,node b)
{return a.l<b.l;}
void init()
void calc()
{
int top=0,now=m;stk[0]=n+1;
init();
rf(i,n,1)
{
while(top&&a[stk[top]]<a[i])--top;
suc[i]=stk[top];
stk[++top]=i;
}
rf(i,n,1)
{
if(suc[i]>i)update(1,1,n+1,i+1,suc[i],p2),update(1,1,n+1,suc[i],suc[i],p1-2*p2);
while(q[now].l==i)ans[q[now].id]+=query(1,1,n+1,i+1,q[now].r),--now;
}
}
}
using namespace Cons;
int main()
{
scanf("%d%d%lld%lld",&n,&m,&p1,&p2);
f(i,1,n)scanf("%lld",&a[i]);//a[n+1]=1e9;
f(i,1,m)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
sort(q+1,q+m+1,cmp),calc();
reverse(a+1,a+n+1);
f(i,1,m)swap(q[i].l,q[i].r),q[i].l=n-q[i].l+1,q[i].r=n-q[i].r+1;
sort(q+1,q+m+1,cmp),calc();
f(i,1,m)printf("%lld\n",ans[i]);return 0;
}