链接
思路
首先\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\sum\limits_{k=i}^{j}max(a_k)\)可以用单调队列求解。?
求解此题目,我们分治。计算\([l,mid]\)对\([mid+1,r]\)的贡献。 我们从后向前枚举\(mid\)到\(l\),定义为\(x\)。(\(A\)为\([x,mid]\)中的最小值,\(B\)为\([x,mid]\)中的最大值) 得到\(p\)(\([mid+1,r]\)中大于等于\(A\)的位置)和\(q\)(\([mid+1,r]\)中小于等于\(B\)的位置) 然后根据p,q的位置四种情况讨论,处理前缀和O1得到贡献。 显然p,q类似于单调队列是\(O(n)\)求得 代码有种简单但是恶心的感觉 复杂度\(O(nlogn)\)代码
#includeusing namespace std;const int N=1e6+7,inf=0x3f3f3f3f,mod=1e9;int read() { int x=0,f=1;char s=getchar(); for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1; for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0'; return x*f;}int n,a[N],ans;int ma[N],mi[N],sum_mi[N],sum_ma[N],sum_mimai[N],sum_mima[N],sum_mii[N],sum_mai[N];int jan(int a,int b) { int ans=(a-b); if(ans<0) ans+=mod; return ans;}void add(int &x,int y) { x+=y; if(x>=mod) x-=mod;}void cdq(int l,int r) { if(l>r) return; if(l==r) {ans=(1LL*a[l]*a[l]%mod+ans)%mod;return;} int mid=(l+r)>>1; cdq(l,mid),cdq(mid+1,r); sum_mi[mid]=sum_ma[mid]=sum_mima[mid]=sum_mimai[mid]=sum_mii[mid]=sum_mai[mid]=0; mi[mid]=inf,ma[mid]=0; for(int i=mid+1;i<=r;++i) { mi[i]=min(mi[i-1],a[i]); ma[i]=max(ma[i-1],a[i]); sum_mi[i]=(sum_mi[i-1]+mi[i])%mod; sum_ma[i]=(sum_ma[i-1]+ma[i])%mod; sum_mii[i]=(sum_mii[i-1]+1LL*mi[i]*i%mod)%mod; sum_mai[i]=(sum_mai[i-1]+1LL*ma[i]*i%mod)%mod; sum_mima[i]=(sum_mima[i-1]+1LL*mi[i]*ma[i]%mod)%mod; sum_mimai[i]=(sum_mimai[i-1]+1LL*mi[i]*ma[i]%mod*i%mod)%mod; } long long L,R; int p=mid,q=mid,A=a[mid],B=a[mid]; int tot=ans; for(int i=mid;i>=l;--i) { A=min(A,a[i]),B=max(B,a[i]); while(p <=a[p+1]) p++; while(q =a[q+1]) q++; L=mid+1,R=min(p,q); if(L<=R) add(ans,1LL*A*B%mod*((L+R+2-2LL*i)*(R-L+1)/2%mod)%mod); L=p+1,R=q; if(L<=R) add(ans,1LL*B*jan(sum_mii[R],sum_mii[L-1])%mod), add(ans,1LL*jan(1,i)*B%mod*jan(sum_mi[R],sum_mi[L-1])%mod); L=q+1,R=p; if(L<=R) add(ans,1LL*A*jan(sum_mai[R],sum_mai[L-1])%mod), add(ans,1LL*jan(1,i)*A%mod*jan(sum_ma[R],sum_ma[L-1])%mod); L=max(p+1,q+1),R=r; if(L<=R) add(ans,jan(sum_mimai[R],sum_mimai[L-1])), add(ans,1LL*jan(1,i)*jan(sum_mima[R],sum_mima[L-1])%mod); }}int main() { n=read(); for(int i=1;i<=n;++i) a[i]=read(); cdq(1,n); printf("%d",ans); return 0;}