这不是求逆序对吗?我怎么错了
查看原帖
这不是求逆序对吗?我怎么错了
528287
多喝岩浆楼主2022/7/5 14:22
#include<bits/stdc++.h>
#define LL long long
#define PP pair <int, int>
using namespace std;
const int N = 1e5 + 10;
const int mid = 1e8 - 3;
struct hcz_feiwu {
	int l, r;
} a[N];
int n;
int ans;
int ls[N], tot;
int szsz[N];
inline int Get (int x) {
	return lower_bound (ls + 1, ls + tot + 1, x) - ls;
}
inline bool cmp (hcz_feiwu x, hcz_feiwu y) {
	return x.l < y.l;
}
inline int lowbit (int x) {
	return x & -x;
}
inline void insert (int x, int y) {
	for (; x <= n; x += lowbit (x) ) szsz[x] += y;
}
inline int query (int x) {
	int res = 0;
	while (x > 0) {
		res += szsz[x];
		x -= lowbit (x);
	}
	return res;
}
int main () {
	ios::sync_with_stdio (false);
	cin.tie (0), cout.tie (0);
	cin >> n;
	for (int i = 1; i <= n; i ++ ) cin >> a[i].l;
	for (int i = 1; i <= n; i ++ ) cin >> a[i].r;
	sort (a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i ++ ) ls[i] = a[i].r;
	sort (ls + 1, ls + n + 1);
	tot = unique (ls + 1, ls + n + 1) - ls - 1;
	for (int i = 1; i <= n; i ++ ) {
		insert (Get (a[i].r), 1);
		ans = ans + i - query (Get (a[i].r));
	}
	cout << ans << endl;
	return 0;
}
2022/7/5 14:22
加载中...