ruye @ 2024-08-10 13:30:47
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 10;
int n;
int mp[N];
struct node {
int id, w;
}a[N];
bool cmp(node a, node b) {
//if(a.w == b.w) return a.id < b.id;
return a.w < b.w;
}
struct BIT {
int tr[N];
int lowbit(int x) { return x & -x; }
void clear() {
for (int i = 1; i <= n; i ++ ) tr[i] = 0;
}
void add(int x, int k) {
for (int i = x; i <= n; i += lowbit(i)) tr[i] += k;
}
int query(int x) {
int res = 0;
for (int i = x; i; i -= lowbit(i)) res += tr[i];
return res;
}
int ask(int l, int r) {
return query(r) - query(l - 1);
}
} tr;
signed main() {
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> a[i].w, a[i].id = i;
sort(a + 1, a + 1 + n, cmp);
for(int i = 1; i <= n; i ++ ) mp[a[i].id] = i;
int ans = 0;
for(int i = n; i >= 1; i -- ) {
tr.add(mp[i], 1);
ans += tr.query(mp[i] - 1);
}
cout << ans << endl;
return 0;
}
就是 我在cmp里不打上if(a.w == b.w) return a.id < b.id; 会错50% 可两个相同的元素对答案没有影响 为什么会错 求助大佬