自动搬运

查看原文

来自洛谷，原作者为

	lmh .

搬运于2025-08-24 23:10:08，当前版本为作者最后更新于2025-02-23 18:06:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分五种情况：

$a_i\le a_k,a_j\le a_k$：显然。

$a_i\le a_k\le a_j$：答案为 $\min\{B,C\}(a_j-a_k)$。

$a_j\le a_k\le a_i$：答案为 $\min\{A,C\}(a_i-a_k)$。

$a_k\le a_i\le a_j$：答案为 $\min\{A+B,C\}(a_i-a_k)+\min\{B,C\}(a_j-a_i)$。

$a_k\le a_j\le a_i$：答案为 $\min\{A+B,C\}(a_j-a_k)+\min\{A,C\}(a_i-a_j)$。

令 $(A,B,C)\leftarrow (\min\{A,C\},\min\{B,C\},\min\{A+B,C\})$ 即可去掉式子里的根号。

对于第 2,3 种情况，可以在 $i$ 处记录答案，此时需要在权值线段树上维护 $(j,k)$ 的个数和答案中只和 $j,k$ 有关的部分。

对于第 4,5 种情况，可以在 $k$ 处记录答案，需要维护 $(i,j)$ 的个数和 $\max\{0,a_i-a_j\}\cdot A+\max\{0,a_j-a_i\}\cdot B+\min\{a_i,a_j\}\cdot C$，可以用树状数组记录 $\ge x$ 的 $a_i$ 的个数和它们的和。

时间复杂度 $O(n\log n)$，需要卡常。$\color{white}{下面给的这份代码常数不太能过。}$

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define lson (u<<1)
#define rson (u<<1|1)
const int N=500007;
int n,m;
uint ans,s,A,B,C,K,x[N],y[N],cnt[N<<2],len[N<<2],val[N<<2],tag[N<<2],sum[N<<2],extag[N<<2];
void addex(int u,uint v){val[u]+=v*cnt[u];extag[u]+=v;}
void add(int u,uint v){val[u]+=K*len[u]*v;tag[u]+=v;sum[u]+=cnt[u]*v;}
void pushdown(int u){
	if (tag[u]){
		add(lson,tag[u]);add(rson,tag[u]);tag[u]=0;
	}
	if (extag[u]){
		addex(lson,extag[u]);addex(rson,extag[u]);extag[u]=0;
	}
}
void add(int u,int l,int r,int L,int R,uint v){
	if (L<=l&&r<=R){addex(u,v);add(u,1);return;}
	int mid=l+r>>1;pushdown(u);
	if (L<=mid) add(lson,l,mid,L,R,v);
	if (R>mid) add(rson,mid+1,r,L,R,v);
	val[u]=val[lson]+val[rson];sum[u]=sum[lson]+sum[rson];
}
void modify(int u,int l,int r,int x,uint v,uint c){
	++cnt[u];len[u]+=y[x];sum[u]+=c;val[u]+=v;
	if (l==r) return;
	int mid=l+r>>1;pushdown(u);
	if (x<=mid) modify(lson,l,mid,x,v,c);
	else modify(rson,mid+1,r,x,v,c);
}
uint getcnt(int u,int l,int r,int L,int R){
	if (L<=l&&r<=R) return cnt[u];
	int mid=l+r>>1;pushdown(u);
	if (R<=mid) return getcnt(lson,l,mid,L,R);
	if (L>mid) return getcnt(rson,mid+1,r,L,R);
	return getcnt(lson,l,mid,L,R)+getcnt(rson,mid+1,r,L,R);
}
uint getsum(int u,int l,int r,int L,int R){
	if (L<=l&&r<=R) return sum[u];
	int mid=l+r>>1;pushdown(u);
	if (R<=mid) return getsum(lson,l,mid,L,R);
	if (L>mid) return getsum(rson,mid+1,r,L,R);
	return getsum(lson,l,mid,L,R)+getsum(rson,mid+1,r,L,R);
}
uint getval(int u,int l,int r,int L,int R){
	if (L<=l&&r<=R) return val[u];
	int mid=l+r>>1;pushdown(u);
	if (R<=mid) return getval(lson,l,mid,L,R);
	if (L>mid) return getval(rson,mid+1,r,L,R);
	return getval(lson,l,mid,L,R)+getval(rson,mid+1,r,L,R);
}
void output(int u,int l,int r){
	cout<<l<<' '<<r<<' '<<val[u]<<' '<<cnt[u]<<' '<<sum[u]<<' '<<len[u]<<endl;
	if (l==r) return;pushdown(u);
	int mid=l+r>>1;
	output(lson,l,mid);output(rson,mid+1,r);
}
struct BIT{
	uint cnt[N];
	void clear(){memset(cnt,0,sizeof(cnt));}
	void add(int x,uint v){
		while(x<=m){cnt[x]+=v;x+=x&-x;}
	}
	uint query(int x){
		uint sum=0;
		while(x){sum+=cnt[x];x&=x-1;}
		return sum;
	}
}X,Y;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>A>>B>>C;C=min(C,A+B);A=min(A,C);B=min(B,C);
	for (int i=1;i<=n;++i){cin>>x[i];y[i]=x[i];}
	sort(y+1,y+1+n);m=unique(y+1,y+1+n)-y-1;K=C-B;
	for (int i=1;i<=n;++i){
		x[i]=lower_bound(y+1,y+1+m,x[i])-y;
//		if (x[i]<m) cout<<getval(1,1,m,x[i]+1,m)<<' '<<getsum(1,1,m,x[i]+1,m)<<endl;
		if (x[i]<m) ans+=getval(1,1,m,x[i]+1,m)-getsum(1,1,m,x[i]+1,m)*y[x[i]]*C;
		add(1,1,m,1,x[i],B*y[x[i]]);
		uint c=i-1-X.query(x[i]),v=s-Y.query(x[i]);
//		cout<<i<<' '<<c<<' '<<v<<endl;
		modify(1,1,m,x[i],(v-c*y[x[i]])*A+c*y[x[i]]*C,c);
		s+=y[x[i]];
		X.add(x[i],1);Y.add(x[i],y[x[i]]);
//		output(1,1,m);
//		cout<<ans<<endl;
	}
	X.clear();Y.clear();
	memset(val,0,sizeof(val));memset(tag,0,sizeof(tag));memset(sum,0,sizeof(sum));memset(len,0,sizeof(len));memset(cnt,0,sizeof(cnt));memset(extag,0,sizeof(extag));
	K=-B;
	for (int i=n;i;--i){
		ans+=getval(1,1,m,x[i],m);
		add(1,1,m,1,x[i],B*y[x[i]]);
		modify(1,1,m,x[i],0,0);
	}
	X.clear();Y.clear();
	memset(val,0,sizeof(val));memset(tag,0,sizeof(tag));memset(sum,0,sizeof(sum));memset(len,0,sizeof(len));memset(cnt,0,sizeof(cnt));memset(extag,0,sizeof(extag));
	K=-A;
	for (int i=n;i;--i){
		ans+=A*y[x[i]]*getsum(1,1,m,1,x[i])+getval(1,1,m,1,x[i]);
		add(1,1,m,x[i],m,0);
		modify(1,1,m,x[i],0,0);
	}
	cout<<ans<<endl;
	return 0;
}