Luogu

BZOJ

分析

对所有询问离线处理。

首先用单调栈处理出每个点左右最近的比它大的数，分别记为 $L_i$ 和 $R_i$。

显然 $[L_i,R_i]$ 有 $p_1$ 的贡献；左端点在 $[L_i+1,i-1]$ 之间，右端点在 $R_i$ 的区间有 $p_2$ 的贡献；左端点在 $L_i$ ，右端点在 $[i+1,R_i-1]$ 之间的的区间有 $p_2$ 的贡献。

于是离线扫描：对于第一种情况，在 $R_i$ 处更新 $L_i$的贡献；对于第二种情况，在 $R_i$ 处更新 $[L_i+1,i-1]$ 的贡献；对于第三种情况，在 $L_i$ 处更新 $[i+1,R_i-1]$ 的贡献。

这个类似于扫描线。

每个询问 $[l,r]$ 的答案可以拆成 $[1,r]$ 减去 $[1,l-1]$ 。

具体实现及细节见代码。注意要开$\texttt{long long}$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

struct Query { int x,l,r,id,v; };
struct Line { int x,l,r,v; };
bool operator <(Query a,Query b) { return a.x<b.x; }
bool operator <(Line a,Line b) { return a.x<b.x; }

int n,m,p1,p2;
int a[N],L[N],R[N];
int sta[N],top=0;
Query q[N<<1];
Line s[N*3];
ll c1[N],c2[N],ans[N];

inline int lowbit(int x) { return x&-x; }
inline void add(int x,int y) {
    if (!x) return;
    for (re int i=x;i<=n;i+=lowbit(i)) c1[i]+=y,c2[i]+=1ll*x*y;
}
inline ll sum(int x) {
    ll ans=0;
    for (re int i=x;i;i-=lowbit(i)) ans+=(x+1)*c1[i]-c2[i];
    return ans;
}

int main() {
    n=read(),m=read(),p1=read(),p2=read();
    for (re int i=1;i<=n;++i) a[i]=read();

    for (re int i=1;i<=n;++i) {
        while (top&&a[sta[top]]<a[i]) --top;
        L[i]=sta[top],sta[++top]=i;
    }
    sta[top=0]=n+1;
    for (re int i=n;i>=1;--i) {
        while (top&&a[sta[top]]<a[i]) --top;
        R[i]=sta[top],sta[++top]=i;
    }
    
    for (re int i=1;i<=m;++i) {
        int x=read(),y=read(); ans[i]+=(y-x)*p1;
        q[i]=(Query){x-1,x,y,i,-1};
        q[i+m]=(Query){y,x,y,i,1};
    }
    sort(q+1,q+m+m+1);
    
    int tot=0;
    for (re int i=1;i<=n;++i) {
        if (1<=L[i]&&R[i]<=n) s[++tot]=(Line){R[i],L[i],L[i],p1};
        if (1<=L[i]&&R[i]>i+1) s[++tot]=(Line){L[i],i+1,R[i]-1,p2};
        if (L[i]<i-1&&R[i]<=n) s[++tot]=(Line){R[i],L[i]+1,i-1,p2};
    }
    sort(s+1,s+tot+1);

    int pos1=1,pos2=1; while (!q[pos1].x) ++pos1;
    for (re int i=1;pos1<=m+m&&i<=n;++i) {
        while (pos2<=tot&&s[pos2].x<=i) {
            add(s[pos2].r+1,-s[pos2].v);
            add(s[pos2].l,s[pos2].v);
            ++pos2;
        }
        while (pos1<=m+m&&q[pos1].x<=i) {
            ans[q[pos1].id]+=q[pos1].v*(sum(q[pos1].r)-sum(q[pos1].l-1));
            ++pos1;
        }
    }
    for (re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
    return 0;
}