「COCI2014-2015#2」Norma 题解
题目大意
给定一个 \(n\) 个数的序列 \(a\)，求
\[\underset{i=1}{\overset{n}{\sum}}\underset{j=i}{\overset{n}{\sum}}(j-i+1)\min(a_i,a_{i+1},\dots,a_j)\max(a_i,a_{i+1},\dots,a_j) \]人话：求序列 \(a\) 的所有子序列的 \(\text{最小值}\times\text{最大值}\times\text{序列长度}\) 的和。
输入
第一行一个整数 \(n\)。
接下来 \(n\) 行，每行一个正整数，表示 \(a_i\)。
输出
一个正整数，表示答案。
结果对 \(10^9\) 取模。
思路
暴力
\(O(n^2)\) 做法。
显然，不用多说，直接上代码。
#include<bits/stdc++.h>
#define ll long long
const ll N=500010;
const ll p=1e9;
using namespace std;
ll n,a[N];
ll ans;
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
for(ll i=1;i<=n;i++){
ll maxx=a[i],minn=a[i];
for(ll j=i;j<=n;j++){
maxx=max(maxx,a[j]),minn=min(minn,a[j]);
ans=(ans+(j-i+1)*maxx%p*minn%p+p)%p;
}
}
printf("%lld",ans);
return 0;
}
正解
考虑分治。
那么问题转化为：计算区间左端点在 \([l,mid]\)，右端点在 \((mid,r]\) 时对答案的贡献。
令区间左端点为 \(i\)，区间 \([i,mid]\) 中最大值为 \(maxx\)，最小值为 \(minn\)；
\(p\) 为满足 \(minn<\min(a_{mid+1},a_{mid+2},\dots,a_{q})\) 的最大 \(p\)；
\(q\) 为满足 \(maxx>\max(a_{mid+1},a_{mid+2},\dots,a_{p})\) 的最大 \(q\)；
\(w_1=\min(p,q)\)，\(w_2=\max(p,q)\)。
则对于 \((mid,r]\) 这段区间，可以分为三个小区间：
-
\((mid,w_1]\)：所有子序列的最大最小值均为定值；
-
\((w_1,w_2]\)：所有子序列的最大最小值有一个为定值；
-
\((w_2,r]\)：所有子序列的最大最小值均不为定值。
第一个区间对答案的贡献为：
\[\underset{j=mid+1}{\overset{w_1}{\sum}}(j-i+1)\min(a_i,a_{i+1},\dots,a_j)\max(a_i,a_{i+1},\dots,a_j) \]\[=\underset{j=mid+1}{\overset{w_1}{\sum}}(j-i+1)\times minn\times maxx \]\[=minn\times maxx\times\underset{j=mid+1}{\overset{w_1}{\sum}}(j-i+1) \]\[=minn\times maxx\times\frac{((mid+1-i+1)+(w_1-i+1))\times(w_1-(mid+1)+1)}{2} \]\[=minn\times maxx\times\frac{(w_1+mid-2\times i+3)\times(w_1-mid)}{2} \]第二个区间对答案的贡献分两种情况：
- \(p > q\)
那么 \(minn\) 是定值，贡献为：
\[\underset{j=mid+1}{\overset{q}{\sum}}(j-i+1)\min(a_i,a_{i+1},\dots,a_j)\max(a_i,a_{i+1},\dots,a_j) \]\[=\underset{j=mid+1}{\overset{q}{\sum}}(j-i+1)\times minn\times\max(a_i,a_{i+1},\dots,a_j) \]\[=minn\times\underset{j=mid+1}{\overset{q}{\sum}}(j-i+1)\times\max(a_i,a_{i+1},\dots,a_j) \]对于后面的求和，实际上是可以前缀和优化的。只需要将求和中的 \(i\) 拆分出来。
\[=minn\times\underset{j=mid+1}{\overset{q}{\sum}}(j-i+1)\times\max(a_{mid+1},a_{mid+2},\dots,a_j) \]\[=minn\times\underset{j=mid+1}{\overset{q}{\sum}}(j-mid+mid-i+1)\times\max(a_{mid+1},a_{mid+2},\dots,a_j) \]\[=minn\times(\underset{j=mid+1}{\overset{q}{\sum}}(mid-i+1)\times\max(a_{mid+1},a_{mid+2},\dots,a_j)+\underset{j=mid+1}{\overset{q}{\sum}}(j-mid)\times\max(a_{mid+1},a_{mid+2},\dots,a_j)) \]化简到这里，我们发现已经可以前缀和优化了。
\[s1_{mid}=0 \]\[s1_x(x\in (mid,r])=s1_{x-1}+((x-mid)\times max(a_{mid+1},a_{mid+2},\cdots,a_{x}) \]\[s1'_{mid}=0 \]\[s1'_x(x\in (mid,r])=s1'_{x-1}+max(a_{mid+1},a_{mid+2},\cdots,a_{x}) \]所以原式化为：
\[minn\times((mid-i+1)\times(s1'_p-s1'_q)+(s1_p-s1_q)) \]- \(p < q\)
同 1 可得：
\[s2_{mid}=0 \]\[s2_x(x\in (mid,r])=s2_{x-1}+((x-mid)\times min(a_{mid+1},a_{mid+2},\cdots,a_{x}) \]\[s2'_{mid}=0 \]\[s2'_x(x\in (mid,r])=s2'_{x-1}+min(a_{mid+1},a_{mid+2},\cdots,a_{x}) \]对答案的贡献为：
\[maxx\times((mid-i+1)\times(s2'_q-s2'_p)+(s2_q-s2_p)) \]第三个区间对答案的贡献计算与第二个区间的思路大体相同：
\[s3_{mid}=0 \]\[s3_x(x\in (mid,r])=s3_{x-1}+((x-mid)\times min(a_{mid+1},a_{mid+2},\cdots,a_{x})\times max(a_{mid+1},a_{mid+2},\cdots,a_{x}) \]\[s3'_{mid}=0\\s3'_x(x\in (mid,r])=s3'_{x-1}+min(a_{mid+1},a_{mid+2},\cdots,a_{x}\times max(a_{mid+1},a_{mid+2},\cdots,a_{x})) \]对答案的贡献为：
\[(mid-i+1)\times(s3'_{r}-s3'_{w2})+(s3_{r}-s3_{w2}) \]最后综合一下即是答案。
代码实现
#include<bits/stdc++.h>
#define ll long long
const ll N=500010;
const ll mod=1e9;
using namespace std;
ll n,a[N],s1[N],s1_[N],s2[N],s2_[N],s3[N],s3_[N];
ll ans;
void f(ll l,ll r){
if(l==r){
ans=(ans+a[l]*a[l]%mod+mod)%mod;
return;
}
ll mid=l+r>>1;
ll minn=a[mid+1],maxx=a[mid+1];
s2[mid]=s1[mid]=s3[mid]=s2_[mid]=s1_[mid]=s3_[mid]=0;
for(ll i=mid+1;i<=r;++i){
minn=min(minn,a[i]),maxx=max(maxx,a[i]);
s1[i]=(s1[i-1]+maxx*(i-mid)%mod+mod)%mod;
s1_[i]=(s1_[i-1]+maxx+mod)%mod;
s2[i]=(s2[i-1]+minn*(i-mid)%mod+mod)%mod;
s2_[i]=(s2_[i-1]+minn+mod)%mod;
s3[i]=(s3[i-1]+minn*maxx%mod*(i-mid)%mod+mod)%mod;
s3_[i]=(s3_[i-1]+minn*maxx%mod+mod)%mod;
}
ll i,p,q;
i=p=q=mid;
minn=maxx=a[mid];
while(i>=l){
minn=min(minn,a[i]),maxx=max(maxx,a[i]);
while(p<r&&a[p+1]>minn)++p;
while(q<r&&a[q+1]<maxx)++q;
ll w1=min(p,q),w2=max(p,q);
//1
if(w1>mid)ans=(ans+minn*maxx%mod*((mid-2*i+w1+3)*(w1-mid)/2%mod)%mod+mod)%mod;
//2
if(p>q){
ans+=(minn*((mid-i+1)*(s1_[p]-s1_[q]+mod)%mod+(s1[p]-s1[q]+mod)%mod)%mod+mod)%mod;
}
if(p<q){
ans+=(maxx*((mid-i+1)*(s2_[q]-s2_[p]+mod)%mod+(s2[q]-s2[p]+mod)%mod)%mod+mod)%mod;
}
//3
ans+=(((mid-i+1)*(s3_[r]-s3_[w2]+mod)%mod+(s3[r]-s3[w2]+mod)%mod)%mod+mod)%mod;
i--;
}
f(l,mid);
f(mid+1,r);
}
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
f(1,n);
printf("%lld\n",ans%mod);
return 0;
}