提出 #52970218

---

ソースコード 拡げる

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

using std::sort;
const int N=4e5+5;
int n,q,i;
ll t[N],ans=0;
ll T[N];
int rank[N];
int lowbit(int x){
	return x&-x;
}
struct NODE{
	int val;
	int id;
}a[N]; 
bool operator<(const NODE&x,const NODE&y){
	if(x.val==y.val) return x.id<y.id;
	return x.val<y.val;
}
void update(int x,int k){
	for(;x<=n;x+=lowbit(x))t[x]+=k;
}
ll query(int l){
	ll ans=0;
	for(;l;l-=lowbit(l)){
		ans+=t[l];
	}
	return ans;
}
void update2(int x,int k){
	for(;x<=n;x+=lowbit(x))T[x]+=k;
}
ll query2(int l){
	ll ans=0;
	for(;l;l-=lowbit(l)){
		ans+=T[l];
	}
	return ans;
}
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=n;i>=1;--i){
		ll S=query(n)-query(rank[i]);
		ll s=query2(n)-query2(rank[i]);
		update(rank[i],b[i]);
		update2(rank[i],1);
		ans+=S-s*b[i];
	}
	std::cout<<ans;
	return 0;
}

提出情報

ジャッジ結果