代码

// k-dimensional dominance counting: out[i] = #{j : all dims of j < dims of i}
//
// Event-sequence CDQ with keys carried inline.
//   event (u64) = (key << 32) | (q << 31) | id          q = 1 for a "query" event
//   key = coordinate of dim (level+1): the field used by this level's merge.
//   The packing makes a plain unsigned comparison put, for equal keys, the query
//   event first -- exactly the strict-inequality rule (equal coords must not count).
//
//   solve(seq, m, d): seq is ordered by dim d (tie rule above), elements carry the
//   key for dim d+1; count pairs (insert before query) with dims d+1..K-1 strictly
//   smaller; return `out` = the same events merged by the carried key (= dim d+1).
//   Cross = A-inserts + B-queries re-keyed to dim d+2, recursed at level d+1.
//   d == K-1 : every (insert before query) pair qualifies -> running counter, O(m).
#include <cstring>
#include <cstdlib>
#include <cstdint>

typedef unsigned u32;
typedef uint64_t u64;

#ifndef KG_COND
#define KG_COND 0
#endif
#ifndef KG_PF
#define KG_PF 64
#endif
#ifndef KG_BASE
#define KG_BASE 32
#endif
#define KG_MAXK 5
#ifndef KG_ARENA
#define KG_ARENA (400u << 20)
#endif

