代码

// References:
// [1] saffah_codex_6s_agg2, duck.ac submission #102744,
//     https://duck.ac/submission/102744 . Its complete CDQ three-dimensional
//     dominance engine, SIMD leaf accumulator and 128-record clear crossover
//     are directly copied as the base.
// [2] saffah_cc_v41_agg1, duck.ac submission #101102,
//     https://duck.ac/submission/101102 . CDQ, leaf bitonic sort, and
//     prefetching inherited through [1].
// [3] saffah_cc_v41_260924, duck.ac submissions #101087, #101079
//     and #99994: https://duck.ac/submission/101087,
//     https://duck.ac/submission/101079 and
//     https://duck.ac/submission/99994 . Z-prefix counter and bitonic
//     leaf sort inherited through [2].
// [4] saffah_cc_v41_agg1, duck.ac submission #100129,
//     https://duck.ac/submission/100129 . Masked SIMD leaf tail and
//     scatter prefetch inherited through [2].
// No explicit license was displayed on these public submissions. Authors,
// URLs and reused components are credited above.
// Approach:
// In the touched-clear path, reset the tiny C2 level once as a short
// contiguous vector sweep rather than writing its same 32-byte group for
// every inserted record. Continue touching only needed ZB and C1 groups.
// Purpose:
// Measure whether removing duplicate C2 stores clears the current strict
// 1009a threshold on duck.ac.
#include <string.h>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
typedef unsigned u32;
typedef unsigned long long u64;
typedef unsigned char u8;
typedef unsigned short u16;

static const int MAXN = 1000001;
int g_nz = 0;
#ifndef ZCTHR
#define ZCTHR 16
#endif

#define W_Y(v)    ((u32)((v) >> 40))
#define W_ORIG(v) ((u32)(((v) >> 20) & 0xFFFFFu))
#define W_A(v)    ((u32)((v) & 0xFFFFFu))
#define W_T(v)    ((u32)((v) >> 40))
#define W_R(v)    ((u32)(((v) >> 20) & 0xFFFFFu))
#define W_X(v)    ((u32)((v) & 0xFFFFFu))

// +16 u64 of pad per row keeps the two buffers off a 4096-byte multiple (4K aliasing)
static u64 RC[2][2 * (MAXN + 8)] __attribute__((aligned(64)));
static u64 TIE[(MAXN + 63) / 64 + 8];   // TIE[p] bit = (x[p-1] == x[p])
// H64 and CNT are only live during the BUILD, i.e. before the CDQ ping-pong needs RC[1].
// Aliasing them onto RC[1] removes 1.2 MB of first-touch pages (measured ~0.064 us/KB).
#define H64  ((u64 *)(void *)RC[1])
#define CNT  ((u32 *)(void *)(RC[1] + (MAXN + 8)))

// ---------- z counter: prefix count over rank domain [0,n) ----------
// LV<=3 COUNTER (n <= 262144, i.e. this row):
//   C1[w] (u16) = # inserted ranks in [(w&~15)*64, w*64)   -- cumulative in a 16-WORD group
//   C2[p] (u16) = # inserted ranks in [(p&~15)*1024, p*1024) -- cumulative in a 16-BLOCK group
//   C3[q] (u32) = # inserted ranks in [0, q*16384)          -- global cumulative
//   count(<T) = C3[T>>14] + C2[T>>10] + C1[T>>6] + popcount(ZB[T>>6] & ((1<<(T&63))-1))
// The query is then FOUR SCALAR LOADS and no vector code at all.  The three suffix
// increments in zadd are one aligned 32-byte load/add/store each (windows never partially
// overlap, so store-to-load forwarding is clean).
static u64 ZB[(MAXN + 63) / 64 + 16] __attribute__((aligned(64)));   // bit per rank
static u16 C1[(MAXN + 63) / 64 + 32] __attribute__((aligned(32)));   // per-word cumulative (group 16 words = 1024 ranks)
static u16 C2[(MAXN + 1023) / 1024 + 32] __attribute__((aligned(32)));// per-1024 cumulative (group 16 blocks = 16384 ranks)
static u32 C3[8] __attribute__((aligned(32)));                       // global cumulative per 16384 ranks (LV<=3)
// LV>=4 fallback (unchanged classic counter, not used on this row)
static u8  ZW1[(MAXN + 63) / 64 + 32];
static u16 ZW2[(MAXN + 1023) / 1024 + 32];
static u16 ZW3[(MAXN + 16383) / 16384 + 32];
static u32 ZW4[(MAXN + 262143) / 262144 + 32];

