求助 对于一个node只规定了对权值排序 对答案有什么影响吗

P1908 逆序对

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% 可两个相同的元素对答案没有影响 为什么会错 求助大佬


|