51Nod 1019 逆序数(线段树)

题目链接:逆序数

模板题。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i(a); i <= (b); ++i)

#define lson i << 1, L, mid

#define rson i << 1 | 1, mid + 1, R

const int N = 100010;

long long ans = 0;

struct node{

    int x, y;

    friend bool operator < (const node &a, const node &b){

        return a.x < b.x;

    }

} a[N];

int tree[N << 2];

int c[N];

int n;

inline void pushup(int i){

    tree[i] = tree[i << 1] + tree[i << 1 | 1];

}

void build(int i, int L, int R){

    tree[i] = 0;

    if (L == R) return ;

    int mid = (L + R) >> 1;

    build(lson);

    build(rson);

}

void update(int i, int L, int R, int pos, int val){

    if (L == R && L == pos){

        tree[i] += val;

        return;

    }

    int mid = (L + R) >> 1;

    if (pos <= mid) update(lson, pos, val);

    else update(rson, pos, val);

    pushup(i);

}

int query(int i, int L, int R, int l, int r){

    if (L == l && R == r) return tree[i];

    int mid = (L + R) >> 1;

    if (r <= mid) return query(lson, l, r);

    else if (l > mid) return query(rson, l, r);

    else return query(lson, l, mid) + query(rson, mid + 1, r);

}

int main(){

    scanf("%d", &n);

    rep(i, 1, n){

        scanf("%d", &a[i].x);

        a[i].y = i;

    }

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

    c[a[1].y] = 1; rep(i, 2, n) c[a[i].y] = a[i].x == a[i - 1].x ? c[a[i - 1].y] : c[a[i - 1].y] + 1;

    build(1, 1, n);  ans = 0;

    rep(i, 1, n){

        ans += (long long)query(1, 1, n, min(c[i] + 1, n), n);

        update(1, 1, n, c[i], 1);

    }

    printf("%lld\n", ans);

    return 0;

}