static const u16 IDX16[16] __attribute__((aligned(32))) = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
static const u32 IDX8[8]   __attribute__((aligned(32))) = {0,1,2,3,4,5,6,7};
// add +1 (sgn=+1) / -1 (sgn=-1) to lanes (t0, 15] of the 16-lane u16 group at p
static inline void grp16(u16 *p, u32 t0, int sgn) {
  __m256i x = _mm256_load_si256((const __m256i *)(const void *)p);
  __m256i m = _mm256_cmpgt_epi16(_mm256_load_si256((const __m256i *)(const void *)IDX16),
                                 _mm256_set1_epi16((short)t0));
  x = sgn > 0 ? _mm256_sub_epi16(x, m) : _mm256_add_epi16(x, m);
  _mm256_store_si256((__m256i *)(void *)p, x);
}
static inline void grp8(u32 *p, u32 t0, int sgn) {
  __m256i x = _mm256_load_si256((const __m256i *)(const void *)p);
  __m256i m = _mm256_cmpgt_epi32(_mm256_load_si256((const __m256i *)(const void *)IDX8),
                                 _mm256_set1_epi32((int)t0));
  x = sgn > 0 ? _mm256_sub_epi32(x, m) : _mm256_add_epi32(x, m);
  _mm256_store_si256((__m256i *)(void *)p, x);
}
template <int LV> static inline void zclear() {
  memset(ZB,  0, (size_t)((g_nz + 63) / 64) * 8);
  memset(C1,  0, (size_t)(((g_nz + 63) / 64 + 15) / 16) * 32);     // whole 16-entry groups
  memset(C2,  0, (size_t)(((g_nz + 1023) / 1024 + 15) / 16) * 32);
  memset(C3,  0, 32);
  if (LV >= 4) {   // classic upper levels, used only by the LV>=4 fallback
    memset(ZW1, 0, (size_t)((g_nz + 63) / 64));
    memset(ZW2, 0, (size_t)((g_nz + 1023) / 1024) * 2);
    memset(ZW3, 0, (size_t)((g_nz + 16383) / 16384) * 2);
    memset(ZW4, 0, (size_t)((g_nz + 262143) / 262144) * 4);
  }
}
// Upper LEVELS are tiny; clear them inline (no libc call per node).
static inline void zclear_upper() {
  __m128i z = _mm_setzero_si128();
  int i2 = (g_nz + 1023) / 1024, q2 = (i2 + 7) >> 3;
  for (int q = 0; q < q2; q++) _mm_storeu_si128((__m128i *)(void *)(ZW2 + 8 * q), z);
  int i3 = (g_nz + 16383) / 16384, q3 = (i3 + 7) >> 3;
  for (int q = 0; q < q3; q++) _mm_storeu_si128((__m128i *)(void *)(ZW3 + 8 * q), z);
  int i4 = (g_nz + 262143) / 262144, q4 = (i4 + 3) >> 2;
  for (int q = 0; q < q4; q++) _mm_storeu_si128((__m128i *)(void *)(ZW4 + 4 * q), z);
  int i1 = (g_nz + 63) / 64, q1 = (i1 + 15) >> 4;
  for (int q = 0; q < q1; q++) _mm_storeu_si128((__m128i *)(void *)(ZW1 + 16 * q), z);
}
// Touched-only clear: the ZB word (and, at LV<=3, the C1/C2 GROUPS) of the ranks this node
// inserted.  ⚠ At LV>=4 the classic ZW1/ZW2/ZW3 levels are live and MUST be cleared here too
// -- clearing only ZB/C1/C2 would leave them stale.
template <int LV> static inline void zclear_touched(int l, int aIns, const u64 *S) {
  __m256i z = _mm256_setzero_si256();
  for (int k = l; k < aIns; k++) {
    u32 r = W_R(S[2 * k + 1]);
    ZB[r >> 6] = 0;
    if (LV <= 3) {
      _mm256_store_si256((__m256i *)(void *)(C1 + ((r >> 6) & ~15u)), z);
    }
  }
  if (LV <= 3) {
    // C2 has only ceil(n/16384) vectors, fewer than repeated touched stores.
    int groups = ((g_nz + 1023) / 1024 + 15) / 16;
    for (int i = 0; i < groups; i++)
      _mm256_store_si256((__m256i *)(void *)(C2 + i * 16), z);
    _mm256_store_si256((__m256i *)(void *)C3, z);
  } else zclear_upper();
}

