牛客ACM赛 C 区区区间间间

链接 C 区区区间间间

给定长度为$n$序列，求$$\sum_{i=1}^{n} \sum_{j=i}^{n} max-min$$
其中$max$，$min$为区间最大，最小值，$n\leq 10^5$。
$cdq$分治模板题，每次考虑跨过$mid$的区间。
如果考虑从$mid$到$le$枚举左端点，那么区间之间的最大最小值是单调的。
在右边维护$j,k$，表示当前最大、最小值能管辖到的最大范围。
那么贡献就是$mid$到$j,k$的长度和当前$mn,mx$的乘积，以及后面所有最大最小值的总和。
对$mid$到$r$前缀和优化即可。

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int N=100001;

ll n,t,w[N],Sm[N],Sx[N];ll ans;

int gi(){

	R x=0,k=1;char c=getchar();

	while((c<'0'||c>'9')&&c!='-')c=getchar();

	if(c=='-')k=-1,c=getchar();

	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

	return x*k;

}

void CDQ(R le,R ri){

	if(le==ri)return;

	R mid=(le+ri)>>1;CDQ(le,mid),CDQ(mid+1,ri);

	Sm[mid]=Sx[mid]=0;

	for(ll i=mid+1,mx=0,mn=1e9;i<=ri;++i){

		mx=max(mx,w[i]),mn=min(mn,w[i]);

		Sm[i]=Sm[i-1]+mn,Sx[i]=Sx[i-1]+mx;

	}

	for(ll i=mid,j=mid,k=mid,mx=0,mn=1e9;i>=le;--i){

		mx=max(mx,w[i]),mn=min(mn,w[i]);

		for(;j<ri&&w[j]>=mn&&w[j+1]>=mn;++j);

		for(;k<ri&&w[k]<=mx&&w[k+1]<=mx;++k);

		ans-=1ll*mn*(j-mid)+(Sm[ri]-Sm[j]);

		ans+=1ll*mx*(k-mid)+(Sx[ri]-Sx[k]);

	}

}

void sol(){

	n=gi(),ans=0;

	for(R i=1;i<=n;++i)w[i]=gi();

	CDQ(1,n),printf("%lld\n",ans);

}

int main(){

	t=gi();

	while(t--)sol();

	return 0;

}

巴特西

牛客ACM赛 C 区区区间间间

链接 C 区区区间间间

最新文章

热门文章