【題解】Codeforces NWERC 2015 G. Guessing Camels

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, x, a[3][200005], bit[200005];
long long tot;
 
void update(int x){
    while (x <= n){
        bit[x]++;
        x += x & (-x);
    }
}
int query(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}
 
long long f(int b, int c){
    long long ret = 0;
    vector <pair<int, int> > v;
    for (int i = 1; i <= n; i++){
        v.push_back({a[b][i], a[c][i]});
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++){
        ret += query(v[i].second-1);
        update(v[i].second);
    }
    memset(bit, 0, sizeof(bit));
    return ret;
}
 
int main() {
    cin >> n;
    for (int i = 0; i < 3; i++){
        for (int j = 1; j <= n; j++){
            cin >> x;
            a[i][x] = j;
        }
    }
    tot += f(0, 1);
    tot += f(1, 2);
    tot += f(2, 0);
    tot -= (long long)n * (n-1) / 2;
    tot /= 2;
    cout << tot << "\n";
}