static inline __m256i mkI16() { return _mm256_setr_epi16(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); }
static inline __m128i mkI8() { return _mm_setr_epi8(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); }
static inline __m256i mkOne16() { return _mm256_set1_epi16(1); }

template <int LV> static inline void zadd(u32 r) {
  ZB[r >> 6] |= 1ull << (r & 63);
  if (LV <= 3) {
    u32 w = r >> 6, p = r >> 10;
    grp16(C1 + (w & ~15u), w & 15u, +1);
    grp16(C2 + (p & ~15u), p & 15u, +1);
    grp8(C3, r >> 14, +1);
  } else { ZW1[r >> 6]++; ZW2[r >> 10]++; ZW3[r >> 14]++; ZW4[r >> 18]++; }
}
template <int LV> static inline void zsub(u32 r) {
  ZB[r >> 6] &= ~(1ull << (r & 63));
  if (LV <= 3) {
    u32 w = r >> 6, p = r >> 10;
    grp16(C1 + (w & ~15u), w & 15u, -1);
    grp16(C2 + (p & ~15u), p & 15u, -1);
    grp8(C3, r >> 14, -1);
  } else { ZW1[r >> 6]--; ZW2[r >> 10]--; ZW3[r >> 14]--; ZW4[r >> 18]--; }
}
static inline u32 hsum256(__m256i s) {
  __m128i lo = _mm256_castsi256_si128(s), hi = _mm256_extracti128_si256(s, 1);
  __m128i t = _mm_add_epi32(lo, hi);
  t = _mm_add_epi32(t, _mm_shuffle_epi32(t, _MM_SHUFFLE(1, 0, 3, 2)));
  t = _mm_add_epi32(t, _mm_shuffle_epi32(t, _MM_SHUFFLE(2, 3, 0, 1)));
  return (u32)_mm_cvtsi128_si32(t);
}
template <int LV> static inline u32 zquery(u32 T) {
  if (LV <= 3) {
    // FOUR SCALAR LOADS, NO VECTOR CODE: C3[T>>14] + C2[T>>10] + C1[T>>6] + bits
    u32 w = T >> 6;
    u32 s = (u32)C3[T >> 14] + (u32)C2[T >> 10] + (u32)C1[w];
    return s + (u32)__builtin_popcountll(_bzhi_u64(ZB[w], T & 63));
  }
  u32 k4 = T >> 18, k3 = (T >> 14) & 15, k2 = (T >> 10) & 15, k1 = (T >> 6) & 15, rem = T & 63;
  __m256i acc = _mm256_setzero_si256();
  if (LV >= 4) acc = _mm256_and_si256(_mm256_loadu_si256((const __m256i *)ZW4),
      _mm256_cmpgt_epi32(_mm256_set1_epi32((int)k4), _mm256_setr_epi32(0,1,2,3,4,5,6,7)));
  acc = _mm256_add_epi32(acc, _mm256_madd_epi16(_mm256_and_si256(
        _mm256_loadu_si256((const __m256i *)(ZW3 + (k4 << 4))),
        _mm256_cmpgt_epi16(_mm256_set1_epi16((short)k3), mkI16())), mkOne16()));
  acc = _mm256_add_epi32(acc, _mm256_madd_epi16(_mm256_and_si256(
        _mm256_loadu_si256((const __m256i *)(ZW2 + ((T >> 14) << 4))),
        _mm256_cmpgt_epi16(_mm256_set1_epi16((short)k2), mkI16())), mkOne16()));
  __m128i s8 = _mm_sad_epu8(_mm_and_si128(
        _mm_loadu_si128((const __m128i *)(ZW1 + ((T >> 10) << 4))),
        _mm_cmpgt_epi8(_mm_set1_epi8((char)k1), mkI8())), _mm_setzero_si128());
  u32 s = hsum256(acc) + (u32)_mm_cvtsi128_si32(s8) + (u32)(_mm_extract_epi16(s8, 4) & 0xFFFF);
  s += (u32)__builtin_popcountll(_bzhi_u64(ZB[T >> 6], rem));
  return s;
}

