求助!
查看原帖
求助!
814343
bc2_cryeggy楼主2024/1/16 21:56
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>

using namespace std;

using ll = long long;

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1, kMod = 1e9 + 7;
const ll kLInf = 9.22e18;

int n, tree[kMaxN], rk[kMaxN];
int lowbit(int x) {return ((x) & -(x));}

struct node {
	int a, b;
	bool operator< (const node &b) const {
    return a < b.a;
  }
} b[kMaxN];

struct node2 {
	int id, val;
} a[kMaxN];

bool cmp(node2 a, node2 b) {
	if (a.val == b.val) {
		return a.id < b.id;
	}
	return a.val < b.val;
}

void Update(int x, int d) {
	for (; x <= kMaxN; tree[x] += d, x += lowbit(x));
}

int Sum(int x) {
	int ans = 0;
	for (; x > 0; ans += tree[x], x -= lowbit(x));
	return ans;
}

int ReverseOrderPair() {
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; ++ i) {
    rk[a[i].id] = i;
	}
	int cnt = 0;
	for (int i = n; i >= 1; -- i) {
		Update(rk[i], 1);
		cnt += Sum(rk[i] - 1);
	}
	return cnt;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	for (cin >> t; t; -- t) {
		memset(tree, 0, sizeof tree);
    cin >> n;
		for (int i = 1; i <= n; ++ i) {
			cin >> b[i].a >> b[i].b;
		}
		sort(b + 1, b + n + 1);
		for (int i = 1; i <= n; ++ i) {
      a[i].val = b[i].b;
			a[i].id = i;
		}
    cout << ReverseOrderPair() << '\n';
	}
  return 0;
}
2024/1/16 21:56
加载中...