看一眼题面,离线操作八九不离十。

为了不盲目地去思考,考虑包含位置$i$(非端点)的必定有效区间。

若$a_i$为最大点且不为端点,无效。

若端点$a_{l_i},a_{r_i}\ge\forall j\in(l_i,r_i)$,为$p_1$类有效区间。

这个条件可以转化为$i$往左(右)走,找到第一个比$a_i$大的数的位置即为$l_i(r_i)$。

$p_2$类的贡献区间其实就是$[l_i,i+1\sim r_i-1],[l_i+1\sim i-1,r_i]$

经过一番不严谨的思考,这样的操作是不重不漏的。

离线操作时,按照产生贡献的位置与询问位置进行排序,可以达到差分的效果求解。

题目中还有一种贡献形式不解释了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int mod=1e9+7,N=2e5+10;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct SGT{int l,r;ll s,ad;}t[N<<2];
void update(int p){t[p].s=t[p<<1].s+t[p<<1|1].s;}
void pushdown(int p)
{
    if(t[p].ad)
    {
        ll ad=t[p].ad;
        t[p<<1].s+=(t[p<<1].r-t[p<<1].l+1)*ad;t[p<<1].ad+=ad;
        t[p<<1|1].s+=(t[p<<1|1].r-t[p<<1|1].l+1)*ad;t[p<<1|1].ad+=ad;
        t[p].ad=0;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l;t[p].r=r;
    if(l==r){t[p].s=0;return ;}
    int mid=l+r>>1;
    build(p<<1,l,mid);build(p<<1|1,mid+1,r);
    update(p);
}
void change(int p,int L,int R,ll ad)
{
    if(L<=t[p].l&&R>=t[p].r){t[p].ad+=ad;t[p].s+=(t[p].r-t[p].l+1)*ad;return ;}
    pushdown(p);int mid=t[p].l+t[p].r>>1;
    if(L<=mid)change(p<<1,L,R,ad);
    if(R>mid)change(p<<1|1,L,R,ad);
    update(p);
}
ll query(int p,int L,int R)
{
    if(L<=t[p].l&&R>=t[p].r)return t[p].s;
    pushdown(p);int mid=t[p].l+t[p].r>>1;ll val=0;
    if(L<=mid)val+=query(p<<1,L,R);
    if(R>mid)val+=query(p<<1|1,L,R);
    return val;
}
struct Query
{
    int op,pos,l,r,d,id;
    Query(int op=0,int pos=0,int l=0,int r=0,int d=0,int id=0):op(op),pos(pos),l(l),r(r),d(d),id(id){}
    bool operator <(const Query a)const{return pos==a.pos?op<a.op:pos<a.pos;}
}Q[N<<3];
int L[N],R[N],sta[N],a[N],top,cnt;
ll ans[N];
int main()
{
    int n,m,p1,p2;qr(n),qr(m),qr(p1),qr(p2);
    for(int i=1;i<=n;i++)qr(a[i]);
    for(int i=1;i<=n;i++)
    {
        for(;top&&a[sta[top]]<a[i];--top)
            R[sta[top]]=i;
        L[i]=sta[top];sta[++top]=i;
    }
    while(top)R[sta[top]]=n+1,--top;
    for(int i=1;i<=n;i++)
    {
        if(i+1<=n)Q[++cnt]=Query(0,i+1,i,i,p1,1);
        if(1<=L[i]&&R[i]<=n)Q[++cnt]=Query(0,R[i],L[i],L[i],p1,0);
        if(1<=L[i]&&R[i]>i+1)Q[++cnt]=Query(0,L[i],i+1,R[i]-1,p2,0);
        if(R[i]<=n&&L[i]<i-1)Q[++cnt]=Query(0,R[i],L[i]+1,i-1,p2,0);
    }
    for(int i=1,x,y;i<=m;i++)
    {
        qr(x),qr(y);
        if(x>1)Q[++cnt]=Query(1,x-1,x,y,-1,i);
        Q[++cnt]=Query(1,y,x,y,1,i);
    }
    sort(Q+1,Q+cnt+1);
    build(1,1,n);
    for(int i=1;i<=cnt;i++)
        if(Q[i].op)ans[Q[i].id]+=query(1,Q[i].l,Q[i].r)*Q[i].d;
        else change(1,Q[i].l,Q[i].r,Q[i].d);
    for(int i=1;i<=m;i++)qw(ans[i]),puts("");
    return 0;
}