样例为什么过不了?!
查看原帖
样例为什么过不了?!
816792
coritom楼主2024/3/11 21:52
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e4 + 5;
int n, tree1[maxn], tree2[maxn];
struct node{
	int x, val;
}a[maxn];
bool cmp(node x,node y){
	return x.val < y.val;
}
int lowbit(int x){ 
	return x & (-x); 
}
int query1(int x){
	int sum = 0;
	while(x){
		sum += tree1[x];
		x -= lowbit(x);
	}
	return sum;
}
void add1(int x, int k){
	while(x <= 50005){
		tree1[x] += k;
		x += lowbit(x);
	}
}
int query2(int x){
	int sum = 0;
	while(x){
		sum += tree2[x];
		x -= lowbit(x);
	}
	return sum;
}
void add2(int x, int k){
	while(x <= 50005){
		tree2[x] += k;
		x += lowbit(x);
	}
}
signed main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i].val >> a[i].x;
	}
	sort(a + 1, a + n + 1, cmp);
	int ans = 0; 
	for(int i = 1; i <= n; i++){
		int num = query1(a[i].x);
		int sum = query2(a[i].x);
		ans += 1LL * a[i].val * (num * a[i].x - sum);
		num = query1(50005) - query1(a[i].x);
		sum = query2(50005) - query2(a[i].x);
		ans += 1LL * a[i].val * (sum - num * a[i].x);
		add1(a[i].x, 1);
		add2(a[i].x, a[i].x);
	}
	cout << ans;
	return 0;
}
2024/3/11 21:52
加载中...