Partial Order Problem (Divide and Conquer)

日付: 12月 03, 2018

## Problem
A partial order problem is something like this: Given $n$ points with coordinates $(x_{i1}, \cdots, x_{im})$, we want to calculate the number of $j$ such that $x_{jk} < x_{ik}, \quad 1\le k\le m$ is satisfied for every $i$.

## Solution
This kind of problems can be solved with divide and conquer (which is known as *CDQ's divide and conquer* in China). Take 3 dimensional partial order for example:
1. Sort all points by the first dimension. (divide-and-conquer will be done on this dimension)
2. Recursively solve the subranges. (here to solve a range is to calculate the **contributions** of that range, not to calculate the final answer)
3. Label each element with which range it is in.
4. Calculate contribution of left range to the right range. (we must make sure that any element in the right range will not affect the answer of the left range)
  
  4.1. Merge the left range and the right range by the order of the second dimension (the same idea with merge sort)
  
  4.2. Iterate on the merged total range (now the order of the second dimension is guaranteed), and maintain a fenwick tree for the third dimension. If current element is labeled in left range, update the fenwick tree, else calculate the contribution and update answer.

In fact, in #4.1 there is no need to maintain a fenwick tree, we can use nested divide and conquer to solve it:
1. Sort all points by the first dimension. 
2. Recursively solve the subranges. 
3. Label each element with which range it is in, store the result in array $Label1$
4. Merge the left range and the right range by the order of the second dimension
5. **Copy the merged range, and do another divide and conquer on it**
  
  5.1. Revursively solve subranges.

5.2. Label each element with which range it is in, store the result in array $Label2$

5.3. Merge the left range and right range by the order of the third dimension
  
  5.4. Iterate on all elements in the merged range and maintain a counter. If the current element is both in left range in $Label1$ and $Label2$, update the counter. If the current element is both in right range, add the counter to answer.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;

// Luogu. 3810
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    map<array<int, 3>, int> M;
    vector<array<int, 3>> Q;
    for (int i = 0; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        M[array<int, 3> {a, b, c}]++;
    }
    int idx = 0;
    vector<int> Dup;
    for (const auto &p : M) {
        Q.emplace_back(p.first);
        Dup.push_back(p.second);
        idx++;
    }
    vector<int> Ans(idx), I(idx), J(idx);
    vector<char> L1(idx), L2(idx);
    iota(I.begin(), I.end(), 0);
    sort(I.begin(), I.end(), [&](int i, int j) { return Q[i] < Q[j]; });
    auto dac1 = [&](int l, int r, auto f1) -> void {
        if (l + 1 >= r) return;
        int m = (l + r) >> 1;
        f1(l, m, f1), f1(m, r, f1);
        for (int i = l; i < r; i++) L1[I[i]] = i >= m;
        inplace_merge(&I[l], &I[m], &I[r], [&](int i, int j) { return Q[i][1] < Q[j][1]; });
        copy(&I[l], &I[r], &J[l]);
        auto dac2 = [&](int l, int r, auto f2) -> void {
            if (l + 1 >= r) return;
            int m = (l + r) >> 1;
            f2(l, m, f2), f2(m, r, f2);
            for (int i = l; i < r; i++) L2[J[i]] = i >= m;
            inplace_merge(&J[l], &J[m], &J[r], [&](int i, int j) { return Q[i][2] < Q[j][2]; });
            int cnt = 0;
            for (int i = l; i < r; i++) {
                int ii = J[i];
                if (!L1[ii] && !L2[ii]) cnt += Dup[ii];
                if (L1[ii] && L2[ii]) Ans[ii] += cnt;
            }
        };
        dac2(l, r, dac2);
    };
    dac1(0, idx, dac1);
    for (int i = 0; i < idx; i++) Ans[i] += Dup[i] - 1;
    vector<int> Cnt(n);
    for (int i = 0; i < idx; i++) Cnt[Ans[i]] += Dup[i];
    for (int i = 0; i < n; i++) printf("%d\n", Cnt[i]);
}
```

KONGROOの基地

このブログを検索

Partial Order Problem (Divide and Conquer)

コメント

コメントを投稿