#ifndef SIMD_LIM
#define SIMD_LIM 128
#endif

// count records in [l,i) whose R < T  (4 records per AVX iteration)
static inline u32 count_lt(const u64 *S, int l, int i, u32 T) {
  u32 c = 0;
  int k = l;
  const __m256i m20 = _mm256_set1_epi64x(0xFFFFF);
  for (; k + 2 <= i; k += 2) {          // two records = 4 u64 lanes
    __m256i v = _mm256_loadu_si256((const __m256i *)(S + 2 * k));   // {w0,w1,w0,w1}
    __m256i r = _mm256_and_si256(_mm256_srli_epi64(v, 20), m20);
    __m256i cm = _mm256_cmpgt_epi64(_mm256_set1_epi64x((long long)T), r);
    c += (u32)__builtin_popcount((u32)_mm256_movemask_pd(_mm256_castsi256_pd(cm)) & 0xAu);
  }
  for (; k < i; k++) if (W_R(S[2 * k + 1]) < T) c++;
  return c;
}

// fused y-merge + cross count (no x-ties: every left x < every right x)
template <int LV> static void node_fused(int l, int m, int r, int src, int dst) {
  u64 *S = RC[src];
  u64 *D = RC[dst];
  int a = l, b = m, t = l;
  if (a < m && b < r) {
    u64 w0a = S[2 * a], w1a = S[2 * a + 1];
    u64 w0b = S[2 * b], w1b = S[2 * b + 1];
    for (;;) {
      if ((w0b >> 40) <= (w0a >> 40)) {           // right first on equal y (strict)
        w0b += zquery<LV>((u32)(w1b >> 40));
        D[2 * t] = w0b; D[2 * t + 1] = w1b; t++; b++;
        if (b >= r) break;
        w0b = S[2 * b]; w1b = S[2 * b + 1];
      } else {
        zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
        D[2 * t] = w0a; D[2 * t + 1] = w1a; t++; a++;
        if (a >= m) break;
        w0a = S[2 * a]; w1a = S[2 * a + 1];
      }
    }
  }
  int aIns = a;
  while (b < r) {
    u64 w0b = S[2 * b], w1b = S[2 * b + 1];
    w0b += zquery<LV>((u32)(w1b >> 40));
    D[2 * t] = w0b; D[2 * t + 1] = w1b; b++; t++;
  }
  while (a < m) { D[2 * t] = S[2 * a]; D[2 * t + 1] = S[2 * a + 1]; a++; t++; }
  // full zclear ~= 497 vector stores + 4 memset calls; touched-clear ~= 3 stores per insert.
  if (aIns - l >= 128) zclear<LV>();
  else if (r - l >= ZCTHR) zclear_touched<LV>(l, aIns, S);
  else for (int k = l; k < aIns; k++) zsub<LV>(W_R(S[2 * k + 1]));
}

// plain branchless y-merge (used for single-group nodes)
static void merge_run(int l, int m, int r, int src, int dst) {
  u64 *S = RC[src];
  u64 *D = RC[dst];
  int a = l, b = m, t = l;
  while (a < m && b < r) {
    int c = ((S[2 * a] >> 40) <= (S[2 * b] >> 40));
    int s = c ? a : b;
    D[2 * t] = S[2 * s]; D[2 * t + 1] = S[2 * s + 1];
    a += c; b += 1 - c; t++;
  }
  while (a < m) { D[2 * t] = S[2 * a]; D[2 * t + 1] = S[2 * a + 1]; a++; t++; }
  while (b < r) { D[2 * t] = S[2 * b]; D[2 * t + 1] = S[2 * b + 1]; b++; t++; }
}

