提供一份主席树套主席树的 MLE 代码。

Solution

想法很简单。
可知左边的最大值和右边的最大值 $lm_x, rm_x$，然后统计以下等式：

$$\sum_{rm_x\leq R, x\in [L, R]} p2(x-1-max(lm_x, L-1))$$

另一半同理。
再统计一下 $lm_x\geq L, rm_x\leq R$ 的对数乘以 $p1$ 即可。

于是由于那个式子中的 $min,max$ 去打了主席树套主席树。
其实一开始本来想玄学过去的，但是打到最后一点玄学的余地都没有了。

所以只得上离线做法。

后来知道好像是可以二维数点在线做来着。

Code

// Code by ajcxsu
// Problem: shadow

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
using namespace std;
typedef long long ll;

template<typename T> inline void gn (T &x) {
    char ch=getchar(); x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }

const int N=2e5+10;
int k[N], stk[N], pos[N], lm[N], rm[N], t, n, m, p1, p2;
struct Query { int x, id; } ;
ll ans[N];
#define ls x<<1
#define rs x<<1|1
ll su[N<<2];
int cn[N<<2];
void updata(int x, int l, int r, int d, ll v) {
    if(l==r) { su[x]+=v; return; }
    int mid=(l+r)>>1;
    if(d<=mid) updata(ls, l, mid, d, v); else updata(rs, mid+1, r, d, v);
    su[x]=su[ls]+su[rs];
}
ll query(int x, int l, int r, int xr) {
    if(r<=xr) return su[x];
    int mid=(l+r)>>1; ll ret=query(ls, l, mid, xr);
    if(xr>mid) ret+=query(rs, mid+1, r, xr);
    return ret;
}
void updata2(int x, int l, int r, int d, int v) {
    if(l==r) { cn[x]+=v; return; }
    int mid=(l+r)>>1;
    if(d<=mid) updata2(ls, l, mid, d, v); else updata2(rs, mid+1, r, d, v);
    cn[x]=cn[ls]+cn[rs];
}
int query2(int x, int l, int r, int xr) {
    if(r<=xr) return cn[x];
    int mid=(l+r)>>1; int ret=query2(ls, l, mid, xr);
    if(xr>mid) ret+=query2(rs, mid+1, r, xr);
    return ret;
}

int h[N], ty[N<<1], nexp[N<<1], id[N<<1], p=1;
void ini() { CLR(h, 0), p=1; }
void ins(int a, int b, int t) { nexp[p]=h[a], h[a]=p, id[p]=b, ty[p]=t, p++; }
vector<Query> q1[N], q2[N];

void work(bool cac=0) {
    ini();
    for(int i=1;i<=n;i++) {
        assert(lm[i]<i);
        ins(lm[i]+1, i, 1), ins(i, i, 2), updata(1, 0, n+1, rm[i], 1ll*(i-1-lm[i])*p2);
        if(cac) updata(1, 0, n+1, rm[i], p1);
    }
    for(int i=0;i<=n+2;i++) {
        if(cac) {
            for(int u=h[i];u;u=nexp[u])
                if(ty[u]==1) updata(1, 0, n+1, rm[id[u]], -p1);
        }
        for(Query &x:q1[i])
            ans[x.id]+=query(1, 0, n+1, x.x)-1ll*query2(1, 0, n+1, x.x)*(i-1)*p2;
        for(int u=h[i];u;u=nexp[u])
            if(ty[u]==1) updata(1, 0, n+1, rm[id[u]], 1ll*p2*lm[id[u]]), updata2(1, 0, n+1, rm[id[u]], 1);
            else if(ty[u]==2) updata(1, 0, n+1, rm[id[u]], 1ll*p2*(-id[u]+1)), updata2(1, 0, n+1, rm[id[u]], -1);
    }
}

int main() {
    gn(n, m, p1, p2);
    for(int i=1;i<=n;i++) gn(k[i]);
    for(int i=1;i<=n;i++) {
        while(t && stk[t]<k[i]) t--;
        lm[i]=pos[t];
        stk[++t]=k[i], pos[t]=i;
    }
    pos[0]=n+1, t=0;
    for(int i=n;i>=1;i--) {
        while(t && stk[t]<k[i]) t--;
        rm[i]=pos[t];
        stk[++t]=k[i], pos[t]=i;
    }
    int nl, nr;
    for(int i=0;i<m;i++) gn(nl, nr), q1[nl].push_back({nr, i}), q2[n-nr+1].push_back({n-nl+1, i}), ans[i]+=1ll*p1*(nr-nl);
    work(1);
    for(int i=1;i<=n;i++) q1[i].swap(q2[i]), lm[i]=n-lm[i]+1, rm[i]=n-rm[i]+1, swap(lm[i], rm[i]);
    reverse(lm+1, lm+1+n), reverse(rm+1, rm+1+n);
    work();
    for(int i=0;i<m;i++) cout<<ans[i]<<'\n';
    return 0;
}

