题目大意
解题思路
考虑分治，统计跨国分治中心的区间的答案，从左到右枚举右端点，维护第一个左端点到分治中心max比分治中心到右端点大的位置，同理维护min，同时维护对答案的贡献即可。
code
using namespace std;
int const mn=
5*1e5+
9,inf=
1e9+
7,mo=
1e9+
7;
int n,ans,a[mn],f[mn],g[mn];
int max(
int x,
int y){
return (
x>
y)?
x:
y;}
int min(
int x,
int y){
return (
x<
y)?
x:
y;}
void solve(
int l,
int r){
if(l>=r){
if(l==r)ans=(ans+
1ll
*a[l]
*a[l])
%mo;
return;
}
int md=(l+r)/
2;
solve(l,md);
solve(md+
1,r);
int mx=
0,mi=inf,j=md,k=md,sum=
0,su2=
0;
f[md+
1]=
0;g[md+
1]=inf;
fd(i,md,l)f[i]=max(f[i+
1],a[i]),g[i]=min(g[i+
1],a[i]),
sum=(sum+
1ll
*f[i]
*g[i])
%mo;
int tmp=ans;
fo(i,md+
1,r){
mx=max(mx,a[i]);
mi=min(mi,a[i]);
while((j>=l)&&(f[j]<mx)){
if(j<=k)sum=(sum-
1ll
*f[j]
*g[j])
%mo,su2=(su2+g[j])
%mo;
else su2=(su2-f[j])
%mo;
j--;
}
while((k>=l)&&(g[k]>mi)){
if(j<k)su2=(su2-g[k])
%mo;
else sum=(sum-
1ll
*f[k]
*g[k])
%mo,su2=(su2+f[k])
%mo;
k--;
}
ans=(ans+sum+
1ll
*su2*((j<k)?mx:mi)
%mo+
1ll
*mx*mi%mo*(md-max(j,k)))
%mo;
}
}
int main(){
freopen(
"seq.in",
"r",stdin);
freopen(
"seq.out",
"w",stdout);
scanf(
"%d",&n);
fo(i,
1,n)scanf(
"%d",&a[i]);
solve(
1,n);
printf(
"%d",(ans+mo)
%mo);
return 0;
}
