然而好像没有平衡树

还是题解包：

T1：森林

树上主席树+启发式合并。

然而好像知道标签就没啥了。在启发式合并时可以顺手求lca

然而这题好像可以时间换空间（回收空间）

T2：影魔

难点在于考虑贡献的来源

考虑一个区间两端点和区间最值（不含端点）的关系

小，中，大：贡献p1

大，小，大：贡献p2

大，中，小：贡献p1

则预处理出每个点左右第一个比它大的数的位置，设为l和r

则l会对r有p2的贡献，l会对i+1～r-1产生p1的贡献，同理r会对l+1~i-1产生p1的贡献。

用线段树维护扫描线，正向，逆向分别扫一遍，先把贡献都加进线段树，扫到某个点时先统计贡献再在线段树中减掉贡献。

具体实现见代码

#include<bits/stdc++.h>
#define LL long long
#define N 200050
using namespace std;
struct node{int l,r,id;LL ans;}q[N];
const int inf=1000000007;
int n,m,p1,p2;
int a[N];
int l[N],r[N],dq[N],ba;
vector<pair<int,int> >v[N];
#define pb push_back
#define mmp make_pair
#define F first 
#define S second
inline bool cmp1(const node &a,const node &b){return a.l<b.l;}
inline bool cmp2(const node &a,const node &b){return a.r>b.r;}
inline bool cmp(const node &a,const node &b){return a.id<b.id;}
struct Segment_tree{
    LL sum[N<<2],tag[N<<2];
    inline void clear(){
        memset(sum,0,sizeof(sum));
        memset(tag,0,sizeof(tag));
    }
    inline void upd(int g){sum[g]=sum[g<<1]+sum[g<<1|1];}
    inline void down(int g,int l,int m,int r)
    {
        tag[g<<1]+=tag[g];
        tag[g<<1|1]+=tag[g];
        sum[g<<1]+=tag[g]*(m-l+1);
        sum[g<<1|1]+=tag[g]*(r-m);
        tag[g]=0;return;
    }
    inline void add(int g,int l,int r,int x,int y,int v){
        if(l>y||r<x)return;
        if(l>=x&&r<=y){sum[g]+=v*(r-l+1);tag[g]+=v;return;}
        const int m=l+r>>1;
        if(tag[g])down(g,l,m,r);
        add(g<<1,l,m,x,y,v);
        add(g<<1|1,m+1,r,x,y,v);
        upd(g);
    }
    inline LL ask(int g,int l,int r,int x,int y)
    {
        if(l>y||r<x)return 0;
        if(l>=x&&r<=y)return sum[g];
        const int m=l+r>>1;
        if(tag[g])down(g,l,m,r);
        return ask(g<<1,l,m,x,y)+ask(g<<1|1,m+1,r,x,y);
    }
}T;
int main()
{
//    freopen("da.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&p1,&p2);
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=1;i<=m;++i)
        scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    a[0]=inf;a[n+1]=inf-1;
    
    for(int i=1;i<=n+1;++i){
        while(a[i]>a[dq[ba]]){
            r[dq[ba]]=i;
            v[l[dq[ba]]].pb(mmp(dq[ba]+1,i-1));
            --ba;
        }
        l[i]=dq[ba];dq[++ba]=i;
    }
//    for(int i=1;i<=n;++i)
//        printf("l[%d]=%d r[%d]=%d\n",i,l[i],i,r[i]);
    
    
    
    
    sort(q+1,q+m+1,cmp1);
    for(int i=1;i<=n;++i){
        if(r[i]!=i+1)T.add(1,1,n,r[i],r[i],p1);
        for(int j=v[i].size()-1;~j;--j)
            T.add(1,1,n,v[i][j].F,v[i][j].S,p2);
    }
    for(int i=1,k=1;i<=n;++i){
        while(q[k].l==i&&k<=m){
            q[k].ans+=T.ask(1,1,n,i,q[k].r);
            ++k;
        }
        if(r[i]!=i+1)T.add(1,1,n,r[i],r[i],-p1);
        for(int j=v[i].size()-1;~j;--j)
            T.add(1,1,n,v[i][j].F,v[i][j].S,-p2);
        v[i].clear();
    }
    
    for(int i=1;i<=n;++i)
        if(r[i])v[r[i]].push_back(mmp(l[i]+1,i-1));
    sort(q+1,q+m+1,cmp2);
    for(int i=n;i;--i){
        if(l[i]!=i-1)T.add(1,1,n,l[i],l[i],p1);
        for(int j=v[i].size()-1;~j;--j)
            T.add(1,1,n,v[i][j].F,v[i][j].S,p2);
    }
    for(int i=n,k=1;i;--i){
        while(q[k].r==i&&k<=m){
            q[k].ans+=T.ask(1,1,n,q[k].l,i);
            ++k;
        }
        if(l[i]!=i-1)T.add(1,1,n,l[i],l[i],-p1);
        for(int j=v[i].size()-1;~j;--j)
            T.add(1,1,n,v[i][j].F,v[i][j].S,-p2);
    }
//    printf("%d %d %lld\n",q[2].l,q[2].r,q[2].ans);
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;++i)
        printf("%lld\n",q[i].ans+1ll*(q[i].r-q[i].l)*p1);
    return 0;
}