Soltuion Norma

题目大意:求

[sum_{i=1}^{n}sum_{j=i}^{n}(j-i+1) cdot min[j,i] cdot max[j,i] ]

(cdq)分治

分析：

求树上所有点对我们有点分治，求所有子序列我们也可以考虑(cdq)分治

设当前统计([l,r]),中点(mid)，我们要统计跨(mid)的子序列对答案的贡献

不难想到，我们用一个指针(i in[l,mid])逆序枚举，这样我们可以在(O(n))的时间内统计出序列在(mid)左端部分的最小/大值

然后我们看([i,mid])这段对右边的影响，我们设右端第一个小于(mi)的位置为(p)，第一个大于(mx)的位置为(q)，([i,mid])这段最小/大值为(mi/mx)

分类讨论，不妨设(p < q)，另一种情况同理

(1.)右端点(j in (mid,p))

对答案的贡献

(mi cdot mx cdot sum_{j=mid+1}^{p-1}(j-i+1))

显然左边一个常数，右边等差数列求和（高斯笑而不语）

(2.)右端点(j in [p,q))

对答案的贡献

(mx cdot sum_{j=p}^{q-1}min[j] cdot(j-i+1))

其中(min[j])表示([mid + 1,j])中最小值,(max[j])同理

这玩意儿不好算拆开来

(mx cdot (sum_{j=p}^{q-1}(min[j] cdot j - min[j] cdot i + min[j])))

我们维护一下(min[j],min[j] cdot j)的前缀和即可

(3.)右端点(jin[q,r])

对答案贡献

(sum_{j=q}^{r}min[j] cdot max[j] cdot (j - i + 1))

拆拆拆

(sum_{j=q}^{r}(min[j] cdot max[j] cdot j - min[j] cdot max[j] cdot i + min[j] cdot max[j]))

同理，维护(min[j]cdot max[j],min[j] cdot max[j] cdot j)前缀和

(p > q)同理

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn = 5e5 + 100,mod = 1e9;
typedef long long ll;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x; 
}
int n,val[maxn],mi,mx;
ll ans,smi[maxn],smii[maxn],smx[maxn],smxi[maxn],smix[maxn],smixi[maxn],p,q;
inline ll gauss(int l,int r){
	return ll(l + r) * (r - l + 1) / 2 % mod;
}
inline ll getsum(ll *val,int l,int r){return (val[r] - val[l - 1]) % mod;}
inline void cdq(int l,int r){
	if(l == r){(ans += (ll)val[l] * val[l]) %= mod;return;}
	int mid = (l + r) >> 1;
	cdq(l,mid),cdq(mid + 1,r);
	smi[mid] = smii[mid] = smx[mid] = smxi[mid] = smix[mid] = smixi[mid] = 0;
	mi = 0x7fffffff,mx = -0x7fffffff;
	for(int i = mid + 1;i <= r;i++){
		mi = min(mi,val[i]);
		mx = max(mx,val[i]);
		smi[i] = (smi[i - 1] + mi) % mod;
		smii[i] = (smii[i - 1] + (ll)mi * i % mod) % mod;
		smx[i] = (smx[i - 1] + mx) % mod;
		smxi[i] = (smxi[i - 1] + (ll)mx * i % mod) % mod;
		smix[i] = (smix[i - 1] + (ll)mi * mx % mod) % mod;
		smixi[i] = (smixi[i - 1] + (ll)mi * mx % mod * i % mod) % mod;
	}
	mi = 0x7fffffff,mx = -0x7fffffff,p = q = mid + 1;
	for(int i = mid;i >= l;i--){
		mi = min(mi,val[i]);
		mx = max(mx,val[i]);
		while(p <= r && val[p] > mi)p++;
		while(q <= r && val[q] < mx)q++;
		if(p < q){
			(ans += (ll)mx * mi % mod * gauss(mid - i + 2,p - i)) %= mod;
			(ans += mx * (getsum(smii,p,q - 1) - (i * getsum(smi,p,q - 1) % mod) + getsum(smi,p,q - 1) + mod) % mod) %= mod;
			(ans += (getsum(smixi,q,r) - (i * getsum(smix,q,r) % mod) + getsum(smix,q,r)) % mod + mod) %= mod;
		}else{
			(ans += (ll)mx * mi % mod * gauss(mid - i + 2,q - i)) %= mod;
			(ans += mi * (getsum(smxi,q,p - 1) - (i * getsum(smx,q,p - 1) % mod) + getsum(smx,q,p - 1) + mod) % mod) %= mod;
			(ans += (getsum(smixi,p,r) - (i * getsum(smix,p,r) % mod) + getsum(smix,p,r)) % mod + mod) %= mod;
		}
	}
}
int main(){
	n = read();
	for(int i = 1;i <= n;i++)val[i] = read();
	cdq(1,n);
	printf("%lld
",ans);
	return 0;
}