namespace kg {

static int K;
static const u32 *XD[KG_MAXK];
static u32 *OUT;
static u64 *AB, *ABtop;
uint64_t g_peak = 0;

static inline int eid(u64 v) { return (int)(v & 0x7FFFFFFFu); }
static inline int eq_(u64 v) { return (int)((v >> 31) & 1); }
static inline int keep_test(int takeA, int role) { return 1 - (takeA ^ role); }
static inline u64 mk(u32 key, int q, int id) {
  return ((u64)key << 32) | ((u64)(1 - q) << 31) | (u64)id;
}

static void solve(u64 *seq, int m, int d, u64 *out, int needOut);

// small base: brute force over the pairs, then insertion-sort by the carried key
static void base_case(u64 *seq, int m, int d, u64 *out, int needOut) {
  int nd = K - (d + 2);
  u32 C[KG_BASE * 4];
  for (int t = 0; t < m; t++) {                 // issue all loads first (hide latency)
    int id = eid(seq[t]);
    for (int q = 0; q < nd; q++) __builtin_prefetch(&XD[d + 2 + q][id], 0, 1);
  }
  for (int t = 0; t < m; t++) {
    int id = eid(seq[t]);
    u32 *c = C + t * 4;
    for (int q = 0; q < nd; q++) c[q] = XD[d + 2 + q][id];
  }
  for (int t = 0; t < m; t++) {
    u64 v = seq[t];
    if ((v >> 31) & 1) continue;               // only query events (bit31 = insert)
    const u32 *cv = C + t * 4;
    u32 c = 0;
    for (int s = 0; s < t; s++) {
      u64 w = seq[s];
      if (!((w >> 31) & 1)) continue;          // only insert events
      if (!(w < v)) continue;                  // dim d+1 strictly smaller (inline key)
      const u32 *cw = C + s * 4;
      int ok = 1;
      for (int q = 0; q < nd; q++) if (cw[q] >= cv[q]) { ok = 0; break; }
      c += (u32)ok;
    }
    OUT[eid(v)] += c;
  }
  if (!needOut) return;
  for (int t = 1; t < m; t++) {
    u64 v = seq[t];
    int s = t - 1;
    while (s >= 0 && v < seq[s]) { seq[s + 1] = seq[s]; s--; }
    seq[s + 1] = v;
  }
  memcpy(out, seq, sizeof(u64) * (size_t)m);
}

static void solve(u64 *seq, int m, int d, u64 *out, int needOut) {
  if (m <= 1) return;
  if (d >= K - 1) {
    int cnt = 0;
    for (int t = 0; t < m; t++) {
      u64 v = seq[t];
      if ((v >> 31) & 1) cnt++;                       // insert (bit31 = 1)
      else OUT[eid(v)] += (u32)cnt;                   // query
    }
    return;
  }
  if (m <= KG_BASE) { base_case(seq, m, d, out, needOut); return; }
  (void)0;
  int h = m >> 1, r = m - h;
  u64 *save = ABtop;
  u64 *retA = ABtop; ABtop += h;
  u64 *retB = ABtop; ABtop += r;
  solve(seq, h, d, retA, 1);
  solve(seq + h, r, d, retB, 1);
  if (d == K - 2) {
    // Key here is dim K-1 and queries sort before inserts on ties, so an A-side insert
    // emitted before a B-side query has a strictly smaller dim-(K-1) value: one running
    // counter closes the whole cross count in place (no cross set, no extra level).
    // Branchless: buffer the answer into a dummy slot for the events that must not count.
    static u32 dummy_slot;
    u32 *dummy = &dummy_slot;
    int cnt = 0, ia = 0, ib = 0, t = 0;
    while (ia < h && ib < r) {
      u64 ea = retA[ia], eb = retB[ib];
      int takeA = (ea < eb);
      ia += takeA; ib += 1 - takeA;
      u64 v = takeA ? ea : eb;
      if (needOut) out[t] = v;
      t++;
      int ins = (int)((v >> 31) & 1);
      int keep = (takeA | ins) ^ 1;                 // 1 only for a B-side query
      u32 *dst = keep ? &OUT[eid(v)] : dummy;
      *dst += (u32)(keep ? cnt : 0);
      cnt += (takeA & ins);
    }
    while (ia < h) {
      u64 v = retA[ia++];
      if (needOut) out[t] = v;
      t++;
      cnt += (int)((v >> 31) & 1);
    }
    while (ib < r) {
      u64 v = retB[ib++];
      if (needOut) out[t] = v;
      t++;
      int ins = (int)((v >> 31) & 1);
      u32 *dst = ins ? dummy : &OUT[eid(v)];
      *dst += (u32)(ins ? 0 : cnt);
    }
    ABtop = save;
    return;
  }
  u64 *cross = ABtop; ABtop += m + 1;
  const int rekey = (d + 2 <= K - 1);
  const u32 *XN = XD[rekey ? d + 2 : 0];
  int ia = 0, ib = 0, cx = 0, t = 0;
  while (ia < h && ib < r) {
#if KG_PF
    if (!(ia & (KG_PF - 1)) && ia + KG_PF < h) __builtin_prefetch(&XN[eid(retA[ia + KG_PF])], 0, 1);
    if (!(ib & (KG_PF - 1)) && ib + KG_PF < r) __builtin_prefetch(&XN[eid(retB[ib + KG_PF])], 0, 1);
#endif
    u64 ea = retA[ia], eb = retB[ib];
    int takeA = (ea < eb);
    ia += takeA; ib += 1 - takeA;
    u64 v = takeA ? ea : eb;
    if (needOut) out[t] = v;
    t++;
    int role = (int)((v >> 31) & 1);
#if KG_COND
    if (keep_test(takeA, role)) {
      cross[cx++] = rekey ? (((u64)XN[eid(v)] << 32) | (v & 0xFFFFFFFFull)) : (v & 0xFFFFFFFFull);
    }
#else
    u64 c = rekey ? (((u64)XN[eid(v)] << 32) | (v & 0xFFFFFFFFull)) : (v & 0xFFFFFFFFull);
    cross[cx] = c;
    cx += keep_test(takeA, role);
#endif
  }
  while (ia < h) {
    u64 v = retA[ia++];
    if (needOut) out[t] = v;
    t++;
    if ((v >> 31) & 1) cross[cx++] = rekey ? (((u64)XN[eid(v)] << 32) | (v & 0xFFFFFFFFull)) : (v & 0xFFFFFFFFull);
  }
  while (ib < r) {
    u64 v = retB[ib++];
    if (needOut) out[t] = v;
    t++;
    if (!((v >> 31) & 1)) cross[cx++] = rekey ? (((u64)XN[eid(v)] << 32) | (v & 0xFFFFFFFFull)) : (v & 0xFFFFFFFFull);
  }
  u64 *cres = ABtop; ABtop += cx;
  solve(cross, cx, d + 1, cres, 0);
  ABtop = save;
  if ((u64)(ABtop - AB) > g_peak) g_peak = (u64)(ABtop - AB);
}

static u32 *g_ord, *g_x;

static void sort0(int n) {
  const u32 *X0 = XD[0];
  u32 *cnt = g_x;
  memset(cnt, 0, sizeof(u32) * (size_t)(n + 1));
  for (int i = 0; i < n; i++) cnt[X0[i] + 1]++;
  for (int i = 0; i < n; i++) cnt[i + 1] += cnt[i];
  for (int i = 0; i < n; i++) g_ord[cnt[X0[i]]++] = (u32)i;
}

void run(int n, const u32 **x, int k, u32 *out) {
  K = k;
  for (int d = 0; d < k; d++) XD[d] = x[d];
  OUT = out;
  ABtop = AB;
  if (n <= 1) return;
  sort0(n);
  const u32 *X0 = XD[0], *X1 = XD[1];
  u64 *ev = AB;                     // top-level event array: 2n entries
  int m = 0, g = 0;
  while (g < n) {
    int g1 = g;
    u32 v = X0[g_ord[g]];
    while (g1 < n && X0[g_ord[g1]] == v) g1++;
    for (int t = g; t < g1; t++) ev[m++] = mk(X1[g_ord[t]], 1, (int)g_ord[t]);
    for (int t = g; t < g1; t++) ev[m++] = mk(X1[g_ord[t]], 0, (int)g_ord[t]);
    g = g1;
  }
  ABtop = AB + m;
  u64 *res = ABtop; ABtop += m;
  if ((u64)(ABtop - AB) > g_peak) g_peak = (u64)(ABtop - AB);
  solve(ev, m, 0, res, 0);
}

}  // namespace kg

static u64 *g_arena;
#ifndef KG_NS
#define KG_NS 1000005
#endif
static u32 *g_ord_st, *g_x_st;
static int g_ready = 0;
unsigned long long kg_arena_used(){ return (unsigned long long)kg::g_peak; }

static void setup() {
  if (g_ready) return;
  g_ready = 1;
  g_arena = (u64 *)malloc(KG_ARENA);
  g_ord_st = (u32 *)malloc(sizeof(u32) * (size_t)KG_NS);
  g_x_st = (u32 *)malloc(sizeof(u32) * ((size_t)KG_NS + 1));
  kg::AB = g_arena;
  kg::g_ord = g_ord_st;
  kg::g_x = g_x_st;
}

void count_4d(int n, const unsigned *x[4], unsigned *out) {
  setup();
  memset(out, 0, sizeof(unsigned) * (size_t)n);
  kg::run(n, (const unsigned **)x, 4, out);
}
void count_5d(int n, const unsigned *x[5], unsigned *out) {
  setup();
  memset(out, 0, sizeof(unsigned) * (size_t)n);
  kg::run(n, (const unsigned **)x, 5, out);
}

评测结果