【Codeforces】Gym 101485G Guessing Camels CDQ分治

gym比赛链接

题意

现在有个赛马比赛，有三个人赌马，给出了自己猜的马的排名。

即三个全排列，问有多少匹 "马对" \({i,j}(i<j)\) ，在三个人猜的排名中，相对顺序都一样。

思路

对于两匹马 \({i,j}\) ，当 i 在三个人中的位置都分别小于 j 在三个人中的位置时，会对答案贡献 1。

这是我们就把一匹马在三个人中的位置看成三个属性 a, b, c。

那么现在问题就转化成了三维偏序问题：给出一个有 n 个元素的序列，每个元素包括三个属性 a, b, c。问有多少个点对 \((i,j)\) 满足 \(a_i\leq b_i\ and\ b_i\leq b_j\ and\ c_i\leq c_j\)。

CDQ分治模板题。

代码

#include <algorithm>
#include <iostream>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#define emplace_back push_back
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const int seed = 12289;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int N = 2e5 + 10;

struct note {
    int a, b, c;
} arr[N];

bool cmp1(note x, note y)
{
    return x.a < y.a;
}

bool cmp2(note x, note y)
{
    return x.b < y.b;
}

struct treearray {
    int tree[N], k;
    ll rel;
    int lowbit(int x)
    {
        return x & (-x);
    }
    void update(int pos, int val)
    {
        for (; pos <= k; pos += lowbit(pos)) {
            tree[pos] += val;
        }
    }
    int sum(int pos)
    {
        int ans = 0;
        for (; pos; pos -= lowbit(pos)) {
            ans += tree[pos];
        }
        return ans;
    }
} tr;

void cdq(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) / 2;
    cdq(l, mid), cdq(mid + 1, r);
    sort(arr + l, arr + mid + 1, cmp2);
    sort(arr + mid + 1, arr + r + 1, cmp2);
    int i = l, j = mid + 1;
    for (; j <= r; j++) {
        while (arr[i].b < arr[j].b && i <= mid) {
            tr.update(arr[i].c, 1);
            i++;
        }
        tr.rel += tr.sum(arr[j].c - 1);
    }
    for (j = l; j < i; j++) {
        tr.update(arr[j].c, -1);
    }
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        arr[x].a = i;
    }
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        arr[x].b = i;
    }
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        arr[x].c = i;
    }
    sort(arr + 1, arr + 1 + n, cmp1);
    tr.k = n;
    cdq(1, n);
    printf("%lld\n", tr.rel);
    return 0;
}