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
", ans);
        
    return 0;
}