题目链接：https://ac.nowcoder.com/acm/problem/208150
题目大意：
求出所有区间的最大值*最小值的和
题目思路：
有一个比较经典的思路
有一个相似的思路：(待补)
枚举所有的结束节点 1~n
用线段树维护 从i到当前枚举的结束节点的 最大值*最小值
假设当前枚举位置是 pos:
那么节点1 维护的 即为 1~pos的区间最大值*最小值 节点2维护2~pos的最大值*最小值
也就是说 整个过程 我们每次会多一个起点，之前的区间会向右扩充一个数
可以发现这个节点维护是单调的
即 最大值 i~pos 一定是递减的
即 最小值 i~pos 一定是递增的
假设维护最大值，新来的的数向左找到比他大的第一个数，就是它可以维护的区间，因为之前的一定包括比他大的数
所以此过程用单调栈实现即可
至于接下来的操作，用一个线段树维护区间修改 —— 区间赋值
注意维护 乘积时：当前节点下，最大值改为a ,那么和就会改为a*当前节点下最小值的和
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef unsigned long long ll;
const ll INF=1e17;
const int maxn =1e7+700;
const int mod= 1e9+7;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
ll num[maxn];
ll suma[maxn],sumb[maxn],sum[maxn];
ll lazya[maxn],lazyb[maxn];
int prea[maxn],preb[maxn];
int st[maxn],s = 0;
void work(){
st[s=0] = 0;
for(int i=1;i<=n;i++){
while(s&&num[i]>=num[st[s]]) s--;
prea[i] = st[s]+1;
st[++s] = i;
}
st[s=0] = 0;
for(int i=1;i<=n;i++){
while(s&&num[i]<=num[st[s]]) s--;
preb[i] = st[s]+1;
st[++s] = i;
}
}
void push(int k){
sum[k] = sum[k<<1] + sum[k<<1|1];
suma[k] = suma[k<<1] + suma[k<<1|1];
sumb[k] = sumb[k<<1] + sumb[k<<1|1];
}
void down(int k,int l,int r){
int mid = (l+r)/2;
if(~lazya[k]){
suma[k<<1] = lazya[k] * (mid-l+1)*1ll;
suma[k<<1|1] = lazya[k] * (r-mid)*1ll;
lazya[k<<1] = lazya[k];
lazya[k<<1|1] = lazya[k];
sum[k<<1] = lazya[k]*sumb[k<<1];
sum[k<<1|1] = lazya[k]*sumb[k<<1|1];
lazya[k] = -1;
}
if(~lazyb[k]){
sumb[k<<1] = lazyb[k] * (mid-l+1)*1ll;
sumb[k<<1|1] = lazyb[k] * (r-mid)*1ll;
lazyb[k<<1] = lazyb[k];
lazyb[k<<1|1] = lazyb[k];
sum[k<<1] = suma[k<<1]*lazyb[k];
sum[k<<1|1] = suma[k<<1|1]*lazyb[k];
lazyb[k] = -1;
}
}
void modify(int k,int x,int y,int l,int r,int f,ll w){///f = 0 a ,f = 1,b
if(x<=l&&y>=r){
/// printf("%d %d %d\n",k,l,r);
if(!f) suma[k] = (r-l+1)*w,lazya[k] = w,sum[k] = w*sumb[k];
else sumb[k] = (r-l+1)*w,lazyb[k] = w,sum[k] = w*suma[k];
return;
}
down(k,l,r);
int mid = (l+r)/2;
if(x<=mid) modify(k<<1,x,y,l,mid,f,w);
if(y>mid) modify(k<<1|1,x,y,mid+1,r,f,w);
push(k);
}
int main(){
read(n);
memset(lazya,-1,sizeof(lazya));
memset(lazyb,-1,sizeof(lazyb));
for(int i=1;i<=n;i++) read(num[i]);
work();
ll ans = 0;
for(int i=1;i<=n;i++){
int f = 0;
modify(1,prea[i],i,1,n,0,num[i]);
modify(1,preb[i],i,1,n,1,num[i]);
ans += sum[1];
}
printf("%llu\n",ans);
return 0;
}
/***
3 3 = 9
3 2 = 6
3 1 = 3
***/
