@[kingho11](https://www.luogu.com.cn/user/562569)
AC代码
```
#include<bits/stdc++.h>
using namespace std;
#define ri register int
typedef long long ll;
const int maxn=1e5+10,mod=1e9+7;
struct node
{
ll val;
int id;
inline bool operator<(const node &k)const
{
return val<k.val;
}
} tl[maxn];
int a[maxn],n;
ll ans,fl[maxn],fr[maxn],gl[maxn],gr[maxn],sml[maxn],sgl[maxn];
void solve(int l,int r)
{
if(l==r)
{
ans=(ans+a[l])%mod;
return;
}
int mid=l+r>>1;
solve(l,mid);
solve(mid+1,r);
for(ri i=mid; i>=l; --i)
{
if(i==mid)fl[i]=a[i],fl[i+1]=gl[i]=0;
else fl[i]=max(fl[i+1],fl[i+2]+a[i]);
if(i==mid-1)gl[i]=a[i],gl[i+1]=0;
else if(i!=mid)gl[i]=max(gl[i+1],gl[i+2]+a[i]);
tl[i]= {max(fl[i]-gl[i],0ll),i};
}
sort(tl+l,tl+mid+1);
sml[l-1]=sgl[l-1]=0;
for(ri i=l; i<=mid; ++i)
{
sml[i]=sml[i-1]+max(fl[tl[i].id],gl[tl[i].id]);
sgl[i]=sgl[i-1]+gl[tl[i].id];
}
for(ri i=mid+1; i<=r; ++i)
{
if(i==mid+1)fr[i]=a[i],fr[i-1]=gr[i]=0;
else fr[i]=max(fr[i-1],fr[i-2]+a[i]);
if(i==mid+2)gr[i]=a[i];
else if(i!=mid+1)gr[i]=max(gr[i-1],gr[i-2]+a[i]);
ri k=lower_bound(tl+l,tl+mid+1,node {fr[i]-gr[i],0})-tl;
ans=(ans+(sml[mid]-sml[k-1])%mod+(mid-k+1)*(gr[i]%mod)%mod)%mod;
ans=(ans+(sgl[k-1]%mod)+(k-l)*(fr[i]%mod)%mod)%mod;
}
}
int main()
{
scanf("%d",&n);
for(ri i=1; i<=n; ++i)scanf("%d",a+i);
solve(1,n);
printf("%lld",ans);
return 0;
}
```
by liumoumou_haha @ 2024-08-20 11:48:40