题解（有分析）

题解:

这个题可以采取离线处理的方式.先处理出每个点i左边第一个比它大的点$L[i]$,和右边第一个比它大的点$R[i]$.

那么对于区间$L[i]$到$R[i]$有$p1$的贡献.$①$

对于左端点在$L[i]+1$到$i-1$,右端点为$R[i]$的区间有$p2$的贡献.$②$

对于左端点为$L[i]$,右端点为$i+1$到$R[i]-1$的区间也有$p2$的贡献.$③$

所以我们离线排序处理好.

对于$①$情况,我们在扫到$R[i]$时,更新点$L[i]$的贡献

对于$②$情况,我们在扫到$R[i]$时,更新区间$L[i]+1$到$i-1$的贡献

对于$③$情况,我们在扫到$L[i]$时,更新区间$i+1$到$R[i]-14$的贡献

我们对于每个询问$[l,r]$,在扫到l$-1$时,我们记录此时区间$l$到$r$的每个点的贡献和为$sum1$,然后当我们扫到$r$的时候,再次记录此时的区间$l$到$r$的每个点的贡献和为$sum2$,显然答案就是$sum2-sum1$了.

鹅鹅鹅，建议看到最后

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#define RG register
#define LL long long int
#define MAXN 500010
using namespace std;
const int INF=1e9;
struct node{
  int l,r,x,id,v;
  node(){}
  node(int l_,int r_,int x_,int id_,int v_):l(l_),r(r_),x(x_),id(id_),v(v_){}
  bool operator <(const node &tmp)const{
    return x<tmp.x;
  }
}s1[MAXN],s2[MAXN];
int n,m,p1,p2;
int k[MAXN],q[MAXN],top;
int L[MAXN],R[MAXN];
LL ans[MAXN],c1[MAXN],c2[MAXN];
int lowbit(int x)
{
  return x&(-x);
}
void add(int x,int y)//区间修改操作
{
  if(x) for(int i=x;i<=n;i+=lowbit(i)) c1[i]+=y,c2[i]+=(LL)x*y;
}
LL sum(int x)
{
  LL num=0;
  for(int i=x;i>0;i-=lowbit(i)) num+=(x+1)*c1[i]-c2[i];
  return num;
}
int main()
{
  freopen("1.in","r",stdin);
  scanf("%d%d%d%d",&n,&m,&p1,&p2);
  k[0]=k[n+1]=n+1;q[++top]=0;
  for(int i=1;i<=n;i++) scanf("%d",&k[i]);
  for(int i=1;i<=n+1;i++)
    {
      while(k[q[top]]<k[i]) R[q[top]]=i,top--;
      L[i]=q[top];q[++top]=i;
    }
  int x,y;
  for(int i=1;i<=m;i++)
    {
      scanf("%d%d",&x,&y);ans[i]+=(y-x)*p1;
      s1[i]=node(x,y,x-1,i,-1);s1[i+m]=node(x,y,y,i,1);
    }
  sort(s1+1,s1+2*m+1);int tot=0;
  for(int i=1;i<=n;i++)
    {
      if(1<=L[i]&&R[i]<=n) s2[++tot]=node(L[i],L[i],R[i],0,p1);
      if(1<=L[i]&&R[i]>i+1) s2[++tot]=node(i+1,R[i]-1,L[i],0,p2);
      if(L[i]+1<i&&R[i]<=n) s2[++tot]=node(L[i]+1,i-1,R[i],0,p2);
    }
  sort(s2+1,s2+tot+1);int n1=1,n2=1;
  while(!s1[n1].x) n1++;
  for(int i=1;n1<=m*2&&i<=n;i++)
    {
      while(n2<=tot&&s2[n2].x==i){
    add(s2[n2].r+1,-s2[n2].v);
    add(s2[n2].l,s2[n2].v);
    n2++;
      }
      while(n1<=m*2&&s1[n1].x==i){
    ans[s1[n1].id]+=s1[n1].v*(sum(s1[n1].r)-sum(s1[n1].l-1));
    n1++;
      } 
    }
  for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
  return 0;
}

别走！！！这里才是正确代码：：

#include<bits/stdc++.h>
#define ri register int
#define p(i) ++i
#define LL long long
using namespace std;
const int N=2e5+7;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
struct node{
	int l,r,w;
	node(){}
	node(int l,int r,int w):l(l),r(r),w(w){}
};
struct E{
	int first[N],t;
	void init() {t=1;}
	struct edge{
		int nxt;
		node v;
	}e[N<<2];
	inline void add(int u,node v) {
		e[t].v=v;
		e[t].nxt=first[u];
		first[u]=t++;
	} 
}E;
struct Seg{
	int root[N],tot;
	struct Segmenttree{
		int l,r;
		LL sum,tag;
	}T[N*32];
	inline void update(int &x,int l,int r,int lt,int rt,int w) {
		if (!x) x=p(tot);
		T[x].sum+=1ll*(min(r,rt)-max(l,lt)+1)*w;
		if (l<=lt&&rt<=r) {T[x].tag+=1ll*w;return;}
		int mid=(lt+rt)>>1;
		if (l<=mid) update(T[x].l,l,r,lt,mid,w);
		if (r>mid) update(T[x].r,l,r,mid+1,rt,w);
	}
	inline int merge(int x,int y) {
		if (!x||!y) return x+y;
		T[x].sum+=T[y].sum;T[x].tag+=T[y].tag;
		T[x].l=merge(T[x].l,T[y].l);
		T[x].r=merge(T[x].r,T[y].r);
		return x;
	}
	inline LL query(int x,int l,int r,int lt,int rt) {
		if (!x) return 0;
		if (l<=lt&&rt<=r) return T[x].sum;
		int mid=(lt+rt)>>1;LL res=0;
		if (l<=mid) res+=query(T[x].l,l,r,lt,mid);
		if (r>mid) res+=query(T[x].r,l,r,mid+1,rt);
		return res+1ll*(min(r,rt)-max(l,lt)+1)*T[x].tag;
	}
}T;
int n,st[N],p,pp,at[N],ll[N],rr[N],m;
int main() {
	n=read(),m=read(),p=read(),pp=read();
	const int p1=p,p2=pp;
	int tp=0;
	for (ri i(1);i<=n;p(i)) {
		at[i]=read();
		while(tp&&at[st[tp]]<at[i]) rr[st[tp--]]=i;
		ll[i]=st[tp];
		st[p(tp)]=i;
	}
	while(tp) rr[st[tp--]]=n+1;
	E.init();
	for (ri i(1);i<=n;p(i)) {
		if (i!=n) E.add(i,node(i+1,i+1,p1));
		if (ll[i]&&rr[i]<=n) E.add(ll[i],node(rr[i],rr[i],p1));
		if (ll[i]&&i+1<=rr[i]-1) E.add(ll[i],node(i+1,rr[i]-1,p2));
		if (rr[i]<=n&&ll[i]+1<=i-1) E.add(rr[i],node(ll[i]+1,i-1,p2));
	}
	for (ri i(1);i<=n;p(i)) {
		for (ri j(E.first[i]);j;j=E.e[j].nxt) {
			node v=E.e[j].v;
			int l=v.l,r=v.r,w=v.w;
			T.update(T.root[i],l,r,1,n,w);
		}
		T.root[i]=T.merge(T.root[i],T.root[i-1]);
	}
	for (ri i(1);i<=m;p(i)) {
		int l=read(),r=read();
		printf("%lld\n",T.query(T.root[r],l,r,1,n)-T.query(T.root[l-1],l,r,1,n));
	}
	return 0;
}