// Variant: per-node z-compression + PLAIN Fenwick (no gen/mark), reset by memset per node.
// The Fenwick bound is the node's distinct-z count d, so small nodes do few steps.
#include <cstddef>
#include <cstring>
#include <algorithm>
namespace {
int N;
const unsigned *X, *Y, *Z;
unsigned *OUT;
int *ord, *ordz, *tmp, *bit, *cnt, *zrank;
int D;
const int BASE = 16;
static inline void bit_add(int i) {
for (; i <= D; i += i & -i) bit[i] += 1;
}
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]; });
}
static void sort_z_range(int l, int r) {
std::sort(ordz + l, ordz + r, [](int a, int b){ return Z[a] < Z[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);
sort_z_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); sort_z_range(l, r); return; }
cdq(l, m);
cdq(m, r);
{
int i = l, j = m, k = l;
while (i < m && j < r) {
if (Z[ordz[i]] <= Z[ordz[j]]) tmp[k++] = ordz[i++];
else tmp[k++] = ordz[j++];
}
while (i < m) tmp[k++] = ordz[i++];
while (j < r) tmp[k++] = ordz[j++];
unsigned prev = Z[tmp[l]];
int rk = 0;
zrank[tmp[l]] = 0;
for (int t = l + 1; t < r; t++) {
if (Z[tmp[t]] != prev) { rk++; prev = Z[tmp[t]]; }
zrank[tmp[t]] = rk;
}
D = rk + 1;
memcpy(ordz + l, tmp + l, (size_t)(r - l) * sizeof(int));
}
memset(bit, 0, (size_t)(D + 1) * sizeof(int));
{
int i = l, j = m, k = l;
while (i < m && j < r) {
if (Y[ord[i]] < Y[ord[j]]) {
bit_add(zrank[ord[i]] + 1);
tmp[k++] = ord[i++];
} else {
OUT[ord[j]] += (unsigned)bit_sum(zrank[ord[j]]);
tmp[k++] = ord[j++];
}
}
while (i < m) { bit_add(zrank[ord[i]] + 1); tmp[k++] = ord[i++]; }
while (j < r) { OUT[ord[j]] += (unsigned)bit_sum(zrank[ord[j]]); tmp[k++] = ord[j++]; }
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];
ordz = new int[n];
tmp = new int[n];
bit = new int[n + 1];
cnt = new int[n + 1];
zrank = new int[n];
for (int i = 0; i < n; i++) ord[i] = i;
sort_by_x(n);
for (int i = 0; i < n; i++) ordz[i] = ord[i];
cdq(0, n);
delete[] ord;
delete[] ordz;
delete[] tmp;
delete[] bit;
delete[] cnt;
delete[] zrank;
}