bzoj4430 [Nwerc2015]Guessing Camels赌骆驼

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4430

【题解】

把每只骆驼在第一个人、第二个人、第三个人的位置找出来，然后做三维偏序即可。

排序+cdq分治+BIT

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 2e5 + ;

const int mod = 1e9+;

# define RG register

# define ST static

int n, a[M], b[M], c[M], pb[M], pc[M];

ll ans = ;

struct pa {

    int a, b, c, ans;

    pa() {}

    pa(int a, int b, int c, int ans) : a(a), b(b), c(c), ans(ans) {}

    friend bool operator <(pa a, pa b) {

        return a.b < b.b || (a.b == b.b && a.a < b.a) ||

               (a.b == b.b && a.a == b.a && a.c < b.c);

    }

}p[M], t[M];

struct BIT {

    int n, c[M];

    # define lb(x) (x&(-x))

    inline void set(int _n) {

        n = _n;

        memset(c, , sizeof c);

    }

    inline void edt(int x, int d) {

        for (; x<=n; x+=lb(x)) c[x] += d;

    }

    inline int sum(int x) {

        int ret = ;

        for (; x; x-=lb(x)) ret += c[x];

        return ret;

    }

    inline int sum(int x, int y) {

        if(x > y) return ;

        return sum(y) - sum(x-);

     }

}T;

inline void solve(int l, int r) {

    if(l == r) return;

    int mid = l+r>>, t1n = l-, t2n = mid;

    for (int i=l; i<=r; ++i)

        if(p[i].a <= mid) t[++t1n] = p[i];

        else t[++t2n] = p[i];

    for (int i=l; i<=r; ++i) p[i] = t[i];

    int j=l;

    for (int i=mid+; i<=r; ++i) {

        while(j<=mid && p[j].b <= p[i].b) T.edt(p[j].c, ), j++;

        p[i].ans += T.sum(p[i].c);

    }

    for (int i=l; i<j; ++i) T.edt(p[i].c, -);

    solve(l, mid);

    solve(mid+, r);

}

int main() {

    cin >> n; T.set(n);

    for (int i=; i<=n; ++i) scanf("%d", a+i);

    for (int i=; i<=n; ++i) scanf("%d", b+i), pb[b[i]] = i;

    for (int i=; i<=n; ++i) scanf("%d", c+i), pc[c[i]] = i;

    for (int i=; i<=n; ++i) p[i] = pa(i, pb[a[i]], pc[a[i]], );

//    for (int i=1; i<=n; ++i) printf("%d %d %d\n", p[i].a, p[i].b, p[i].c);

    sort(p+, p+n+);

    solve(, n);

    for (int i=; i<=n; ++i) ans += p[i].ans;

    cout << ans;

    return ;

}