Code 2 MLE

// luogu-judger-enable-o2
// Code by ajcxsu
// Problem: shadow

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T> inline void gn (T &x) {
    char ch=getchar(); x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=x*10+ch-'0', ch=getchar();
}
template<typename T, typename ...Args> inline void gn(T &x, Args &...args) { gn(x), gn(args...); }

const int N=2e5+10;
struct Nodeb *nilb;
struct Nodeb {
    Nodeb *ls=nilb, *rs=nilb;
    int nu=0; ll va=0;
} ;
struct Node *nil;
struct Node {
    Node *ls, *rs;
    Nodeb *rt; ll va;
} *r1[N], *r2[N];
void ini() {
    nilb=new Nodeb; nilb->ls=nilb->rs=nilb, nilb->nu=nilb->va=0;
    nil=new Node; nil->ls=nil->rs=nil, nil->rt=nilb, nil->va=0;
    r1[0]=r2[0]=nil;
}

int k[N], stk[N], pos[N], lm[N], rm[N], t, n, m, p1, p2;

void updatab(Nodeb *&b, int l, int r, int val) {
    Nodeb* na=new Nodeb; *na=*b, b=na; b->nu++, b->va+=val;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(val<=mid) updatab(b->ls, l, mid, val);
    else updatab(b->rs, mid+1, r, val);
}
void updata(Node *&x, int l, int r, int d, int g, int v) {
    Node *nd=new Node; *nd=*x, x=nd; updatab(x->rt, 0, n+1, g), x->va+=v;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(d<=mid) updata(x->ls, l, mid, d, g, v);
    else updata(x->rs, mid+1, r, d, g, v);
}

int L, R;
struct Data { int nu; ll va; } ;
Data operator + (const Data &a, const Data &b) { return {a.nu+b.nu, a.va+b.va}; } 
Data operator - (const Data &a, const Data &b) { return {a.nu-b.nu, a.va-b.va}; } 
Data queryB(Nodeb *lx, Nodeb *rx, int l, int r, int xr) {
    if(r<=xr) return (Data){rx->nu-lx->nu, rx->va-lx->va};
    int mid=(l+r)>>1;
    Data ret=queryB(lx->ls, rx->ls, l, mid, xr);
    if(xr>mid) ret=ret+queryB(lx->rs, rx->rs, mid+1, r, xr);
    return ret;
}
ll query1(Node *lx, Node *rx, int l, int r) {
    if(r<=R) {
        Data na=queryB(lx->rt, rx->rt, 0, n+1, L-1), nb=(Data){rx->rt->nu-lx->rt->nu, rx->rt->va-lx->rt->va}-na;
        return ((rx->va-lx->va)-(1ll*(L-1)*na.nu+nb.va))*p2;
    }
    int mid=(l+r)>>1;
    ll ret=query1(lx->ls, rx->ls, l, mid);
    if(R>mid) ret+=query1(lx->rs, rx->rs, mid+1, r);
    return ret;
}
ll query2(Node *lx, Node *rx, int l, int r) {
    if(l>=L) {
        Data na=queryB(lx->rt, rx->rt, 0, n+1, R), nb=(Data){rx->rt->nu-lx->rt->nu, rx->rt->va-lx->rt->va}-na;
        return (1ll*(R+1)*nb.nu+na.va-(rx->va-lx->va))*p2+na.nu*p1;
    }
    int mid=(l+r)>>1;
    ll ret=query2(lx->rs, rx->rs, mid+1, r);
    if(L<=mid) ret+=query2(lx->ls, rx->ls, l, mid);
    return ret;
}

int main() {
    ini();
    gn(n, m, p1, p2);
    for(int i=1;i<=n;i++) gn(k[i]);
    for(int i=1;i<=n;i++) {
        while(t && stk[t]<k[i]) t--;
        lm[i]=pos[t];
        stk[++t]=k[i], pos[t]=i;
    }
    pos[0]=n+1, t=0;
    for(int i=n;i>=1;i--) {
        while(t && stk[t]<k[i]) t--;
        rm[i]=pos[t];
        stk[++t]=k[i], pos[t]=i;
    }
    for(int i=1;i<=n;i++) {
        r1[i]=r1[i-1], r2[i]=r2[i-1];
        updata(r1[i], 0, n+1, rm[i], lm[i], i-1);
        updata(r2[i], 0, n+1, lm[i], rm[i], i+1);
    }
    while(m--) {
        gn(L, R);
        printf("%lld\n", query1(r1[L-1], r1[R], 0, n+1)+query2(r2[L-1], r2[R], 0, n+1)+1ll*(R-L)*p1);
    }
    return 0;
}