提出 #52918856

---

ソースコード 拡げる

// LUOGU_RID: 157360647
#include<iostream>
#include<algorithm>
#define ll long long

using std::sort;
const int N=4e5+5;
int n,q,i;
struct node{
	ll val,t,lz1,lz2;
}*t[N<<2]; 
int rank[N];
struct NODE{
	int val,id;
}a[N];

inline int ls(int p){
	return p<<1;
}
inline int rs(int p){
	return p<<1|1;
}
inline void pushup(int p){
	t[p]->val=t[ls(p)]->val+t[rs(p)]->val;
	t[p]->t=t[ls(p)]->t+t[rs(p)]->t; 
}
inline void tag1(int p,int l,int r,ll k){
	t[p]->val+=(r-l+1)*k;
	t[p]->lz1+=k;
}
inline void tag2(int p,int l,int r,ll k){
	t[p]->t+=(r-l+1)*k;
	t[p]->lz2+=k;
}
inline void pushdn1(int p,int l,int r){
	if(t[p]->lz1){
		int mid=(l+r)>>1;
		tag1(ls(p),l,mid,t[p]->lz1);
		tag1(rs(p),mid+1,r,t[p]->lz1);
		t[p]->lz1=0;
	}
}
inline void pushdn2(int p,int l,int r){
	if(t[p]->lz2){
		int mid=(l+r)>>1;
		tag2(ls(p),l,mid,t[p]->lz2);
		tag2(rs(p),mid+1,r,t[p]->lz2);
		t[p]->lz2=0;
	}
}
inline void build(int p,int l,int r){
	t[p]=new node;
	if(l==r){
		t[p]->t=0;t[p]->val=0;
		return;
	}
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
}
inline void update1(int p,int l,int r,int L,int R,ll k){
	if(L<=l&&R>=r){
		tag1(p,l,r,k);
		return;
	}
	pushdn1(p,l,r);
	int mid=(l+r)>>1;
	if(L<=mid){
		update1(ls(p),l,mid,L,R,k);
	}
	if(R>mid){
		update1(rs(p),mid+1,r,L,R,k);
	}
	pushup(p);
}
inline void update2(int p,int l,int r,int L,int R,ll k){
	if(L<=l&&R>=r){
		tag2(p,l,r,k);
		return;
	}
	pushdn2(p,l,r);
	int mid=(l+r)>>1;
	if(L<=mid){
		update2(ls(p),l,mid,L,R,k);
	}
	if(R>mid){
		update2(rs(p),mid+1,r,L,R,k);
	}
	pushup(p);
}
inline ll query1(int p,int l,int r,int L,int R){
	if(L<=l&&R>=r){
		return t[p]->val;
	}
	pushdn1(p,l,r);
	int mid=(l+r)>>1;
	ll s=0;
	if(L<=mid){
		s+=query1(ls(p),l,mid,L,R);
	}
	if(R>mid){
		s+=query1(rs(p),mid+1,r,L,R);
	}
	return s;
}
inline ll query2(int p,int l,int r,int L,int R){
	if(L<=l&&R>=r){
		return t[p]->t;
	}
	pushdn2(p,l,r);
	int mid=(l+r)>>1;
	ll s=0;
	if(L<=mid){
		s+=query2(ls(p),l,mid,L,R);
	}
	if(R>mid){
		s+=query2(rs(p),mid+1,r,L,R);
	}
	return s;
}

bool operator<(const NODE&x,const NODE&y){
	if(x.val==y.val) return x.id<y.id;
	return x.val<y.val;
}
int b[N];
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin>>n;
	for(i=1;i<=n;++i){
		std::cin>>a[i].val;
		a[i].id=i;
		b[i]=a[i].val;
	}
	sort(a+1,a+n+1);
	for(i=1;i<=n;++i){
		rank[a[i].id]=i;
	}
	for(i=1;i<=(n<<2);++i){
		t[i]=new node;
	}
	build(1,1,n);
	ll ans=0;
	for(i=n;i>=1;--i){
		ll s=query1(1,1,n,rank[i]+1,n);
		ll S=query2(1,1,n,rank[i]+1,n);
		ans+=s-1ll*S*b[i];
		update1(1,1,n,rank[i],rank[i],b[i]);
		update2(1,1,n,rank[i],rank[i],1);
	}
	std::cout<<ans<<'\n';
	return 0;
}

提出情報

ジャッジ結果