P1908 逆序对

本文主要是介绍P1908 逆序对，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e5 + 10;
int n, m, len;
LL ans;
int a[N], num[N];
struct node {
    int l, r;
    int cnt;
}tr[N * 4];
int find(int x)
{
    return lower_bound(num + 1, num + 1 + len, x) - num;
}
void pushup(int u)
{
    tr[u].cnt = tr[u << 1].cnt + tr[u << 1 | 1].cnt;
}
void build(int u, int l, int r)
{
    tr[u] = {l, r, 0};
    if (l == r)  return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void modify(int u, int x)
{
    if (tr[u].l == x && tr[u].r == x) {
        tr[u].cnt ++;
        return;
    }
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid)   modify(u << 1, x);
    if (x > mid)    modify(u << 1 | 1, x);
    pushup(u);
}
int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].cnt;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if (l <= mid)   res = query(u << 1, l, r);
    if (r > mid)    res += query(u << 1 | 1, l , r);
    return res;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )  {
        scanf("%d", &a[i]);
        num[i] = a[i];
    }
    sort(num + 1, num + 1 + n);
    len = unique(num + 1, num + 1 + n) - num - 1;
    build(1, 1, len);
    for (int i = 1; i <= n; i ++ ) {
        modify(1, find(a[i]));
        ans += i - query(1, 1, find(a[i]));
    }
    printf("%lld\n", ans);
    return 0;
}

这篇关于P1908 逆序对的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！