题面

100

在\(O(n^2)\)的基础上，我们可以用线段树来加速。

枚举了左端点之后，需要知道以这个左端点为起点的前缀max，前缀min。

这里只讨论前缀max，前缀min同理。

当我们倒序枚举左端点的时候，这个前缀max就可以用线段树来维护：

左端点向左移一位到i——

首先我们要预处理出a[i]向右第一个比他小的，以及第一个比他大的。

然后就相当于是区间赋值，并在线段树中维护好每一位的min和max积之和。

时间复杂度为\(O(nlogn)\)。

code

#include
    
     #define ll long long#define fo(i,x,y) for(int i=x;i<=y;i++)#define fd(i,x,y) for(int i=x;i>=y;i--)using namespace std;const char* fin="seq.in";const char* fout="seq.out";const int inf=0x7fffffff;int read(){    int x=0;    char ch=getchar();    while (ch<'0' || ch>'9') ch=getchar();    while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();    return x;}const int maxn=500007,mo=1000000007;int n,a[maxn],ans,mx[maxn],mn[maxn],st[maxn];struct node{int x,a,b,ma,mb;node(){ma=mb=-1;}}c[maxn*4];void mkd(int l,int r,int t){    if (c[t].ma!=-1){        c[t].x=1ll*c[t].b*c[t].ma%mo;        c[t].a=1ll*c[t].ma*(r-l+1)%mo;        if (l
     
      v2 || r
      
       =v1 && r<=v2){        c[t].ma=v;        mkd(l,r,t);        return;    }    modifya(l,mid,t*2,v1,v2,v);    modifya(mid+1,r,t*2+1,v1,v2,v);    c[t].x=(c[t*2].x+c[t*2+1].x)%mo;    c[t].a=(c[t*2].a+c[t*2+1].a)%mo;    c[t].b=(c[t*2].b+c[t*2+1].b)%mo;}void modifyb(int l,int r,int t,int v1,int v2,int v){    int mid=(l+r)/2;    mkd(l,r,t);    if (l>v2 || r
       
        =v1 && r<=v2){        c[t].mb=v;        mkd(l,r,t);        return;    }    modifyb(l,mid,t*2,v1,v2,v);    modifyb(mid+1,r,t*2+1,v1,v2,v);    c[t].x=(c[t*2].x+c[t*2+1].x)%mo;    c[t].a=(c[t*2].a+c[t*2+1].a)%mo;    c[t].b=(c[t*2].b+c[t*2+1].b)%mo;}int main(){    freopen(fin,"r",stdin);    freopen(fout,"w",stdout);    n=read();    fo(i,1,n) a[i]=read();    st[0]=0;    fd(i,n,1){        while (st[0] && a[st[st[0]]]>=a[i]) st[0]--;        if (!st[0]) mx[i]=n+1;        else mx[i]=st[st[0]];        st[++st[0]]=i;    }    st[0]=0;    fd(i,n,1){        while (st[0] && a[st[st[0]]]<=a[i]) st[0]--;        if (!st[0]) mn[i]=n+1;        else mn[i]=st[st[0]];        st[++st[0]]=i;    }    fd(i,n,1){        modifya(1,n,1,i,mx[i]-1,a[i]);        modifyb(1,n,1,i,mn[i]-1,a[i]);        ans=(ans+c[1].x)%mo;    }    printf("%d",ans);    return 0;}