// count_3d: 3D strict dominance counting via CDQ.
// Sort by x (counting sort), split each CDQ node at an x-group boundary (strict x),
// merge by y (strict), Fenwick on z (strict) with rollback reset.
// Base case: brute-force segments of size <= BASE (saves the shallow BIT levels).
#include <cstddef>
#include <cstring>
#include <algorithm>
namespace {
int N;
const unsigned *X, *Y, *Z;
unsigned *OUT;
int *ord, *tmp, *bit, *cnt;
const int BASE = 16;
static inline void bit_add(int i, int v) {
for (; i <= N; i += i & -i) bit[i] += v;
}
static inline int bit_sum(int i) {
int s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
static void sort_by_x(int n) {
for (int i = 0; i < n; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[X[i]]++;
int acc = 0;
for (int v = 0; v < n; v++) { int c = cnt[v]; cnt[v] = acc; acc += c; }
for (int i = 0; i < n; i++) ord[cnt[X[i]]++] = i;
}
static void sort_y_range(int l, int r) {
std::sort(ord + l, ord + r, [](int a, int b){ return Y[a] < Y[b]; });
}
void cdq(int l, int r) {
if (r - l <= 1) return;
if (r - l <= BASE) {
for (int i = l; i < r; i++) {
unsigned xi = X[ord[i]], yi = Y[ord[i]], zi = Z[ord[i]];
for (int j = i + 1; j < r; j++) {
if (xi < X[ord[j]] && yi < Y[ord[j]] && zi < Z[ord[j]]) OUT[ord[j]]++;
}
}
sort_y_range(l, r);
return;
}
int m = (l + r) >> 1;
int gs = m;
while (gs > l && X[ord[gs - 1]] == X[ord[gs]]) gs--;
int ge = m;
while (ge + 1 < r && X[ord[ge + 1]] == X[ord[ge]]) ge++;
if (gs > l) {
m = gs;
} else if (ge + 1 < r) {
m = ge + 1;
} else {
sort_y_range(l, r);
return;
}
cdq(l, m);
cdq(m, r);
int i = l, j = m, k = l;
while (i < m && j < r) {
if (Y[ord[i]] < Y[ord[j]]) {
bit_add((int)Z[ord[i]] + 1, 1);
tmp[k++] = ord[i++];
} else {
OUT[ord[j]] += (unsigned)bit_sum((int)Z[ord[j]]);
tmp[k++] = ord[j++];
}
}
while (i < m) { bit_add((int)Z[ord[i]] + 1, 1); tmp[k++] = ord[i++]; }
while (j < r) { OUT[ord[j]] += (unsigned)bit_sum((int)Z[ord[j]]); tmp[k++] = ord[j++]; }
for (int t = l; t < m; t++) bit_add((int)Z[ord[t]] + 1, -1);
memcpy(ord + l, tmp + l, (size_t)(r - l) * sizeof(int));
}
}
void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
N = n; X = x; Y = y; Z = z; OUT = out;
ord = new int[n];
tmp = new int[n];
bit = new int[n + 1];
cnt = new int[n + 1];
memset(bit, 0, (size_t)(n + 1) * sizeof(int));
for (int i = 0; i < n; i++) ord[i] = i;
sort_by_x(n);
cdq(0, n);
delete[] ord;
delete[] tmp;
delete[] bit;
delete[] cnt;
}