单调栈＆线段树
离线处理询问，首先用单调栈预处理出左边第一个大于它的数head[i]及右边第一个大于它的数tail[i]，然后从左到右及从右到左各进行一遍下述操作：
从右到左枚举一个点i，作为区间的左端点，然后对于i+1到tail[i]在线段树中全部加上p2,若tail[i]不等于n+1就把tail[i]加上p1-2*p2 (因为[i,tail[i]]这个区间是要加上p1的，而正反各做一次却加上了两个p2) 。
若有一个以i为左端点的询问，则把这个询问的答案加上1~询问右端点的和。可以自己举几个例子，发现这样是可以处理到每一个区间对答案的贡献的。
复杂度O(nlogn)。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<vector> #include<algorithm> #include<queue> #include<bitset> #include<cmath> #define P puts("lala") #define pc cerr<<"lala"<<endl #define HH puts("") #define pb push_back #define pf push_front #define fi first #define se second #define mkp make_pair using namespace std; inline void read(int &re) { char ch=getchar();int g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+(ch^48),ch=getchar(); re*=g; } typedef long long ll; inline void read(ll &re) { char ch=getchar();ll g=1; while(ch<'0'||ch>'9') {if(ch=='-')g=-1;ch=getchar();} re=0; while(ch<='9'&&ch>='0') re=(re<<1)+(re<<3)+ch-48ll,ch=getchar(); re*=g; } const int N=200050; int n,m,p1,p2; int att[N]; int st[N],top=0; int add[N<<2],head[N],tail[N]; ll sum[N<<2]; inline void pushdown(int o,int l,int r) { if(add[o]) { add[o<<1]+=add[o];add[o<<1|1]+=add[o]; int mid=l+r>>1; sum[o<<1]+=(ll)(mid-l+1)*add[o];sum[o<<1|1]+=(ll)(r-mid)*add[o]; add[o]=0; } } void update(int o,int l,int r,int x,int y,int k) { if(x<=l&&r<=y) { add[o]+=k; sum[o]+=(ll)(r-l+1)*k; return ; } pushdown(o,l,r); int mid=l+r>>1; if(x<=mid) update(o<<1,l,mid,x,y,k); if(y>mid) update(o<<1|1,mid+1,r,x,y,k); sum[o]=sum[o<<1]+sum[o<<1|1]; } ll query(int o,int l,int r,int x,int y) { if(x<=l&&r<=y) return sum[o]; pushdown(o,l,r); int mid=l+r>>1; ll ans=0; if(x<=mid) ans+=query(o<<1,l,mid,x,y); if(y>mid) ans+=query(o<<1|1,mid+1,r,x,y); sum[o]=sum[o<<1]+sum[o<<1|1]; return ans; } struct node { int l,r; ll ans; }qr[N]; bool cmp1(node a,node b) { return a.l<b.l; } bool cmp2(node a,node b) { return a.r>b.r; } vector<int>ve1[N],ve2[N]; int main() { #ifndef ONLINE_JUDGE freopen("1.in","r",stdin);freopen("1.out","w",stdout); #endif int i,j,opt,T; read(n);read(m);read(p1);read(p2); for(i=1;i<=n;++i) read(att[i]); for(i=n;i;--i) { if(!top) st[++top]=i; else { while(top&&att[st[top]]<att[i]) top--; if(top) tail[i]=st[top]; st[++top]=i; } } memset(st,0,sizeof(st)); top=0; for(i=1;i<=n;++i) { if(!top) st[++top]=i; else { while(top&&att[st[top]]<att[i]) top--; if(top) head[i]=st[top]; st[++top]=i; } } for(i=1;i<=m;++i) { read(qr[i].l);read(qr[i].r); ve1[qr[i].l].pb(i);ve2[qr[i].r].pb(i); qr[i].ans=0; } for(i=1;i<=n;++i) { j=(head[i]?head[i]:1); if(j!=i) update(1,1,n,j,i-1,p2); if(head[i]) update(1,1,n,head[i],head[i],p1-2*p2); int siz=ve2[i].size(); for(int o=0;o<siz;++o) { int u=ve2[i][o]; qr[u].ans+=query(1,1,n,qr[u].l,n); } } memset(add,0,sizeof(add));memset(sum,0,sizeof(sum)); for(i=n;i;--i) { j=(tail[i]?tail[i]:n); if(j!=i) update(1,1,n,i+1,j,p2); if(tail[i]) update(1,1,n,tail[i],tail[i],p1-2*p2); int siz=ve1[i].size(); for(int o=0;o<siz;++o) { int u=ve1[i][o]; qr[u].ans+=query(1,1,n,1,qr[u].r); } } for(i=1;i<=m;++i) printf("%lld ",qr[i].ans); return 0; } /* */