双倍经验：P6406P6406

题目描述

给定一个序列$ a_i,\cdots,a_n $，求：

∑i=1n∑j=in(j−i+1)min⁡(ai,ai+1,⋯ ,aj)max⁡(ai,ai+1,⋯ ,aj)\sum_{i=1}^{n} \sum_{j=i}^{n} (j-i+1) \min(a_i,a_{i+1},\cdots,a_j) \max(a_i,a_{i+1},\cdots,a_j)

分析

根据 $ n \leq 5\times10^5 ，，O(n^3)$ 的暴力肯定要炸，于是考虑分治，即把序列分成左区间与右区间，分别计算以下三种情况：

  1. 区间左右端点均落在左区间。

  2. 区间左右端点均落在右区间。

  3. 区间左端点落在左区间，区间右端点落在右区间。

其中第 11，22 种情况用分治递归解决就行了，于是来着重解决如何求第 33 种情况的问题。

首先，暴力枚举求第 33 种情况的时间复杂度显然是 O(n2)O(n^2)，总时间复杂度是 O(n2log⁡n)O(n^2 \log n)，肯定是过不了的。于是可以想一些关于区间的优化：

线段树？好吧，这个蒟蒻作者不会线段树维护区间最大最小值。

单调队列？虽然使用单调队列可以不用分治，但是由于区间长度是不定的，这也需要 O(n2)O(n^2) 的时间复杂度，还是过不了。

前缀和？前缀最小最大值的前缀和？这能算吗…好像真可以…

于是用分治+前缀和预处理，O(nlog⁡n)O(n \log n) 的时间复杂度就能过掉此题。

具体实现

（为什么要推这种式子啊）

如果在左区间内定一个下标 $ i $，对于每一个 $ i $，记 $ mi $ 为在 $ a_i,\cdots ,a_{mid} $ 内的最小值下标，$ mx $ 为该区间内最大值下标。显而易见，当 $ i=mid,mid-1,\cdots,1 $ 时，$ mi $ 与 $ mx $ 也是严格单调递减的。

同样的，记 $ mi_{to} $ 为右区间内最后一个大于 $ a[mi] $ 的下标，$ mx_{to} $ 为右区间内最后一个小于 $ a[mx] $ 的下标。同样显而易见的是，当 $ i=mid,mid-1,\cdots,1 $ 时，$ mi_{to} $ 与 $ mx_{to} $ 也是严格单调递增的。

所以，我们可以将第三种情况对于每一个 $ i $ 分 $ 3 $ 个部分来求：

第一个部分：$ [mid+1,\min(mi_{to},mx_{to})) $

这一部分最大值为 $ mx $，最小值为 $ mi $，直接等差数列求和就行了，这里就不赘述了。

第二个部分：$ [\min(mi_{to},mx_{to}),\max(mi_{to},mx_{to})) $

这一部分 $ mi_{to} $ 与 $ mx_{to} $ 只有一个可用，这个时候就要用前缀和了。假定 $ mi_{to} > mx_{to} $，最小值可用 $ mi_{to} $，最大值就只能用右区间的前缀最大值的前缀和。但是由于 $ i $ 不定，又不能针对于每一个 $ i $ 都算一遍（不然时间复杂度就爆炸了），所以前缀和要算两次，具体如下：

设 $ sum1_k $ 是 $ \max(a_{mid},\cdots,a_k) $ 的前缀和，$ sum2_k $ 是 $ (k + 1) \times \max(a_{mid},\cdots,a_k) $ 的前缀和。

由于区间长度为 $ k-i+1 $，所以可知，这一部分的贡献是 $ sum2[\max(mi_{to},mx_{to})]-sum2[\min(mi_{to},mx_{to})]-i\times(sum1[\max(mi_{to},mx_{to})]-sum1[\min(mi_{to},mx_{to})]) $。

（作者推式子好累，但打式子更累）

$ mi_{to} < mx_{to} $ 是一样的。

第三个部分：$ [\max(mi_{to},mx_{to}),r] $

只要第二部分搞出来了那这一部分就没什么问题了，不过是求 $ \max(a_{mid},\cdots,a_k) \times \min(a_{mid},\cdots,a_k) $ 和 $ (k+1)\times\max(a_{mid},\cdots,a_k) \times \min(a_{mid},\cdots,a_k) $ 的前缀和就行了。

这样这道题就搞出来了。

什么？你说取模爆炸了？来试试 __int128 吧！（见代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5;
const __int128 mod=1e9;
long long a[MAXN];
__int128 summin1[MAXN],summin2[MAXN],summax1[MAXN],summax2[MAXN],summul1[MAXN],summul2[MAXN];
__int128 fz(int l,int r){
	if(l==r)return a[l]*a[l];
	if(l+1==r)return (a[l]*a[l]+a[r]*a[r]+2*min(a[l],a[r])*max(a[l],a[r]));
	__int128 mid=(l+r)/2;
	__int128 ans=(fz(l,mid)+fz(mid+1,r));
	__int128 nowmin=a[mid+1],nowmax=a[mid+1];
	summin1[mid]=summin2[mid]=summax1[mid]=summax2[mid]=summul1[mid]=summul2[mid]=0;
	summin1[mid+1]=a[mid+1];
	summin2[mid+1]=a[mid+1]*(mid+2);
	for(int i=mid+2;i<=r;i++){
		if(a[i]<nowmin)nowmin=a[i];
		summin1[i]=summin1[i-1]+nowmin;
		summin2[i]=(i+1)*nowmin+summin2[i-1];
	}
	summax1[mid+1]=a[mid+1];
	summax2[mid+1]=a[mid+1]*(mid+2);
	for(int i=mid+2;i<=r;i++){
		if(a[i]>nowmax)nowmax=a[i];
		summax1[i]=summax1[i-1]+nowmax;
		summax2[i]=(i+1)*nowmax+summax2[i-1];
	}
	nowmin=a[mid+1],nowmax=a[mid+1];
	summul1[mid+1]=a[mid+1]*a[mid+1];
	summul2[mid+1]=a[mid+1]*a[mid+1]*(mid+2);
	for(int i=mid+2;i<=r;i++){
		if(a[i]<nowmin)nowmin=a[i];
		if(a[i]>nowmax)nowmax=a[i];
		summul1[i]=summul1[i-1]+nowmax*nowmin;
		summul2[i]=(i+1)*nowmax*nowmin+summul2[i-1];
	}
	int mi=mid,mx=mid,mi_to=mid,mx_to=mid;
	for(int k=mid;k>=l;k--){
		if(a[k]<a[mi])mi=k;
		if(a[k]>a[mx])mx=k;	
		while(a[mi_to]>=a[mi]&&mi_to<=r)mi_to++;
		if(mi_to>mid)mi_to--;
		while(a[mx_to]<=a[mx]&&mx_to<=r)mx_to++;
		if(mx_to>mid)mx_to--;
		ans+=(((min(mi_to,mx_to)-k+1+mid-k+2)*(min(mi_to,mx_to)-mid))*a[mi]*a[mx])/2;
		if(mi_to>mx_to)ans+=(summax2[mi_to]-summax2[mx_to]-k*(summax1[mi_to]-summax1[mx_to]))*a[mi];
		else ans+=(summin2[mx_to]-summin2[mi_to]-k*(summin1[mx_to]-summin1[mi_to]))*a[mx];
		ans+=(summul2[r]-summul2[max(mx_to,mi_to)]-k*(summul1[r]-summul1[max(mx_to,mi_to)]));
	}
	return ans;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	cout<<(long long)((fz(1,n))%mod);
}