完全想不到地，考虑分治。
对区间[l,r]，将左端点x由mid不断左移，右边记录最右的p满足max[mid+1,p]<=max[x,mid]，q满足min[mid+1,q]>=min[x,mid]。这样右边被分成三部分，分别统计。
对于p和q左边的位置，这部分的max和min显然是由左边部分决定的，答案非常好算。
对于p和q右边的位置，这部分的max和min显然是由右边部分决定的，可以在分治的一开始预处理一个右区间的前缀len*max*min和max*min，这样就很好算了。
对于p和q中间的位置，若p在q左边，则这一部分最小值是由左边决定的，而最大值是由右边决定的，预处理右区间前缀len*max和max；反之同理。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } #define N 500010 #define P 1000000000 int n,a[N],lenmaxmin[N],maxmin[N],lenmax[N],lenmin[N],MAX[N],MIN[N],ans; void inc(int &x,int y){x+=y;if (x>=P) x-=P;} void solve(int l,int r) { if (l==r) {inc(ans,1ll*a[l]*a[l]%P);return;} int mid=l+r>>1; solve(l,mid),solve(mid+1,r); int mx=0,mn=P,p=mid,q=mid; lenmaxmin[mid]=maxmin[mid]=lenmax[mid]=lenmin[mid]=MAX[mid]=MIN[mid]=0; for (int i=mid+1;i<=r;i++) { mx=max(mx,a[i]),mn=min(mn,a[i]); lenmaxmin[i]=(lenmaxmin[i-1]+1ll*(i-mid)*mx%P*mn%P)%P; maxmin[i]=(maxmin[i-1]+1ll*mx*mn%P)%P; lenmax[i]=(lenmax[i-1]+1ll*(i-mid)*mx%P)%P; lenmin[i]=(lenmin[i-1]+1ll*(i-mid)*mn%P)%P; MAX[i]=(MAX[i-1]+mx)%P; MIN[i]=(MIN[i-1]+mn)%P; } mx=0,mn=P; for (int i=mid;i>=l;i--) { mx=max(mx,a[i]),mn=min(mn,a[i]); while (p<r&&a[p+1]<=mx) p++; while (q<r&&a[q+1]>=mn) q++; inc(ans,((1ll*((mid-i+2+min(p,q)-i+1)%P)*(min(p,q)-mid)>>1)+P)%P*mx%P*mn%P); inc(ans,(1ll*(maxmin[r]-maxmin[max(p,q)]+P)*(mid-i+1)+lenmaxmin[r]-lenmaxmin[max(p,q)]+P)%P); if (p<q) inc(ans,(1ll*(MAX[q]-MAX[p]+P)*(mid-i+1)+lenmax[q]-lenmax[p]+P)%P*mn%P); else inc(ans,(1ll*(MIN[p]-MIN[q]+P)*(mid-i+1)+lenmin[p]-lenmin[q]+P)%P*mx%P); } } int main() { #ifndef ONLINE_JUDGE freopen("bzoj3745.in","r",stdin); freopen("bzoj3745.out","w",stdout); #endif n=read(); for (int i=1;i<=n;i++) a[i]=read(); solve(1,n); cout<<ans; return 0; }