[AH2017/HNOI2017] 影魔

这里给出一种线性做法。

考虑把点对分成第一个小和第二个小的情况，以下只考虑第一个小的情况，另一种情况是相似的。

考虑所有产生贡献的点对一定是某个点作为左端点与从他开始的前缀 max 点作为右端点，其中最近的一个贡献为 p1，其他为 p2。

因此可以使用单调栈求出以某个点为左端点的点对贡献和与以某个点作为右端点的点对贡献和，这样我们解决了全局的询问。

在区间询问中，我们考虑找到区间的最大值，这样区间中的所有点对一定不会跨过这个最大值。以最大值左侧的点作为左端点，其前缀 max 序列在区间中最后一个就是最大值，因此两者的全局贡献和相减即为它在区间中的贡献。若以最大值右侧的点作为右端点，直接考虑以它为右端点的所有点对即可。

综上，我们使用一个 O(n)-O(1) RMQ 求出最大值后，将单调栈求出的两种贡献值作区间和即可

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,p1,p2,a[210000];
int lowbit[410000],lg[21000];
void init_binary(){
    lg[0]=-1;
    for(int i=1;i<=400000;i++)lowbit[i]=(i&1)?0:lowbit[i>>1]+1;
    for(int i=1;i<=20000;i++)lg[i]=lg[i>>1]+1;
}
#define _s_maxx(l,r) (l+lowbit[h[r]>>l-bl[block[l]]])
int get(int x,int y){return a[x]>a[y]?x:y;}
struct RMQ{
    int bsz,block[210000],bl[210000],h[210000],st[21000][21],sta[21],top;
    void init(int* a,int len){
        bsz=__lg(len)+1;
        for(int i=1;i<=len;i++){
            block[i]=(i-1)/bsz+1;
            if(block[i-1]!=block[i]){
                st[block[i]-1][0]=sta[1];
                bl[block[i]]=i,h[i]=1,sta[top=1]=i;
            }else{
                while(top&&a[i]>a[sta[top]])top--;
                h[i]=h[sta[top]]|(1<<i-bl[block[i]]);
                sta[++top]=i;
            }
        }
        st[block[len]][0]=sta[1];
        for(int j=1;j<=20;j++){
            for(int i=block[len]+1-(1<<j);i>=1;i--)
                st[i][j]=get(st[i][j-1],st[i+(1<<j-1)][j-1]);
        }
    }
    int maxx(int* a,int l,int r){
        int lb=block[l],rb=block[r];
        if(lb==rb)return _s_maxx(l,r);
        if(rb-lb==1)return get(_s_maxx(l,bl[lb+1]-1),_s_maxx(bl[rb],r));
        int k=lg[rb-lb-1];
        return get(get(_s_maxx(l,bl[lb+1]-1),_s_maxx(bl[rb],r)),get(st[lb+1][k],st[rb-(1<<k)][k]));
    }
}T;
int sta[210000],top;
int vals1[210000],valp1[210000],nums1[210000],nump1[210000];
int vals2[210000],valp2[210000],nums2[210000],nump2[210000];
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&p1,&p2);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    init_binary();T.init(a,n);
    for(int i=n;i>=1;i--){
        while(top&&a[sta[top]]<a[i])nump2[i]+=nump2[sta[top]]+1,valp2[i]+=p1-p2,top--;
        sta[++top]=i,valp2[i]+=nump2[i]*p2;
        nums1[i]=top-1,vals1[i]=(top==1)?0:p1+(top-2)*p2;
    }
    top=0;
    for(int i=1;i<=n;i++){
        while(top&&a[sta[top]]<a[i])nump1[i]+=nump1[sta[top]]+1,valp1[i]+=p1-p2,top--;
        sta[++top]=i,valp1[i]+=nump1[i]*p2;
        nums2[i]=top-1,vals2[i]=(top==1)?0:p1+(top-2)*p2;
    }
    for(int i=1;i<=n;i++)valp1[i]+=valp1[i-1],valp2[i]+=valp2[i-1],vals2[i]+=vals2[i-1],vals1[i]+=vals1[i-1];
    for(int i=1,l,r;i<=m;i++){
        scanf("%lld%lld",&l,&r);int p=T.maxx(a,l,r);
        int ans=0;
        ans+=vals1[p-1]-vals1[l-1]-(p-l)*nums1[p]*p2+valp1[r]-valp1[p];
        ans+=vals2[r]-vals2[p]-(r-p)*nums2[p]*p2+valp2[p-1]-valp2[l-1];
        printf("%lld\n",ans);
    }
}