0x1f 关于思路
妙妙妙！
可以发现，暴力的枚举点对可以在 \(O(n^2)\) 的复杂度下解决问题。
似乎不能优化了。
对于这样的困境，一种思路是计算每个点的贡献，枚举的复杂度就降下来了。
考虑对题意进行转化：求出每个点左边第一个比他大的数 \(L_i\)，右边同理 \(R_i\)。
这样答案的贡献可以转换成三部分。
- \(R_i\) 对 \([L_i,i-1]\) 的区间产生 \(p_2\) 的贡献。
- \(L_i\) 对 \([i+1,R_i]\) 的区间产生 \(p_2\) 的贡献。
- \(L_i\) 和 \(R_i\) 产生 \(p_1\) 的贡献。
我们可以离线地按询问左端点排序询问，每到一个点，如果是右端点，那就线段树区间查询。
每到一个点 \(R_i\)，区间加上贡献 \(1\)，\(L_i\) 加上贡献 \(2\)。
至于贡献 \(3\)，我们慎重考虑，因为线段树区间查询，所以如果区间内一个点的 \(R_i\) 在区间外右侧，那就不应该统计。
所以贡献 \(3\) 应该在右端点时再加上。
0x2f 关于代码
\(\huge \mathscr{Code}\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+100;
int n,m,p1,p2,val[N],L[N],R[N],ans[N];
struct node{int l,r,pos,id,ki;friend bool operator<(node a,node b) {return a.pos<b.pos;}
}Q[N<<1];
class G{public:struct GG{int ans,tag;}T[N<<2];inline void pushup(int u){T[u].ans = T[u*2].ans + T[u*2+1].ans;}inline void pushdown(int u,int l,int r){if(T[u].tag){int mid = (l+r)>>1;T[u*2].ans += (mid-l+1)*T[u].tag;T[u*2+1].ans += (r-mid)*T[u].tag;T[u*2].tag += T[u].tag;T[u*2+1].tag += T[u].tag;T[u].tag = 0; }}void update(int u,int l,int r,int ql,int qr,int v){if(ql<=l && r<=qr){T[u].ans += (r-l+1)*v;T[u].tag += v;return;}pushdown(u,l,r);int mid = (l+r)>>1;if(ql<=mid) update(u*2,l,mid,ql,qr,v);if(qr>mid) update(u*2+1,mid+1,r,ql,qr,v);pushup(u);}int query(int u,int l,int r,int ql,int qr){if(ql<=l && r<=qr) return T[u].ans;pushdown(u,l,r);int mid = (l+r)>>1,ans = 0;if(ql<=mid) ans += query(u*2,l,mid,ql,qr);if(qr>mid) ans += query(u*2+1,mid+1,r,ql,qr);return ans;}
}S;
int stk[N],top;
struct num{int l,r,ki;
};
vector<num> event[N];
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>p1>>p2;for(int i=1;i<=n;i++) cin>>val[i];val[n+1] = n+1;stk[++top] = 0;for(int i=1;i<=n+1;i++){while(top && val[stk[top]]<val[i]) R[stk[top--]] = i;L[i] = stk[top];stk[++top] = i;}for(int i=1;i<=n;i++){if(L[i]>=1 && R[i]<=n) event[R[i]].push_back(num{L[i],L[i],p1});if(L[i]+1<i && R[i]<=n) event[R[i]].push_back(num{L[i]+1,i-1,p2});if(L[i]>=1 && R[i]>i+1) event[L[i]].push_back(num{i+1,R[i]-1,p2});}for(int i=1;i<=m;i++){int l,r;cin>>l>>r;ans[i] += (r-l)*p1;Q[i] = node{l,r,l-1,i,-1},Q[i+m] = node{l,r,r,i,1};}sort(Q+1,Q+2*m+1);int pos = 1;while(pos<=m*2 && !Q[pos].pos) pos++;for(int i=1;i<=n;i++){for(num e:event[i]){S.update(1,1,n,e.l,e.r,e.ki);}while(pos<=m*2 && Q[pos].pos==i){ans[Q[pos].id] += Q[pos].ki*S.query(1,1,n,Q[pos].l,Q[pos].r);pos++;}}for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';return 0;
}