// tie fallback: queries p with x==g (pass 2) / x!=g (pass 1), inserts q with x<g (pass 2)
template <int LV> static void cross_filter(int l, int m, int r, int src, u32 g, int pass) {
  u64 *S = RC[src];
  int i = l;
  if (pass == 1) {
    for (int j = m; j < r; j++) {
      if (W_X(S[2 * j + 1]) == g) continue;
      u32 yj = (u32)(S[2 * j] >> 40);
      while (i < m && (u32)(S[2 * i] >> 40) < yj) { zadd<LV>(W_R(S[2 * i + 1])); i++; }
      u32 c = zquery<LV>(W_T(S[2 * j + 1]));
      if (c) S[2 * j] += c;
    }
    for (int k = l; k < i; k++) zsub<LV>(W_R(S[2 * k + 1]));
  } else {
    for (int j = m; j < r; j++) {
      if (W_X(S[2 * j + 1]) != g) continue;
      u32 yj = (u32)(S[2 * j] >> 40);
      while (i < m && (u32)(S[2 * i] >> 40) < yj) {
        if (W_X(S[2 * i + 1]) < g) zadd<LV>(W_R(S[2 * i + 1]));
        i++;
      }
      u32 c = zquery<LV>(W_T(S[2 * j + 1]));
      if (c) S[2 * j] += c;
    }
    for (int k = l; k < i; k++) if (W_X(S[2 * k + 1]) < g) zsub<LV>(W_R(S[2 * k + 1]));
  }
}

