线段树--求逆序数

本文主要是介绍线段树--求逆序数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求逆序数，n<= 50000,ai < 1e9

oredr记录数字大小和顺序位置，sort后，对每个数，求比他小（即排序后在他前面的），但是原位置比他大（即order[j].second比他的order[i].second大）的数的个数，（线段树记录数的个数，在线段树总存入order[i].second即可得到）。

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespacestd;

const int maxn =50005;

pair<int,int> order[maxn];

int seg[maxn <<2];

void build(int l,int r,int rt)

{

    if(l == r)

    {

        seg[rt] =0;

        return;

    }

    int mid = (l + r) >>1;

    build(l, mid, rt <<1);

    build(mid +1, r, rt << 1 |1);

}

int query(int ql,int qr,int l,int r,int rt)

{

    if(ql <= l && r <= qr)return seg[rt];

    int res =0;

    int mid = (l + r) >>1;

    if(ql <= mid) res +=query(ql, qr, l, mid, rt <<1);

    if(mid < qr) res +=query(ql, qr, mid + 1, r, rt << 1 |1);

    return res;

}

void update(int num,int l,int r,int rt)

{

    if(l == r)

    {

        seg[rt] ++;

        return;

    }

    int mid = (l + r) >>1;

    if(num <= mid)update(num, l, mid, rt <<1);

    if(num > mid)update(num, mid + 1, r, rt << 1 |1);

    seg[rt] =seg[rt << 1] +seg[rt << 1 |1];

}

int main()

{

    int n;

    cin >> n;

    int sum =0;

    build(1, n,1);

    for (int i =1; i <= n; i ++) {

        scanf("%d",&order[i].first);

        order[i].second = i;

    }

    sort(order +1,order +1 + n);

    for (int i =1; i <= n; i ++) {

        sum += query(order[i].second, n,1, n,1);

        update(order[i].second,1, n, 1);

    }

    cout << sum <<endl;

    return0;

}

／／51nod1019

这篇关于线段树--求逆序数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---