P1908 逆序对 ——树状数组求逆序对模板

P1908

求逆序对，注意可能有重复数字，排序的时候要注意，否则会wa

C[x]表示1-x中已经有的数字数量,也就是说如果1-5中有3个数，那么逆序就是5-3=2，但是正序是C[x-1] = C[4] = 2

数组C中存的是正序对-1，所以每次操作要sum += i - sum(node[i].index)，这样才是逆序对

时间复杂度O(nlogn)

// Decline is inevitable,
// Romance will last forever.
// P1908
//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define mst(a, x) memset(a, x, sizeof(a))
#define INF 0x3f3f3f3f
//#define mp make_pair
#define pii pair
#define fi first
#define se second
#define ll long long
//#define int long long
const int maxn = 5e5 + 10;
const int maxm = 25;
const int P = 1e9 + 7;
int C[maxn], n, m;
struct Node {
    int v, index;
    bool operator <(const Node &x) const {
        if(v == x.v) return index < x.index;    //有重复数字则不能省略这句话
        return v < x.v;
    }
}node[maxn];
int lb(int x) {
    return x & -x;
}
int sum(int x) {    //前x组的和
    int ret = 0;
    while(x) {
        ret += C[x];
        x -= lb(x);
    }
    return ret;
}
void add(int x, int d) {    //第x组加d
    while(x <= n) {
        C[x] += d;
        x += lb(x);
    }
}
int t = 0;
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        int a;
        scanf("%d", &a);
        node[i].index = i;
        node[i].v = a;
    }
    sort(node + 1, node + n + 1);
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
        add(node[i].index, 1);
        ans += i - sum(node[i].index);
    }
    printf("%lldn", ans);
}
signed main() {
//    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int T; scanf("%d", &T); while(T--)
//    int T; cin >> T; while(T--)
    solve();
    return 0;
}

P1908 逆序对 ——树状数组求逆序对模板

C/C++/C#相关栏目本月热门文章