#ifndef LEAF_N
#define LEAF_N 8
#endif
// base case: count all internal dominance pairs of a small x-group-aligned range
// directly, then insertion-sort the range by y.  No counter, no recursion.
#define LSCR 512                    // >= any LF; the leaf is processed entirely inside one call
static u32 lex[LSCR + 16], ley[LSCR + 16], ler[LSCR + 16];
static u64 lkey[LSCR + 16], ltmp[2 * (LSCR + 16)];
static u32 lk[64] __attribute__((aligned(32)));
// ---- generated AVX2 bitonic sort of 64 u32 keys (keys in r[0..7]) ----
static inline void bs64(__m256i *r) {
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
  { __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[2]=Hi; }
  { __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
  { __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
  { __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
  { __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
  { __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[4]=Hi; }
  { __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[5]=Hi; }
  { __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
  { __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
  { __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[4]=Hi; }
  { __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
  { __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
  { __m256i A=r[0], B=r[4]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[4]=Hi; }
  { __m256i A=r[1], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[5]=Hi; }
  { __m256i A=r[2], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[6]=Hi; }
  { __m256i A=r[3], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[7]=Hi; }
  { __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
  { __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
  { __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[6]=Hi; }
  { __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[7]=Hi; }
  { __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
  { __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
  { __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
  { __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[7]=Hi; }
  { __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
  { __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
  { __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
}

static int cdq_leaf(int l, int r, int in) {
  u64 *S = RC[in];
  const int sn = r - l;
  for (int k = 0; k < sn; k++) {          // compact u32 lanes in x-order (leaf is x-sorted)
    u64 w0 = S[2 * (l + k)], w1 = S[2 * (l + k) + 1];
    lex[k] = (u32)(w1 & 0xFFFFFu);
    ley[k] = (u32)(w0 >> 40);
    ler[k] = (u32)((w1 >> 20) & 0xFFFFFu);
  }
  for (int j = l + 1; j < r; j++) {
    const int jl = j - l;
    const u32 xj = W_X(S[2 * j + 1]), yj = (u32)(S[2 * j] >> 40), tj = W_T(S[2 * j + 1]);
    const __m256i mxj = _mm256_set1_epi32((int)xj);
    const __m256i myj = _mm256_set1_epi32((int)yj);
    const __m256i mtj = _mm256_set1_epi32((int)tj);
    __m256i vacc = _mm256_setzero_si256();
    int k = 0;
    for (; k + 8 <= jl; k += 8) {         // all values < 2^20, so signed cmps are exact
      __m256i c = _mm256_and_si256(_mm256_cmpgt_epi32(mxj, _mm256_loadu_si256((const __m256i *)(lex + k))),
                  _mm256_and_si256(_mm256_cmpgt_epi32(myj, _mm256_loadu_si256((const __m256i *)(ley + k))),
                                   _mm256_cmpgt_epi32(mtj, _mm256_loadu_si256((const __m256i *)(ler + k)))));
      vacc = _mm256_sub_epi32(vacc, c);
    }
    {   // tail lanes: masked SIMD compare instead of a scalar loop
      __m256i c = _mm256_and_si256(_mm256_cmpgt_epi32(mxj, _mm256_loadu_si256((const __m256i *)(lex + k))),
                  _mm256_and_si256(_mm256_cmpgt_epi32(myj, _mm256_loadu_si256((const __m256i *)(ley + k))),
                                   _mm256_cmpgt_epi32(mtj, _mm256_loadu_si256((const __m256i *)(ler + k)))));
      __m256i m = _mm256_cmpgt_epi32(_mm256_set1_epi32(jl-k), _mm256_load_si256((const __m256i *)IDX8));
      vacc = _mm256_sub_epi32(vacc, _mm256_and_si256(c, m));
    }
    S[2 * j] += hsum256(vacc);
  }
  {                                     // y-sort: AVX2 bitonic sort of packed u32 keys, then one permute
    if (sn <= 64) {
      for (int k = 0; k < sn; k++) lk[k] = (ley[k] << 6) | (u32)k;
      for (int k = sn; k < 64; k++) lk[k] = 0xFFFFFFFFu;
      {
        __m256i r[8];
        for (int q = 0; q < 8; q++) r[q] = _mm256_load_si256((const __m256i *)(lk + 8 * q));
        bs64(r);
        for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(lk + 8 * q), r[q]);
      }
      for (int k = 0; k < sn; k++) {
        const int sr = (int)(lk[k] & 63u);
        ltmp[2 * k] = S[2 * (l + sr)]; ltmp[2 * k + 1] = S[2 * (l + sr) + 1];
      }
    } else {
      for (int k = 0; k < sn; k++) lkey[k] = ((u64)ley[k] << 20) | (u64)(u32)k;
      for (int i = 1; i < sn; i++) {
        u64 kv = lkey[i];
        int k = i;
        while (k > 0 && lkey[k - 1] > kv) { lkey[k] = lkey[k - 1]; k--; }
        lkey[k] = kv;
      }
      for (int k = 0; k < sn; k++) {
        const int sr = (int)(u32)(lkey[k] & 0xFFFFFu);
        ltmp[2 * k] = S[2 * (l + sr)]; ltmp[2 * k + 1] = S[2 * (l + sr) + 1];
      }
    }
    for (int k = 0; k < sn; k++) { S[2 * (l + k)] = ltmp[2 * k]; S[2 * (l + k) + 1] = ltmp[2 * k + 1]; }
  }
  return in;
}

// returns the buffer holding the y-sorted range [l,r)
template <int LV, int LF> static int cdq(int l, int r, int in) {
  int s = r - l;
  if (s <= 1) return in;
  if (s <= LF) return cdq_leaf(l, r, in);
  int m = (l + r) >> 1;
  int mode = 3;
  const u64 *SI = RC[in];
  if (__builtin_expect(W_X(SI[2 * m - 1]) != W_X(SI[2 * m + 1]), 1)) mode = 0;
  else {
    u32 g = W_X(SI[2 * m + 1]);
    int a = m - 1; while (a > l && W_X(SI[2 * a - 1]) == W_X(SI[2 * a + 1])) a--;
    int b = m;     while (b < r && W_X(SI[2 * b - 1]) == W_X(SI[2 * b + 1])) b++;
    if (a == l && b == r) mode = 2;
    else {
      int lim = s >> 2;
      int ca = -1, cb = -1;
      if (a > l && a - l >= lim && r - a >= lim) ca = a;
      if (b < r && b - l >= lim && r - b >= lim) cb = b;
      if (ca >= 0 && (cb < 0 || m - ca <= cb - m)) { m = ca; mode = 1; }
      else if (cb >= 0) { m = cb; mode = 1; }
    }
  }
  int b1 = cdq<LV, LF>(l, m, in);
  int b2 = cdq<LV, LF>(m, r, in);
  if (b1 != b2) {
    memcpy(RC[b1] + 2 * m, RC[b2] + 2 * m, (size_t)(r - m) * 16);
    b2 = b1;
  }
  if (mode == 0 || mode == 1) {
    int out = 1 - b1;
    node_fused<LV>(l, m, r, b1, out);
    return out;
  }
  if (mode == 2) {
    int out = 1 - b1;
    merge_run(l, m, r, b1, out);
    return out;
  }
  // mode 3: x-tie spans the midpoint, no balanced group boundary: filtered passes
  {
    const u64 *S = RC[b1];
    u32 g = 0;
    for (int k = l; k < m; k++) { u32 xv = W_X(S[2 * k + 1]); if (xv > g) g = xv; }
    cross_filter<LV>(l, m, r, b1, g, 1);
    cross_filter<LV>(l, m, r, b1, g, 2);
  }
  int out = 1 - b1;
  merge_run(l, m, r, b1, out);
  return out;
}

void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
  if (n <= 1) { if (n == 1) out[0] = 0; return; }
  g_nz = n;

  // ---- FUSED BUILD: histograms, then ONE scatter pass (no P0/P1 arrays) ----
  memset(H64, 0, (size_t)(n + 1) * 8);
  memset(CNT, 0, (size_t)(n + 1) * 4);
  for (int i = 0; i < n; i++) {
    if (i + 12 < n) {
      __builtin_prefetch(&H64[z[i + 12]]);
      __builtin_prefetch(&CNT[x[i + 12]]);
    }
    H64[z[i]]++;
    CNT[x[i]]++;
  }
  {
    u32 acc = 0;
    for (int v = 0; v <= n; v++) { u32 c = (u32)(H64[v] & 0xFFFFFu); H64[v] = (u64)acc << 20; acc += c; }
  }
  {
    u32 acc = 0;
    int v = 0;
    for (; v + 8 <= n + 1; v += 8) {
      __m256i x = _mm256_loadu_si256((const __m256i *)(CNT + v));
      __m256i p = _mm256_add_epi32(x, _mm256_slli_si256(x, 4));
      p = _mm256_add_epi32(p, _mm256_slli_si256(p, 8));
      __m128i lo = _mm256_castsi256_si128(p);
      __m128i hi = _mm256_extracti128_si256(p, 1);
      hi = _mm_add_epi32(hi, _mm_shuffle_epi32(lo, 0xFF));
      __m256i pi = _mm256_inserti128_si256(_mm256_castsi128_si256(lo), hi, 1);
      __m256i ex = _mm256_add_epi32(_mm256_sub_epi32(pi, x), _mm256_set1_epi32((int)acc));
      _mm256_storeu_si256((__m256i *)(CNT + v), ex);
      acc += (u32)_mm_extract_epi32(hi, 3);
    }
    for (; v <= n; v++) { u32 c = CNT[v]; CNT[v] = acc; acc += c; }
  }
  {
    u64 *D = RC[0];
    for (int i = 0; i < n; i++) {
      u32 zv = z[i];
      u64 h = H64[zv];
      u32 T = (u32)(h >> 20);
      u32 R = T + (u32)(h & 0xFFFFFu);
      H64[zv] = h + 1;
      u32 xv = x[i];
      if (i + 8 < n) __builtin_prefetch(&D[2 * CNT[x[i + 8]]]);
      u32 t = CNT[xv]++;
      D[2 * t] = ((u64)y[i] << 40) | ((u64)i << 20);
      D[2 * t + 1] = ((u64)T << 40) | ((u64)R << 20) | (u64)xv;
    }
  }
  // ---- tie bits over x-order positions ----
  // ---- CDQ ----
  // (ENGINE, SIZE)-dependent: measured optima are LF=16 at n=1e5 and LF=24 at n=1e6.
  int bb = (n <= 262144) ? cdq<3, 64>(0, n, 0) : cdq<4, 64>(0, n, 0);
  {
    const u64 *D = RC[bb];
    for (int p = 0; p < n; p++) {
      if (p + 32 < n) __builtin_prefetch(&out[W_ORIG(D[2 * (p + 32)])]);
      out[W_ORIG(D[2 * p])] = W_A(D[2 * p]);
    }
  }
}

评测结果