想到了离线的$n^2$做法，然后就不会了。
这里记录两个做法（%%%GPskyh和%%%素质先锋Lrefrain的）
抓住最值，一个点能作为最值的区间的范围可以找出来。
最主要的就是统计答案
1.先说skyh的 考虑到第一种情况非常好统计，我们试图在其中找出第二种情况的答案
我们先维护一个单调递减栈，发现这个点对数是$O(n)$级别的，即只有一个点出栈和入栈的时候才会形成点对。
利用这个性质先把所有点对找出来，然后就可以直接扫了。
延续这个思路，我们发现，能形成情况二的点的是栈中的相邻元素，也就是说，新加进去的点对应着一段区间。
然后就是维护一棵线段树 从前往后扫，扫到一个点就把这个点对应的区间造成的贡献加进去，然后统计以这个点为右端点的区间答案。
线段树维护的是左端点的贡献，也就是我们在保证右端点合法的基础上利用线段树就可以进行降维打击。
我没有实现，只是口胡。
2.再说Lrefrain 假如我们有一个点对应的左右比它大的第一个数$l_i$,$r_i$，那么答案来自
1.[$l_i$,$r_i$]->p1
2.[$l_i$,$i+1$~$r_i-1$]->p2
3.[$l_i+1$~$i-1$,$r_i$]->p2
那我们怎么统计呢？
网上的做法是把区间化为点对，然后把情况2，3化为线段，每次询问视作一个矩阵。
但是现在我们可以有一个更简单的方法，维护一棵线段树，这颗线段树的含义是某一个端点在i的贡献，注意没有限定左还是右。
那我们一个询问的答案是某一端点在l~r的另一端点也在l~r的贡献。
这时候只需要在l-1处减去前面所有对l~r的贡献在r处加上就行了。美妙的差分！
1 #include<cstdio> 2 #include<vector> 3 #include<iostream> 4 #define int long long 5 using namespace std; 6 const int N=2e5+7; 7 struct node{ 8 int l,r,x; 9 node(int l=0,int r=0,int x=0) {this->l=l,this->r=r,this->x=x;return ;} 10 }; 11 int n,m,p1,p2,a[N],l[N],r[N],sta[N],top,gl[N],gr[N],ans[N]; 12 vector<node> cs[N],csl[N],csr[N]; 13 inline int read() 14 { 15 int x=0;char c=getchar(); 16 for(;c>‘9‘||c<‘0‘;c=getchar()); 17 for(;c>=‘0‘&&c<=‘9‘;c=getchar()) x=x*10+c-48; 18 return x; 19 } 20 struct SegmentTree{ 21 #define ls k<<1 22 #define rs ls|1 23 int s[N<<2],f[N<<2]; 24 inline void down(int k,int l,int r) 25 { 26 if(!f[k]) return ; 27 int mid=l+r>>1; 28 f[ls]+=f[k],f[rs]+=f[k]; 29 s[ls]+=f[k]*(mid-l+1),s[rs]+=f[k]*(r-mid); 30 f[k]=0; 31 } 32 inline void up(int k) {s[k]=s[ls]+s[rs];return ;} 33 void insert(int k,int l,int r,int gl,int gr,int val) 34 { 35 if(l>=gl&&r<=gr) return s[k]+=val*(r-l+1),f[k]+=val,void(); 36 down(k,l,r); 37 int mid=l+r>>1; 38 if(gl<=mid) insert(ls,l,mid,gl,gr,val); 39 if(gr>mid) insert(rs,mid+1,r,gl,gr,val); 40 return up(k); 41 } 42 int query(int k,int l,int r,int gl,int gr) 43 { 44 if(l>=gl&&r<=gr) return s[k]; 45 down(k,l,r); 46 int mid=l+r>>1,ans=0; 47 if(gl<=mid) ans=query(ls,l,mid,gl,gr); 48 if(gr>mid) ans=ans+query(rs,mid+1,r,gl,gr); 49 return ans; 50 } 51 }T; 52 main() 53 { 54 n=read(),m=read(),p1=read(),p2=read(); 55 for(int i=1;i<=n;++i) a[i]=read(); 56 for(int i=1;i<=n;++i) 57 { 58 while(top&&a[sta[top]]<a[i]) r[sta[top--]]=i; 59 sta[++top]=i; 60 } 61 while(top) r[sta[top--]]=n+1; 62 for(int i=n;i;--i) 63 { 64 while(top&&a[sta[top]]<a[i]) l[sta[top--]]=i; 65 sta[++top]=i; 66 } 67 while(top) l[sta[top--]]=0; 68 for(int i=1;i<=n;++i) 69 { 70 cs[l[i]].push_back(node(r[i],r[i],p1)); 71 cs[l[i]].push_back(node(i+1,r[i]-1,p2)); 72 cs[r[i]].push_back(node(l[i]+1,i-1,p2)); 73 } 74 for(int i=1,nl,nr;i<=m;++i) nl=read(),nr=read(),csl[nl-1].push_back(node(nl,nr,i)),csr[nr].push_back(node(nl,nr,i)),ans[i]=(nr-nl)*p1; 75 for(int i=1;i<=n;++i) 76 { 77 for(int j=0;j<cs[i].size();++j) if(cs[i][j].l<=cs[i][j].r) T.insert(1,1,n,cs[i][j].l,cs[i][j].r,cs[i][j].x); 78 for(int j=0;j<csl[i].size();++j) ans[csl[i][j].x]-=T.query(1,1,n,csl[i][j].l,csl[i][j].r); 79 for(int j=0;j<csr[i].size();++j) ans[csr[i][j].x]+=T.query(1,1,n,csr[i][j].l,csr[i][j].r); 80 } 81 for(int i=1;i<=m;++i) printf("%lld\n",ans[i]); 82 return 0; 83 }
原文：https://www.cnblogs.com/hzoi-kx/p/12046099.html
