73pts树状数组求助
查看原帖
73pts树状数组求助
605945
luo_xiaoran楼主2023/10/18 09:58

#2#8#9WA

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll k,n,c1[20005],c2[20005];
const int M=(int)(2*1e4);
struct node{
	ll x,v;
}a[20005];
bool cmp(node p,node q){
	return p.v<q.v;
}
void addd(ll i,ll g){
	for(;i<M;i+=(i&-i)) c1[i]++,c2[i]+=g;
}
ll sum1(ll i){
	ll ans=0;
	for(;i;i-=(i&-i)) ans+=c1[i];
	return ans;
}
ll sum2(ll i){
	ll ans=0;
	for(;i;i-=(i&-i)) ans+=c2[i];
	return ans;
}
int main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].v,&a[i].x);
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		k+=1ll*a[i].v*(a[i].x*sum1(a[i].x-1)+sum2(M)-sum2(a[i].x)-sum2(a[i].x-1)-a[i].x*(sum1(M)-sum1(a[i].x)));
		addd((ll)a[i].x,(ll)a[i].x);
	} 
	
	printf("%lld",k);
	return 0;
}
/*

*/
2023/10/18 09:58
加载中...