1. 首页
2. 线段树
3. 本页

UVALive 7429 Guessing Camels (求逆序数对)

题意：~

思路：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PI;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 200010;

int sum[MAXN << 2];
int a[MAXN], b[MAXN], c[MAXN], id[MAXN];
int n;

inline void pushup(int rt)
{
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void build(int l, int r, int rt)
{
    if(l == r)
    {
        sum[rt] = 0;
        return;
    }
    int m = (l + r) >> 1;
    build(lson);
    build(rson);
    pushup(rt);
}

void modify(int p,int x, int l, int r, int rt)
{
    if(l == r)
    {
        sum[rt] ++;
        return;
    }
    int m = (l + r) >> 1;
    if(p <= m) modify(p, x, lson);
    else modify(p, x, rson);
    pushup(rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if(L <= l && r <= R) return sum[rt];
    int m = (l + r) >> 1;
    int res = 0;
    if(L <= m) res += query(L, R, lson);
    if(R > m) res += query(L, R, rson);
    return res;
}

LL solve(int x[], int y[])
{
    for(int i = 0; i < n; ++i) id[x[i]] = i;
    build(0, n - 1, 1);
    LL ans = 0;
    for(int i = 0; i < n; ++i)
    {
        ans += query(id[y[i]], n - 1, 0, n - 1, 1);
        modify(id[y[i]], 1, 0, n - 1, 1);
    }
    return ans;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n)
    {
        for(int i = 0; i < n; ++i) cin >> a[i];
        for(int i = 0; i < n; ++i) cin >> b[i];
        for(int i = 0; i < n; ++i) cin >> c[i];
        LL ans = solve(a, b) + solve(b, c) + solve(c, a);
        ans = (LL)n * (n - 1) / 2 - ans / 2;
        cout << ans << endl;
    }
    return 0;
}