Description
Input
第1行，一个整数N；
第2~n+1行，每行一个整数表示序列a。
Output
输出答案对10^9取模后的结果。
Sample Input
4
2
4
1
4
Sample Output
109
【数据范围】
N <= 500000
1 <= a_i <= 10^8
Solution
这题目好麻烦
考虑所有子区间问题的贡献可以考虑分治
假设当前到达 (l,r) 区间，计算跨过 (mid) 的贡献
一个指针 (x) 从 (mid) 往 (l) 枚举，枚举的过程中可以维护 (a) 和 (b) ，分别代表 ([x,mid]) 的最小值和最大值
再来两个指针 (p,q) ，从 (mid) 开始往右走，保证 ([mid+1,p]) 的最小值是 (a) ，([mid+1,q]) 的最大值是 (b) 的最大位置
那么对于当前的 (x) 位置，根据右端点的不同，出现了三种区间
- 右端点小于等于 (min { p,q }) ，这种区间的最小值最大值分别就是 (a,b) ，直接算就好了
- 右端点在 ((min {p,q} ,max {p,q}]) ，这种区间还要分两种情况，不过其本质是一样的。对于这种区间，我们知道了一个最值，而剩下的最值不知道，这样的话，把式子推出来 (sum_{y=min {p, q}+1}^{max {p, q}} (min_{k = mid}^{y} a_k) imes(y - x + 1) imes b) （这里是假设 (p<q) ），拆开后，可以发现预处理两个前缀和就好了
- 右端点大于 (max {p,q}) ，这种区间也还要推式子，(sum_{y=max {p, q}+1}^{r} (min_{k = mid}^{y} a_k) (max_{k = mid}^{y} a_k) imes(y - x + 1)) ，拆开后又发现是某些个前缀和的加加减减，预处理就好了
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=500000+10,Mod=1e9;
int n,a[MAXN],Mnr[MAXN],Mxr[MAXN];
ll sMn[MAXN],sMx[MAXN],mMn[MAXN],mMx[MAXN],sMxMn[MAXN],mMxMn[MAXN],ans;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch=' ')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!=' ')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void solve(int l,int r)
{
if(l==r)
{
(ans+=1ll*a[l]*a[r]%Mod)%=Mod;
return ;
}
int Mid=(l+r)>>1,p=Mid,q=Mid,Mnl=a[Mid],Mxl=a[Mid];
solve(l,Mid);solve(Mid+1,r);
sMn[Mid]=sMx[Mid]=mMn[Mid]=mMx[Mid]=sMxMn[Mid]=mMxMn[Mid]=0;
Mnr[Mid+1]=sMn[Mid+1]=Mxr[Mid+1]=sMx[Mid+1]=a[Mid+1];
mMn[Mid+1]=mMx[Mid+1]=1ll*a[Mid+1]*(Mid+1)%Mod;
sMxMn[Mid+1]=1ll*a[Mid+1]*a[Mid+1]%Mod;
mMxMn[Mid+1]=1ll*a[Mid+1]*a[Mid+1]%Mod*(Mid+1)%Mod;
for(register int i=Mid+2;i<=r;++i)
{
Mnr[i]=min(Mnr[i-1],a[i]);
Mxr[i]=max(Mxr[i-1],a[i]);
sMn[i]=(sMn[i-1]+Mnr[i])%Mod;
sMx[i]=(sMx[i-1]+Mxr[i])%Mod;
mMn[i]=(mMn[i-1]+1ll*Mnr[i]*i%Mod)%Mod;
mMx[i]=(mMx[i-1]+1ll*Mxr[i]*i%Mod)%Mod;
sMxMn[i]=(sMxMn[i-1]+1ll*Mnr[i]*Mxr[i]%Mod)%Mod;
mMxMn[i]=(mMxMn[i-1]+1ll*Mnr[i]*Mxr[i]%Mod*i%Mod)%Mod;
}
for(register int x=Mid;x>=l;--x)
{
chkmax(Mxl,a[x]);chkmin(Mnl,a[x]);
while(p<r&&Mnr[p+1]>=Mnl)++p;
while(q<r&&Mxr[q+1]<=Mxl)++q;
int lt=min(p,q),mt=max(p,q);
(ans+=1ll*(1ll*(Mid-x+2+lt-x+1)*(lt-Mid)/2)*Mxl%Mod*Mnl%Mod)%=Mod;
if(p<q)(ans+=(1ll*Mxl*(mMn[mt]-mMn[lt]+Mod)%Mod-1ll*(x-1)*Mxl%Mod*(sMn[mt]-sMn[lt]+Mod)%Mod+Mod)%Mod)%=Mod;
if(p>q)(ans+=(1ll*Mnl*(mMx[mt]-mMx[lt]+Mod)%Mod-1ll*(x-1)*Mnl%Mod*(sMx[mt]-sMx[lt]+Mod)%Mod+Mod)%Mod)%=Mod;
(ans+=((mMxMn[r]-mMxMn[mt]+Mod)%Mod-1ll*(x-1)*(sMxMn[r]-sMxMn[mt]+Mod)%Mod+Mod)%Mod)%=Mod;
}
}
int main()
{
read(n);
for(register int i=1;i<=n;++i)read(a[i]);
solve(1,n);
write(ans,'
');
return 0;
}