前言
洛谷上很多大佬都写的 CDQ分治 的解法。但看了某篇大佬的线段树解法，受益匪浅，于是决定写一篇题解来记录一下这种解法。
前置知识：单调栈，线段树
题目描述
给定一个正整数序列 \(a_1,a_2,\cdots,a_n\) ，求
\[\sum_{i=1}^{n}\sum_{j=i}^{n}(j-i+1)\min(a_i,a_{i+1},\cdots,a_j)\max(a_i,a_{i+1},\cdots,a_j) \]对于 \(100\%\) 的数据，\(1 \le n \leq 5\times 10^5\)，\(1 \le a_i \le 10^8\)。
思路
我们这里定义 \(min_{l,r}\) 和 \(max_{l,r}\) 分别为 \(a_l,a_{l+1},a_{l+2},\cdots,a_r\) 的 最小值 和 最大值。
题目让求的是
\[\sum_{l=1}^{n}\sum_{r=l}^{n}(r-l+1)\times min_{l,r}\times max_{l,r}\\ =\sum_{l=1}^{n}\sum_{r=l}^{n}(r+1)\times min_{i,j}\times max_{i,j} - l\times min_{i,j}\times max_{i,j} \]显然的，对于每个 \(r\) 做出的贡献为
\[(r+1)\times\sum_{l=1}^{r} min_{l,r}\times max_{l,r} \]对于每个 \(l\) 做出的贡献为
\[-l\times \sum_{r=l}^{n} min_{l,r}\times max_{l,r} \]这两个求法类似，这里就只讲 \(r\) 的解法。
假设现在已经有 \(r\) 这个右端点。
设 \(min(i)\) 和 \(max(i)\) 分别为 \(i\) 到 \(r\) 的区间最小值和区间最大值。
那么以 \(r\) 作为右端点做出的贡献就为
\[\sum_{i=1}^{r} min(i)\times max(i) \]考虑快速维护 \(min(i)\) 和 \(max(i)\) 。
考虑右端点从 \(r-1\) 变为 \(r\) 的过程。设 \(a_{j}(j<r)\) 为从 \(r\) 左边第一个 小于等于 \(a_i\) 的值，那么 \(a_i\) 只会对 \(min(j\cdots i)\) 造成影响，\(a_i\) 对 \(max()\) 的贡献同理。
显然的对于维护左边第一个 小于等于 和 大于等于 \(a_i\) 的值可以用 单调栈 做到总复杂度 \(O(n)\)。
再考虑用线段树维护以下信息
区间修改min(x)
区间修改max(x)
区间查询 \(\sum_{i=1}^r min(i)\times max(i)\)
这里的线段树维护信息和单调栈比较好写，就不细讲了
code
#include<bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int N=5e5+3,p=1e9;
struct Val{
int sa,sb,sm;
Val(){sa=sb=sm=0;}
};
Val operator+(Val x,Val y){
Val z;
z.sa=(x.sa+y.sa)%p;
z.sb=(x.sb+y.sb)%p;
z.sm=(x.sm+y.sm)%p;
return z;
}
struct node{
int tga=-1,tgb=-1;
Val v;
void val(int ta,int tb,int l,int r){
if(~ta){
tga=ta;
v.sa=(ta*1LL*(r-l+1))%p;
v.sm=(ta*1LL*v.sb)%p;
}
if(~tb){
tgb=tb;
v.sb=(tb*1LL*(r-l+1))%p;
v.sm=(tb*1LL*v.sa)%p;
}
}
}tr[(N<<2)];
void push_down(int x,int l,int r){
tr[x<<1].val(tr[x].tga,tr[x].tgb,l,mid);
tr[x<<1|1].val(tr[x].tga,tr[x].tgb,mid+1,r);
tr[x].tga=tr[x].tgb=-1;
}
void push_up(int x)
{tr[x].v=tr[x<<1].v+tr[x<<1|1].v;}
void change(int x,int l,int r,int ql,int qr,int ta,int tb){
if(l>=ql&&r<=qr){tr[x].val(ta,tb,l,r);return;}
if(l>qr||r<ql) return;
push_down(x,l,r);
change(x<<1,l,mid,ql,qr,ta,tb),
change(x<<1|1,mid+1,r,ql,qr,ta,tb);
push_up(x);
}
Val ask(int x,int l,int r,int ql,int qr){
if(l>=ql&&r<=qr) return tr[x].v;
if(l>qr||r<ql) return Val();
push_down(x,l,r);
return ask(x<<1,l,mid,l,r)+ask(x<<1|1,mid+1,r,l,r);
}
int a[N],n;
ll ans=0;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
stack<int>mn,mx;
for(int i=1;i<=n;i++){
while(mx.size()&&a[mx.top()]<a[i]) mx.pop();
if(mx.size()) change(1,1,n,mx.top()+1,i,a[i],-1);
else change(1,1,n,1,i,a[i],-1);
mx.push(i);
while(mn.size()&&a[mn.top()]>a[i]) mn.pop();
if(mn.size()) change(1,1,n,mn.top()+1,i,-1,a[i]);
else change(1,1,n,1,i,-1,a[i]);
mn.push(i);
auto v=ask(1,1,n,1,i);
ans=(ans+(v.sm*1LL*(i+1))%p)%p;
}
while(mn.size()) mn.pop();
while(mx.size()) mx.pop();
change(1,1,n,1,n,0,0);
for(int i=n;i>=1;i--){
while(mx.size()&&a[mx.top()]<a[i]) mx.pop();
if(mx.size()) change(1,1,n,i,mx.top()-1,a[i],-1);
else change(1,1,n,i,n,a[i],-1);
mx.push(i);
while(mn.size()&&a[mn.top()]>a[i]) mn.pop();
if(mn.size()) change(1,1,n,i,mn.top()-1,-1,a[i]);
else change(1,1,n,i,n,-1,a[i]);
mn.push(i);
auto v=ask(1,1,n,i,n);
ans=(ans-(v.sm*1LL*i)%p)%p;
}
cout<<(ans%p+p)%p;
return 0;
}