/* 3D dominance counting: for each i, count j with x[j]<x[i] && y[j]<y[i] && z[j]<z[i].
* CDQ divide & conquer over the x-sorted (time) axis with group-boundary splits,
* merge by y, Fenwick tree over z. Base case: brute force over small blocks.
* Works for n = 1e4 / 1e5 / 1e6. */
typedef unsigned u32;
static int N;
static const u32 *PX, *PY, *PZ;
static int *IDX, *TMP;
static u32 *BIT;
static u32 *ANS;
static int *GSTART, *GNEXT; /* GSTART[t] = start of t's x-group; GNEXT[t] = start of next group */
static inline void bit_add(int i, int v) {
for (; i <= N; i += i & (-i)) BIT[i] += (u32)v;
}
static inline u32 bit_sum(int i) {
u32 s = 0;
for (; i > 0; i -= i & (-i)) s += BIT[i];
return s;
}
/* sort the index range [l,r) by PY (insertion sort, small ranges) */
static inline void sort_y(int l, int r) {
for (int i = l + 1; i < r; i++) {
int v = IDX[i];
u32 vy = PY[v];
int j = i - 1;
while (j >= l && PY[IDX[j]] > vy) { IDX[j + 1] = IDX[j]; j--; }
IDX[j + 1] = v;
}
}
#define BASE 32
static void cdq(int l, int r) {
int len = r - l;
if (len <= 1) return;
if (len <= BASE) {
for (int a = l; a < r; a++) {
int ia = IDX[a];
u32 xa = PX[ia], ya = PY[ia], za = PZ[ia];
for (int b = a + 1; b < r; b++) {
int ib = IDX[b];
if (xa < PX[ib] && ya < PY[ib] && za < PZ[ib]) ANS[ib]++;
}
}
sort_y(l, r);
return;
}
/* all same x? then no pair inside can satisfy x_i < x_j strictly */
if (PX[IDX[l]] == PX[IDX[r - 1]]) { sort_y(l, r); return; }
int mid = (l + r) >> 1;
int gs = GSTART[mid];
mid = (gs > l) ? gs : GNEXT[gs];
if (mid <= l || mid >= r) { sort_y(l, r); return; }
cdq(l, mid);
cdq(mid, r);
/* cross pairs: i in [l,mid) (smaller x), j in [mid,r) */
int i = l;
int inserted = 0;
for (int j = mid; j < r; j++) {
int ij = IDX[j];
u32 yj = PY[ij];
while (i < mid && PY[IDX[i]] < yj) {
bit_add((int)PZ[IDX[i]] + 1, 1);
i++; inserted++;
}
ANS[ij] += bit_sum((int)PZ[ij]);
}
for (int k = l; k < i; k++) bit_add((int)PZ[IDX[k]] + 1, -1);
/* merge [l,mid) and [mid,r) by PY into TMP */
int a = l, b = mid, t = l;
while (a < mid && b < r) {
if (PY[IDX[a]] <= PY[IDX[b]]) TMP[t++] = IDX[a++];
else TMP[t++] = IDX[b++];
}
while (a < mid) TMP[t++] = IDX[a++];
while (b < r) TMP[t++] = IDX[b++];
for (int k = l; k < r; k++) IDX[k] = TMP[k];
}
void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
N = n;
if (n <= 0) return;
static int *ordbuf = 0;
static u32 *pybuf = 0, *pzbuf = 0, *ansbuf = 0, *bitbuf = 0;
static int *idxbuf = 0, *tmpbuf = 0, *gstabuf = 0;
/* persistent allocations (called once, but be safe) */
if (!ordbuf) {
ordbuf = new int[n];
pybuf = new u32[n]; pzbuf = new u32[n]; ansbuf = new u32[n];
bitbuf = new u32[n + 1];
idxbuf = new int[n]; tmpbuf = new int[n]; gstabuf = new int[2 * n + 2];
}
int *ord = ordbuf;
/* counting sort points by x */
{
static u32 *cnt = 0;
if (!cnt) cnt = new u32[n + 1];
for (int i = 0; i <= n; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[x[i]]++;
u32 s = 0;
for (int v = 0; v <= n; v++) { u32 c = cnt[v]; cnt[v] = s; s += c; }
/* stable */
for (int i = 0; i < n; i++) ord[cnt[x[i]]++] = i;
}
PX = x; PY = y; PZ = z;
IDX = idxbuf; TMP = tmpbuf; BIT = bitbuf; ANS = ansbuf; GSTART = gstabuf; GNEXT = gstabuf + n;
for (int t = 0; t < n; t++) { IDX[t] = ord[t]; ANS[t] = 0; }
for (int i = 0; i <= n; i++) BIT[i] = 0;
/* group starts: GSTA[t] = start index of t's x-group; GSTA[start] = next group start */
{
int t = 0;
while (t < n) {
u32 xv = PX[IDX[t]];
int e = t;
while (e < n && PX[IDX[e]] == xv) e++;
for (int k = t; k < e; k++) GSTART[k] = t;
GNEXT[t] = e;
t = e;
}
GNEXT[n] = n;
}
cdq(0, n);
for (int t = 0; t < n; t++) out[IDX[t]] = ANS[IDX[t]];
}