【jzoj5231】【NOIP2017模拟A组模拟8.5】【序列问题】 【分治】

时间:2021-12-17 10:06:30

题目大意

【jzoj5231】【NOIP2017模拟A组模拟8.5】【序列问题】 【分治】

解题思路

考虑分治,统计跨国分治中心的区间的答案,从左到右枚举右端点,维护第一个左端点到分治中心max比分治中心到右端点大的位置,同理维护min,同时维护对答案的贡献即可。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
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;
}