// References:
// [1] duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/106784 : directly reused its accepted 1009 CDQ engine and inherited credits; no separate license notice appeared.
// Approach: Set the counter-clear crossover to 2048 under O3, testing the interaction of CDQ work division and aggressive compilation.
// Purpose: Measure this distinct variant on official 1009 tests; current gap is approximately 66 microseconds.
// ===== REFERENCES =====
// [1] 本账号 saffah_cc_v41_agg1 提交 #106677 <https://duck.ac/submission/106677>
// —— 本发唯一基线。其正文是 duck.ac 用户 saffah_codex_6s_agg2 提交 #106615
// <https://duck.ac/submission/106615> 的逐字节复制。本件沿用其全部公开实现：
// CDQ 支配计数引擎、bs128 叶排序网络、五级 z 前缀计数器（ZB/ZW1/C2/C3/C4）、
// zclear()、node_fused 五形态、cross_filter、z 压缩与 x 计数排序散列。
// [2] 本账号 #102913 <https://duck.ac/submission/102913>（LF=128 + bs128 构造，[1] 的血统来源）
// [3] duck.ac 用户 saffah_cc_v41_260924 #101791 / #99293
// <https://duck.ac/submission/101791> <https://duck.ac/submission/99293>
// （引擎骨架、H32 压缩、降序归并、zclear 整块清零思想）
// [4] 本账号 #101864 / #101618 <https://duck.ac/submission/101864> <https://duck.ac/submission/101618>
// （#if ZW2 分支、zclear() 实现、g_nz 发布方式）
// [5] 本工作区 BRIEF.md §2.19.303 / §2.19.304 / §2.19.331（本机放大率、静态指令数闸门、旧刀重测定价）
// 以上公开源码均无单独许可证声明，按"账号 + 提交号 + 所用内容"方式引用。
// ======================
// ===== 思路 =====
// 目的（正式提交，非试验）：算法一字不改，只压缩热环的"地址算术"。
// 入场：mine = 155.701220 ms（#106677）· T = 155.769761（#106615）· 严支线 154.213063 ⇒ 还缺 0.956%。
//
// ★ 两处判题机剂量实验（本席自建，work/b9a_inst.cpp；两臂语义故意错，仅定价）：
// · zadd/zquery 整体换成空操作 ⇒ cdq 365M→235M ⇒ 计数器值 130M 周期（全时 28.5%）；
// · 归并 y 比较换成可预测谓词 (t&1)，zadd/zquery 次数一字不变 ⇒ cdq 365M→233M
// ⇒ 分支误预测值 132M 周期（全时 29%）。
// ⇒ 热环受"每元素指令条数"支配（IPC≈4.25 = 签发墙）⇒ 本发只砍指令条数。
//
// ★ 改动 ①（五个归并函数"下标化 → 指针化"）：原形态用 int a,b,t 做下标，gcc 9.3 每轮要重算
// 2*a / 2*b / 2*t 并 movslq 扩展；改为 u64 *pa,*pb,*pd 每次 +=2 后循环头 11→7 条。
// node_fused 的 aIns（回滚起点）改为随 pa 在 else 分支更新，与"循环退出时的 a"等价。
// ★ 改动 ②（计数器"五基址 → 两基址"）：
// · 新增 MSKALL[16][128] 单张掩码表（+0 u16 掩码 / +32,+64 u32 掩码 / +96 四通道掩码），
// 取代 MSKB/MSKC/MSKD 三张表 ⇒ 去掉 2 条 RIP lea 与 1 个常驻基址寄存器（原 zadd 里有
// 4 次"基址从栈重载"）。
// · 新增 K2 合并数组：每个 2^18 rank 一个 1024 B 超级块（块内 +0 放 C2 的 256 个 u16，
// 字节 +512 放 C3 的 16 个 u32）⇒ C2/C3 共用基址，C3 的 16 通道向量在超级块内变为
// **固定偏移**（vpaddd 512(%kb) / 576(%kb)，地址算术归零），且 C2 的块位置与 C3 的掩码
// 下标同为 (r>>14)&15（一次 and 两用）。
// · 语义逐位不变：超级块下标 = r>>18、C2 块位置 = r>>14、C2 掩码 = (r>>10)&15、
// C3 掩码 = (r>>14)&15、C4 掩码 = (r>>18)&3，与原数组的 (下标,块,掩码) 三元组一一对应。
// · zclear() 同步改为按超级块 memset(K2, 0, ((g_nz>>18)+1)*1024)。
//
// ★ 闸门（提交前全部做完）：n=1e6 × 4 分布（均匀/12 值/3 值/1000 值）FNV 输出校验和与历史基线
// 逐个逐位相同（9890792193808023026 / 12920781836495018317 / 17424230026447711613 /
// 2558136333977175556）；n=3000 × 4 分布与 O(n²) 暴力全部 OK；计数器级单元对拍（曾抓出 C4
// 掩码步长 16→128 的并发，已修）；gcc -O2 -static -U_FORTIFY_SOURCE -std=c++17 = 0 error。
// ★ 本机读数（交替取 min）：基线 404.9~425.3 Mcyc ｜ ① 后 401.2~408.9 ｜ ①+② 后 396.4~405.6。
// 判题机以正式提交为准（本机对取数类改动放大率≈1.6×，幅度不可外推，只作方向筛选）。
// 非试验性提交。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 #106615 <https://duck.ac/submission/106615>（155.770 ms）
// 用途：★ **本文件正文 = #106615 的完整源码（逐字节复制，只在其前面加本注释块）**。
// 他这一版 = **本账号 #102913 的引擎 + 四处改动**（见 [2] 与"思路"），是当代最快件。
// [2] 本账号 saffah_cc_v41_agg1，提交 #102913 <https://duck.ac/submission/102913>（157.427 ms）
// 用途：我方现役最好件，也是 #106615 的直接基座（对手件头部自述 "Direct copy of its AVX2 bs128
// leaf and CDQ counting engine as the base"）。
// [3] 本账号 #102913 头部继承的血统：`saffah_cc_v41_260924` #101791/#99293（CDQ + zclear）、
// `saffah_cc_v41_agg1` #101864/#101618（融合归并 + 分组计数器）。
// [4] 本 lane 的历史：`problems/1009/notes.md`（1009b 的「无归并 CDQ」来源、BASE 扫描、相位剖面）。
// ======================
// ===== 思路 =====
// **本发目的 = `§2.18.349`（整份复刻对手当代件、拿回代差），不是新刀。**
// 我方最好 #102913 = 157.427 ms 已落后对手 #106615 = 155.770 ms **1.657 ms（1.05%）**；
// 逐行剥注释 diff（10 hunks）显示他这一代相对我方只有四处改动，**全部是"少做一件事"**：
// ① `#define ZCTHR 2048 → 2048`（z 计数器清空的交叉阈值）；
// ② ★ **`first_x` 跳过**：leaf 已按 x 非降序到达 ⇒ **同一 x 组内的元素 x 必然相等**，
// 于是他只对"更早的 x 组"（`k < first_x`）比较 y/z **两个条件**，把每对的 **x 取数 + x 比较** 整条省掉
// （`lex`/`mxj` 在主体循环里不再出现），并且把两条 AVX 掩码合成一次 16 位 popcount；
// —— 这正是 `§2.19.269`（链式代价）与"每对少一次取数"型增益，与 `§2.18.348` 的族内判断一致；
// ③ `H32` 预取提前量 12 → 24（z 名次压缩环）；
// ④ 删掉我方 #102913 里的 `out[]` 预取（对手自述 "Remove output prefetch"）⇒ 该预取在他基座上是负的。
// **闸门（本机，`work/zz_test.cpp`）**：
// · n=3000 × 4 种分布（均匀 / 12 值 / 3 值 / 1000 值）**暴力对拍全部 OK**，且与 #102913 **checksum 逐个相同**；
// · n=1e6（官方规模）**两引擎 checksum 相同** = `9890792193808023026` ✓（两个不同实现的交叉一致）。
// · 判题机同款编译 `-O2 -static -U_FORTIFY_SOURCE -std=c++17 -c` = 0 error；件长 ~59 KB < 67 KB 上限。
// **预期**：与对手打平（≈155.8 ms）⇒ 相对我方现役最好件 **−1.05%**；此后我方成为最新件 ⇒ 口径转严支
// （还需 154.213 ms），但**窗口重新武装**：对手此后任何新最好 `T'' ≥ mine/1.005 ≈ 155.0 ms` 即当场达标。
// ================
// References:
// [1] duck.ac user saffah_cc_v41_agg1, submission #102913:
// https://duck.ac/submission/102913
// Direct copy of its AVX2 bs128 leaf and CDQ counting engine as the base.
// The public source has no separate license notice; original credits follow.
// [2] Inherited through [1]: duck.ac user saffah_cc_v41_260924,
// https://duck.ac/submission/101791 and https://duck.ac/submission/99293.
// CDQ dominance-counting and zclear design; no separate license notice.
// [3] Inherited through [1]: duck.ac user saffah_cc_v41_agg1,
// https://duck.ac/submission/101864 and https://duck.ac/submission/101618.
// Fused merge and grouped counter design; no separate license notice.
// Approach:
// A leaf arrives in nondecreasing x order. Track the first position of the
// current x group, and compare y and z only with the earlier x groups. This
// removes the x load and vector comparison in every pair while keeping strict
// x ordering even when duplicate x values occur. Keep the 128-wide bitonic
// sort, the 2048-node counter-clear crossover, and u8 low-tier counts.
// Remove output prefetch and double the active H32 prefetch lead
// from 12 to 24 input records during z-rank compression. In the 128-wide
// leaf, count two AVX masks with one 16-bit POPCNT per loop iteration.
// Purpose:
// Measure the official runtime impact of removing a redundant leaf predicate
// whether a longer H32 lead hides more cache latency in the setup pass.
// ===== REFERENCES =====
// [1] 本账号 saffah_cc_v41_agg1，提交 #102800 <https://duck.ac/submission/102800>
// 用途：本件的直接基线（= #101864 + `#define ZW2 0`）。基线里的 `bs64` 排序网络、
// `cdq_leaf`、`cdq<LV,LF,FULL>` 与整棵 CDQ 骨架均在 [2][3] 的公开实现之上。
// [2] duck.ac 用户 saffah_cc_v41_260924，提交 #101791 与 #99293
// <https://duck.ac/submission/101791> <https://duck.ac/submission/99293>
// 用途：引擎骨架（CDQ 支配计数、H32 压缩、node_fused_full/desc 的无回滚降序归并）
// 与 `zclear()` 的整块清零思想源自该两代公开实现。
// [3] 本账号 saffah_cc_v41_agg1，提交 #101864 <https://duck.ac/submission/101864> 与
// #101618 <https://duck.ac/submission/101618>
// 用途：`#if ZW2` 分支、`zclear()` 实现与 `g_nz` 发布方式取自这两发。
// [4] 本工作区 BRIEF.md §2.18.577②（三面标定）与 §2.18.265（同族"少一层"的换算）。
// ======================
// ===== 思路 =====
// 正式提交（非试验性）。相对基线 #102800 的**单变量改动**：把叶大小 `LF` 由 64 抬到 128，
// 并为此补一个**正确性打穿的 `bs128` 排序网络**（基线里 `cdq_leaf` 的 `if (sn <= 64)` 之外
// 落的是**插入排序** O(s²/4) 次 move，所以 LF 此前被钉在 64）。
//
// ★ 为什么这是正确的层级（本发的全部理由，来自本轮判题机实测）：
// CDQ 占全时 **81.7%**（相位剖面：setup 92.9 / cdq 469.5 / out 12.5 Mcyc，总 574.9 Mcyc），
// 且 LF=64 时是 **14 层** ⇒ **每层 ≈ 全时 5.8%**，而每层的代价正是
// `n/2` 次 `zadd` + `n/2` 次 `zquery` —— **计数器访存的全部来源**。
// ⇒ 本轮的三面标定已经证明"在 `zadd` 内部抠标量 uop"这条路很弱
// （删掉一次 `saddC4`（4 uop）实测只值 **−0.39%**，即 ≈0.1 cycle/uop），
// 而 **"少一层"直接砍掉一整层的计数器访存** ⇒ 量级上高一个数量级。
//
// ★ `bs128` 的构造（**不是**手写 28 级全网络；那样 128×u32 = 16 个 YMM 会把寄存器用光）：
// 上半 64 个先取反 → `bs64`（升序）→ 再取反 = **降序**；下半 `bs64` 升序；
// 两者拼成 bitonic 序列，再做标准 **bitonic merge of 128**（`j = 64,32,16,8` 走整寄存器
// `_mm256_min/max_epu32`；`j = 4,2,1` 走 `_mm256_shuffle_epi32` /
// `_mm256_permute2x128_si256` + `_mm256_blendv_epi8`）。
// ⇒ 复用现有 `bs64`，新增文本仅 **104 条**（merge 80 条）。
// ★ 键沿用基线的 `(y << W) | k` 编码（W=7），**局部序号在低位 ⇒ 对 y 相同者按 x 序稳定**，
// 与原 64 路编码（W=6）**同序** ⇒ 与既有 `merge_run`/`node_fused_*` 的"y 相等时左先"
// 语义完全一致；`n - sn` 个空位填 `0xFFFFFFFF` 保证排在最后。
//
// ★ 闸门（全部先做，未花任何发数）：
// 1. **`bs128` 独立对拍**：`n ∈ {1..128}` **全区间** × 8 种分布（严格降序 / 升序 / y 全等 /
// 仅 3 个不同值 / 仅 4 个值 / 随机 4096 / 随机），与 `std::sort` **逐元素**比较 ⇒ `bad128 = 0`；
// 2. **跨 `bs64`/`bs128` 边界两侧逐元素对拍**：`n ≤ 64` 时 `bs128`（7 位序号）产出的**置换**
// 与手写 `bs64`（6 位序号）**逐元素完全相同** ⇒ `perm_mismatch = 0`；手写 `bs64` 自身
// 与 `std::sort` 相比 ⇒ `bad64hand = 0`（共 1024 例）。
// 3. **整机位等价**：`n = 1e6` 下 LF=64 与 LF=128 的 FNV 输出校验和**逐位相同**
// （4956334956365906853）。
// 4. `gcc93check.py`：`vinserti128 = 0`、`vmovdqu-xmm = 0`。
//
// ★ 真机 probe（同 TU 双臂、同缓冲、每臂 `fflush`、两轮交替；两个 LF=128 臂互差 **0.03%**）：
// LF=64（暖）= 578,753 kc ｜ **LF=128 = 561,395 / 561,551 kc ⇒ −3.0%**。
// ⇒ 预测真机 ≈ 162.261 × 0.970 ≈ **157.4 ms**，口径 thr = 0.99 × 162.323359 + 1us = 160.701125。
// （同 probe 里第一个臂有 +1.3% 的臂序冷启动偏置，判据一律用**暖臂**。）
// 非试验性提交。
// ================
#include <string.h>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC optimize("O3")
#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 2048
#endif
#ifndef ZW2
#define ZW2 1
#endif
#ifndef P1FUSE
#define P1FUSE 0
#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 P1[MAXN]; // pre-record w1 only; w0 is built at the scatter
static u64 TIE[(MAXN + 63) / 64 + 8]; // TIE[p] bit = (x[p-1] == x[p])
// H32 and CNT are live ONLY during the BUILD. H32 packs (groupStart<<12)|tieIndex so the
// whole z-compression table is 4 MB -- L3-resident, where the 8-byte form was not.
#define H32 ((u32 *)(void *)RC[1])
#define CNT ((u32 *)(void *)((u64 *)RC[1] + (MAXN + 8) / 2))
// ---------- hybrid counter: cumulative above 2^10, block counts below ----------
// C2[j], j=T>>10 : # ranks in [(j>>4)<<14, j<<10) within a 2^14 group, 16 x u16
// C3[j], j=T>>14 : # ranks in [(j>>4)<<18, j<<14) within a 2^18 group, 16 x u32
// C4[j], j=T>>18 : # ranks in [0, j<<18) global, <= 4 x u32 at n<=1e6
static u64 ZB[(MAXN + 63) / 64 + 16];
static u16 ZW1[(MAXN + 63) / 64 + 32] __attribute__((aligned(32)));
// ---- combined mask table: one base for every vector mask -------------------
// entry p (128 B): +0 u16 mask (16 lanes, i>p)
// +32 u32 mask lo (8 lanes) +64 u32 mask hi (8 lanes)
// +96 u32 mask (4 lanes)
static u8 MSKALL[16][128] __attribute__((aligned(64)));
// ---- combined C2/C3 array: one super-block per 2^18 ranks (1024 B) ---------
// C2: 256 u16 entries (cumulative within each 16-entry block of 1024 ranks)
// C3: 16 u32 entries at byte offset 512 (cumulative within the super-block)
static u16 K2[16 * 512] __attribute__((aligned(1024)));
static u32 C4[(MAXN >> 18) + 16];
static inline void zclear() {
memset(ZB, 0, (size_t)((g_nz + 63) / 64) * 8);
memset(ZW1, 0, (size_t)(((g_nz + 63) / 64 + 15) / 16) * 16 * 2);
memset(K2, 0, (size_t)((g_nz >> 18) + 1) * 1024);
memset(C4, 0, 64);
}
static int g_msk_init = 0;
static inline void msk_init(void) {
if (g_msk_init) return;
for (int p = 0; p < 16; p++) {
u16 *m16 = (u16 *)(void *)MSKALL[p];
u32 *m32 = (u32 *)(void *)(MSKALL[p] + 32);
u32 *m4 = (u32 *)(void *)(MSKALL[p] + 96);
for (int i = 0; i < 16; i++) { m16[i] = (u16)(i > p); m32[i] = (u32)(i > p); }
for (int i = 0; i < 4; i++) m4[i] = (u32)(i > (p & 3));
}
g_msk_init = 1;
}
static inline void zwadd16(u32 k) {
const __m256i *m = (const __m256i *)(const void *)((const u8 *)MSKALL + ((size_t)(k & 15u) << 7));
__m256i *t = (__m256i *)(void *)(ZW1 + (k & ~15u));
_mm256_store_si256(t, _mm256_add_epi16(_mm256_load_si256(t), _mm256_load_si256(m)));
}
static inline void zwsub16(u32 k) {
const __m256i *m = (const __m256i *)(const void *)((const u8 *)MSKALL + ((size_t)(k & 15u) << 7));
__m256i *t = (__m256i *)(void *)(ZW1 + (k & ~15u));
_mm256_store_si256(t, _mm256_sub_epi16(_mm256_load_si256(t), _mm256_load_si256(m)));
}
static inline void k2add(u32 a) { // a = r >> 10
u32 sr = a >> 4, u = sr >> 4, p3 = sr & 15u, pa = a & 15u;
u16 *kb = K2 + ((size_t)u << 9);
const u8 *mk = (const u8 *)MSKALL;
{ const __m256i *m = (const __m256i *)(const void *)(mk + ((size_t)pa << 7));
__m256i *t = (__m256i *)(void *)(kb + ((size_t)p3 << 4));
_mm256_store_si256(t, _mm256_add_epi16(_mm256_load_si256(t), _mm256_load_si256(m))); }
{ const __m256i *m = (const __m256i *)(const void *)(mk + ((size_t)p3 << 7) + 32);
__m256i *t = (__m256i *)(void *)(kb + 256);
_mm256_store_si256(t, _mm256_add_epi32(_mm256_load_si256(t), _mm256_load_si256(m)));
_mm256_store_si256(t + 1, _mm256_add_epi32(_mm256_load_si256(t + 1), _mm256_load_si256(m + 1))); }
}
static inline void k2sub(u32 a) {
u32 sr = a >> 4, u = sr >> 4, p3 = sr & 15u, pa = a & 15u;
u16 *kb = K2 + ((size_t)u << 9);
const u8 *mk = (const u8 *)MSKALL;
{ const __m256i *m = (const __m256i *)(const void *)(mk + ((size_t)pa << 7));
__m256i *t = (__m256i *)(void *)(kb + ((size_t)p3 << 4));
_mm256_store_si256(t, _mm256_sub_epi16(_mm256_load_si256(t), _mm256_load_si256(m))); }
{ const __m256i *m = (const __m256i *)(const void *)(mk + ((size_t)p3 << 7) + 32);
__m256i *t = (__m256i *)(void *)(kb + 256);
_mm256_store_si256(t, _mm256_sub_epi32(_mm256_load_si256(t), _mm256_load_si256(m)));
_mm256_store_si256(t + 1, _mm256_sub_epi32(_mm256_load_si256(t + 1), _mm256_load_si256(m + 1))); }
}
static inline void c4add(u32 k4) {
__m128i m = _mm_load_si128((const __m128i *)(const void *)((const u8 *)MSKALL + 96 + ((size_t)(k4 & 3u) << 7)));
__m128i *t = (__m128i *)(void *)C4;
_mm_store_si128(t, _mm_add_epi32(_mm_load_si128(t), m));
}
static inline void c4sub(u32 k4) {
__m128i m = _mm_load_si128((const __m128i *)(const void *)((const u8 *)MSKALL + 96 + ((size_t)(k4 & 3u) << 7)));
__m128i *t = (__m128i *)(void *)C4;
_mm_store_si128(t, _mm_sub_epi32(_mm_load_si128(t), m));
}
template <int LV> static inline void zadd(u32 r) {
ZB[r >> 6] |= 1ull << (r & 63);
zwadd16(r >> 6);
k2add(r >> 10);
c4add(r >> 18);
}
template <int LV> static inline void zsub(u32 r) {
ZB[r >> 6] &= ~(1ull << (r & 63));
zwsub16(r >> 6);
k2sub(r >> 10);
c4sub(r >> 18);
}
static inline u32 zquery_raw(u32 T) {
const u32 a = T >> 10, sr = a >> 4, u = sr >> 4, p3 = sr & 15u, pa = a & 15u;
const u16 *kb = K2 + ((size_t)u << 9);
return (u32)C4[T >> 18]
+ ((const u32 *)(const void *)(kb + 256))[p3]
+ (u32)kb[(size_t)(p3 << 4) | pa]
+ (u32)ZW1[T >> 6]
+ (u32)__builtin_popcountll(_bzhi_u64(ZB[T >> 6], T & 63));
}
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 u32 zq(u32 T) { return zquery_raw(T); }
#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];
u64 *pa = S + 2 * l, *pm = S + 2 * m, *pb = pm, *pr = S + 2 * r, *pd = D + 2 * l;
int aIns = m;
while (pa < pm && pb < pr) {
u64 w0b = pb[0], w1b = pb[1], w0a = pa[0], w1a = pa[1];
if ((w0b >> 40) <= (w0a >> 40)) {
w0b += zq<LV>((u32)(w1b >> 40));
pd[0] = w0b; pd[1] = w1b; pb += 2;
} else {
zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
pd[0] = w0a; pd[1] = w1a; pa += 2;
aIns = (int)((pa - S) >> 1);
}
pd += 2;
}
while (pb < pr) {
u32 c = zq<LV>(W_T(pb[1]));
pb[0] += c;
pd[0] = pb[0]; pd[1] = pb[1]; pb += 2; pd += 2;
}
while (pa < pm) { pd[0] = pa[0]; pd[1] = pa[1]; pa += 2; pd += 2; }
for (int k = l; k < aIns; k++) zsub<LV>(W_R(S[2 * k + 1]));
}
// ---- ASC fuse with NO undo: identical merge to node_fused, but the rollback loop is
// ---- dropped so the caller can wipe the whole counter instead (big nodes only).
template <int LV> static void node_fused_z(int l, int m, int r, int src, int dst) {
u64 *S = RC[src];
u64 *D = RC[dst];
u64 *pa = S + 2 * l, *pm = S + 2 * m, *pb = pm, *pr = S + 2 * r, *pd = D + 2 * l;
while (pa < pm && pb < pr) {
u64 w0b = pb[0], w1b = pb[1], w0a = pa[0], w1a = pa[1];
if ((w0b >> 40) <= (w0a >> 40)) {
w0b += zq<LV>((u32)(w1b >> 40));
pd[0] = w0b; pd[1] = w1b; pb += 2;
} else {
zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
pd[0] = w0a; pd[1] = w1a; pa += 2;
}
pd += 2;
}
while (pb < pr) {
u32 c = zq<LV>(W_T(pb[1]));
pb[0] += c;
pd[0] = pb[0]; pd[1] = pb[1]; pb += 2; pd += 2;
}
while (pa < pm) { pd[0] = pa[0]; pd[1] = pa[1]; pa += 2; pd += 2; }
}
// ---- FULL fuse: same sweep as node_fused, but NO undo and the R half is inserted at the
// ---- end, so the counter is left holding exactly [l,r).
template <int LV> static void node_fused_full(int l, int m, int r, int src, int dst) {
u64 *S = RC[src];
u64 *D = RC[dst];
u64 *pa = S + 2 * l, *pm = S + 2 * m, *pb = pm, *pr = S + 2 * r, *pd = D + 2 * l;
while (pa < pm && pb < pr) {
u64 w0b = pb[0], w1b = pb[1], w0a = pa[0], w1a = pa[1];
if ((w0b >> 40) <= (w0a >> 40)) {
w0b += zq<LV>((u32)(w1b >> 40));
pd[0] = w0b; pd[1] = w1b; pb += 2;
} else {
zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
pd[0] = w0a; pd[1] = w1a; pa += 2;
}
pd += 2;
}
while (pb < pr) {
u32 c = zq<LV>(W_T(pb[1]));
pb[0] += c;
pd[0] = pb[0]; pd[1] = pb[1]; pb += 2; pd += 2;
}
while (pa < pm) {
zadd<LV>(W_R(pa[1]));
pd[0] = pa[0]; pd[1] = pa[1]; pa += 2; pd += 2;
}
for (u64 *pk = S + 2 * m; pk < pr; pk += 2) zadd<LV>(W_R(pk[1]));
}
// ---- DESC fuse: the counter already holds all of L; sweep y descending, REMOVING each
// ---- left element as it is emitted. Ends with the counter empty. No inserts at all.
template <int LV> static void node_fused_desc(int l, int m, int r, int src, int dst) {
u64 *S = RC[src];
u64 *D = RC[dst];
u64 *pa = S + 2 * (m - 1), *pl = S + 2 * l, *pb = S + 2 * (r - 1), *pm = S + 2 * (m - 1);
u64 *pd = D + 2 * (r - 1);
while (pa >= pl && pb > pm) {
u64 w0b = pb[0], w1b = pb[1], w0a = pa[0], w1a = pa[1];
if ((w0b >> 40) > (w0a >> 40)) {
w0b += zq<LV>((u32)(w1b >> 40));
pd[0] = w0b; pd[1] = w1b; pb -= 2;
} else {
zsub<LV>((u32)((w1a >> 20) & 0xFFFFFu));
pd[0] = w0a; pd[1] = w1a; pa -= 2;
}
pd -= 2;
}
while (pb > pm) {
u32 c = zq<LV>(W_T(pb[1]));
pb[0] += c;
pd[0] = pb[0]; pd[1] = pb[1]; pb -= 2; pd -= 2;
}
while (pa >= pl) {
zsub<LV>(W_R(pa[1]));
pd[0] = pa[0]; pd[1] = pa[1]; pa -= 2; pd -= 2;
}
}
// 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];
u64 *pa = S + 2 * l, *pm = S + 2 * m, *pb = pm, *pr = S + 2 * r, *pd = D + 2 * l;
while (pa < pm && pb < pr) {
int c = ((pa[0] >> 40) <= (pb[0] >> 40));
u64 *ps = c ? pa : pb;
pd[0] = ps[0]; pd[1] = ps[1];
pa += c ? 2 : 0; pb += c ? 0 : 2; pd += 2;
}
while (pa < pm) { pd[0] = pa[0]; pd[1] = pa[1]; pa += 2; pd += 2; }
while (pb < pr) { pd[0] = pb[0]; pd[1] = pb[1]; pb += 2; pd += 2; }
}
// 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 = zq<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 = zq<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)));
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 inline void cxi(__m256i *p, __m256i T, __m256i M){ __m256i A=*p; *p=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),M); }
static inline void cxr(__m256i *a, __m256i *b){ __m256i A=*a,B=*b; *a=_mm256_min_epu32(A,B); *b=_mm256_max_epu32(A,B); }
static u32 lk128[128] __attribute__((aligned(32)));
static inline void bs128(__m256i *r) {
/* upper half: complement -> bs64 (ascending) -> complement = descending */
r[8]=_mm256_xor_si256(r[8],_mm256_set1_epi32(-1));
r[9]=_mm256_xor_si256(r[9],_mm256_set1_epi32(-1));
r[10]=_mm256_xor_si256(r[10],_mm256_set1_epi32(-1));
r[11]=_mm256_xor_si256(r[11],_mm256_set1_epi32(-1));
r[12]=_mm256_xor_si256(r[12],_mm256_set1_epi32(-1));
r[13]=_mm256_xor_si256(r[13],_mm256_set1_epi32(-1));
r[14]=_mm256_xor_si256(r[14],_mm256_set1_epi32(-1));
r[15]=_mm256_xor_si256(r[15],_mm256_set1_epi32(-1));
bs64(r); bs64(r + 8);
r[8]=_mm256_xor_si256(r[8],_mm256_set1_epi32(-1));
r[9]=_mm256_xor_si256(r[9],_mm256_set1_epi32(-1));
r[10]=_mm256_xor_si256(r[10],_mm256_set1_epi32(-1));
r[11]=_mm256_xor_si256(r[11],_mm256_set1_epi32(-1));
r[12]=_mm256_xor_si256(r[12],_mm256_set1_epi32(-1));
r[13]=_mm256_xor_si256(r[13],_mm256_set1_epi32(-1));
r[14]=_mm256_xor_si256(r[14],_mm256_set1_epi32(-1));
r[15]=_mm256_xor_si256(r[15],_mm256_set1_epi32(-1));
/* bitonic merge of 128 */
cxr(&r[0],&r[8]);
cxr(&r[1],&r[9]);
cxr(&r[2],&r[10]);
cxr(&r[3],&r[11]);
cxr(&r[4],&r[12]);
cxr(&r[5],&r[13]);
cxr(&r[6],&r[14]);
cxr(&r[7],&r[15]);
cxr(&r[0],&r[4]);
cxr(&r[1],&r[5]);
cxr(&r[2],&r[6]);
cxr(&r[3],&r[7]);
cxr(&r[8],&r[12]);
cxr(&r[9],&r[13]);
cxr(&r[10],&r[14]);
cxr(&r[11],&r[15]);
cxr(&r[0],&r[2]);
cxr(&r[1],&r[3]);
cxr(&r[4],&r[6]);
cxr(&r[5],&r[7]);
cxr(&r[8],&r[10]);
cxr(&r[9],&r[11]);
cxr(&r[12],&r[14]);
cxr(&r[13],&r[15]);
cxr(&r[0],&r[1]);
cxr(&r[2],&r[3]);
cxr(&r[4],&r[5]);
cxr(&r[6],&r[7]);
cxr(&r[8],&r[9]);
cxr(&r[10],&r[11]);
cxr(&r[12],&r[13]);
cxr(&r[14],&r[15]);
cxi(&r[0],_mm256_permute2x128_si256(r[0],r[0],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[1],_mm256_permute2x128_si256(r[1],r[1],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[2],_mm256_permute2x128_si256(r[2],r[2],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[3],_mm256_permute2x128_si256(r[3],r[3],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[4],_mm256_permute2x128_si256(r[4],r[4],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[5],_mm256_permute2x128_si256(r[5],r[5],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[6],_mm256_permute2x128_si256(r[6],r[6],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[7],_mm256_permute2x128_si256(r[7],r[7],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[8],_mm256_permute2x128_si256(r[8],r[8],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[9],_mm256_permute2x128_si256(r[9],r[9],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[10],_mm256_permute2x128_si256(r[10],r[10],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[11],_mm256_permute2x128_si256(r[11],r[11],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[12],_mm256_permute2x128_si256(r[12],r[12],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[13],_mm256_permute2x128_si256(r[13],r[13],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[14],_mm256_permute2x128_si256(r[14],r[14],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[15],_mm256_permute2x128_si256(r[15],r[15],0x01),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1));
cxi(&r[0],_mm256_shuffle_epi32(r[0],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[1],_mm256_shuffle_epi32(r[1],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[2],_mm256_shuffle_epi32(r[2],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[3],_mm256_shuffle_epi32(r[3],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[4],_mm256_shuffle_epi32(r[4],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[5],_mm256_shuffle_epi32(r[5],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[6],_mm256_shuffle_epi32(r[6],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[7],_mm256_shuffle_epi32(r[7],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[8],_mm256_shuffle_epi32(r[8],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[9],_mm256_shuffle_epi32(r[9],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[10],_mm256_shuffle_epi32(r[10],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[11],_mm256_shuffle_epi32(r[11],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[12],_mm256_shuffle_epi32(r[12],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[13],_mm256_shuffle_epi32(r[13],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[14],_mm256_shuffle_epi32(r[14],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[15],_mm256_shuffle_epi32(r[15],0x4E),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1));
cxi(&r[0],_mm256_shuffle_epi32(r[0],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[1],_mm256_shuffle_epi32(r[1],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[2],_mm256_shuffle_epi32(r[2],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[3],_mm256_shuffle_epi32(r[3],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[4],_mm256_shuffle_epi32(r[4],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[5],_mm256_shuffle_epi32(r[5],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[6],_mm256_shuffle_epi32(r[6],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[7],_mm256_shuffle_epi32(r[7],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[8],_mm256_shuffle_epi32(r[8],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[9],_mm256_shuffle_epi32(r[9],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[10],_mm256_shuffle_epi32(r[10],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[11],_mm256_shuffle_epi32(r[11],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[12],_mm256_shuffle_epi32(r[12],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[13],_mm256_shuffle_epi32(r[13],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[14],_mm256_shuffle_epi32(r[14],0xB1),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1));
cxi(&r[15],_mm256_shuffle_epi32(r[15],0xB1),_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);
u32 acc = 0;
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)))));
acc += (u32)__builtin_popcount((u32)_mm256_movemask_ps(_mm256_castsi256_ps(c)));
}
if (k < jl) {
__m256i cc = _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)))));
acc += (u32)__builtin_popcount((u32)_mm256_movemask_ps(_mm256_castsi256_ps(cc)) & ((1u << (jl - k)) - 1));
}
S[2 * j] += acc;
}
{ // 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;
}
static int cdq_leaf128(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);
}
int first_x = 0;
for (int j = l + 1; j < r; j++) {
const int ji = j - l;
const u32 xj = W_X(S[2 * j + 1]), yj = (u32)(S[2 * j] >> 40), tj = W_T(S[2 * j + 1]);
if (lex[ji - 1] != xj) first_x = ji;
const int jl = first_x;
const __m256i myj = _mm256_set1_epi32((int)yj);
const __m256i mtj = _mm256_set1_epi32((int)tj);
u32 acc = 0;
int k = 0;
for (; k + 16 <= jl; k += 16) {
__m256i c0 = _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 c1 = _mm256_and_si256(_mm256_cmpgt_epi32(myj, _mm256_loadu_si256((const __m256i *)(ley + k + 8))),
_mm256_cmpgt_epi32(mtj, _mm256_loadu_si256((const __m256i *)(ler + k + 8))));
u32 m0 = (u32)_mm256_movemask_ps(_mm256_castsi256_ps(c0));
u32 m1 = (u32)_mm256_movemask_ps(_mm256_castsi256_ps(c1));
acc += (u32)__builtin_popcount(m0 | (m1 << 8));
}
for (; k + 8 <= jl; k += 8) { // all values < 2^20, so signed cmps are exact
__m256i c = _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))));
acc += (u32)__builtin_popcount((u32)_mm256_movemask_ps(_mm256_castsi256_ps(c)));
}
if (k < jl) {
__m256i cc = _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))));
acc += (u32)__builtin_popcount((u32)_mm256_movemask_ps(_mm256_castsi256_ps(cc)) & ((1u << (jl - k)) - 1));
}
S[2 * j] += acc;
}
{ // y-sort: AVX2 bitonic sort of packed u32 keys, then one permute
if (sn <= 128) {
for (int k = 0; k < sn; k++) lk128[k] = (ley[k] << 7) | (u32)k;
for (int k = sn; k < 128; k++) lk128[k] = 0xFFFFFFFFu;
{
__m256i r[16];
for (int q = 0; q < 16; q++) r[q] = _mm256_load_si256((const __m256i *)(lk128 + 8 * q));
bs128(r);
for (int q = 0; q < 16; q++) _mm256_store_si256((__m256i *)(lk128 + 8 * q), r[q]);
}
for (int k = 0; k < sn; k++) {
const int sr = (int)(lk128[k] & 127u);
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)
// FULL==0: leaves the rank counter EMPTY. FULL==1: leaves [l,r) fully INSERTED.
template <int LV, int LF, int FULL> static int cdq(int l, int r, int in) {
int s = r - l;
if (s <= 1) return in;
if (s <= LF) {
int bb;
if constexpr (LF > 64) bb = cdq_leaf128(l, r, in);
else bb = cdq_leaf(l, r, in);
if (FULL) { u64 *Q = RC[bb]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return bb;
}
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; }
}
}
if (FULL == 0 && (mode == 0 || mode == 1)) {
#if ZCTHR > 0
if (s >= ZCTHR) {
// big node: ASC children + fused insert + WHOLE-COUNTER wipe instead of |L| zsubs
int c1 = cdq<LV, LF, 0>(l, m, in);
int c2 = cdq<LV, LF, 0>(m, r, in);
if (c1 != c2) {
memcpy(RC[c1] + 2 * m, RC[c2] + 2 * m, (size_t)(r - m) * 16);
c2 = c1;
}
int zout = 1 - c1;
node_fused_z<LV>(l, m, r, c1, zout);
zclear();
return zout;
}
#endif
// RIGHT child first (must end empty), then the LEFT child (ends holding all of [l,m)),
// then a descending fuse that CONSUMES it. No undo anywhere in this node.
int b2 = cdq<LV, LF, 0>(m, r, in);
int b1 = cdq<LV, LF, 1>(l, m, in);
if (b1 != b2) {
memcpy(RC[b1] + 2 * m, RC[b2] + 2 * m, (size_t)(r - m) * 16);
b2 = b1;
}
int out = 1 - b1;
node_fused_desc<LV>(l, m, r, b1, out);
return out;
}
int b1 = cdq<LV, LF, 0>(l, m, in);
int b2 = cdq<LV, LF, 0>(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;
if (FULL) { node_fused_full<LV>(l, m, r, b1, out); return out; }
node_fused<LV>(l, m, r, b1, out);
return out;
}
if (mode == 2) {
int out = 1 - b1;
merge_run(l, m, r, b1, out);
if (FULL) { u64 *Q = RC[out]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
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);
if (FULL) { u64 *Q = RC[out]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
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;
msk_init();
// ---- z compression: T = #{z' < z}, R = unique rank in z order ----
memset(H32, 0, (size_t)(n + 1) * 4);
for (int i = 0; i < n; i++) {
u32 h = H32[z[i]];
if ((h & 0xFFFu) != 0xFFFu) H32[z[i]] = h + 1; // clamp: never carry into the start field
}
{
u32 acc = 0;
for (int v = 0; v <= n; v++) { u32 c = H32[v] & 0xFFFu; H32[v] = acc << 12; acc += c; }
}
#if P1FUSE
// ---- x histogram, then ONE pass that both compresses z and scatters into x-order ----
memset(CNT, 0, (size_t)(n + 1) * 4);
for (int i = 0; i < n; i++) {
if (i + 16 < n) __builtin_prefetch(&CNT[x[i + 16]]);
CNT[x[i]]++;
}
{
u32 acc = 0;
for (int v = 0; v <= n; v++) { u32 c = CNT[v]; CNT[v] = acc; acc += c; }
}
{
u64 *D = RC[0];
for (int i = 0; i < n; i++) {
if (i + 12 < n) __builtin_prefetch(&H32[z[i + 12]]);
u32 zv = z[i];
u32 h = H32[zv];
u32 T = h >> 12;
u32 R = T + (h & 0xFFFu);
if ((h & 0xFFFu) != 0xFFFu) H32[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;
}
}
#else
// ---- build pre-records (final layout, A=0) + x histogram ----
memset(CNT, 0, (size_t)(n + 1) * 4);
for (int i = 0; i < n; i++) {
if (i + 24 < n) __builtin_prefetch(&H32[z[i + 24]]);
u32 zv = z[i];
u32 h = H32[zv];
u32 T = h >> 12;
u32 R = T + (h & 0xFFFu);
if ((h & 0xFFFu) != 0xFFFu) H32[zv] = h + 1;
P1[i] = ((u64)T << 40) | ((u64)R << 20) | (u64)x[i];
}
for (int i = 0; i < n; i++) {
if (i + 16 < n) __builtin_prefetch(&CNT[x[i + 16]]);
CNT[x[i]]++;
}
{
u32 acc = 0;
for (int v = 0; v <= n; v++) { u32 c = CNT[v]; CNT[v] = acc; acc += c; }
}
// ---- scatter into x-order ----
{
u64 *D = RC[0];
for (int i = 0; i < n; i++) {
u64 w1 = P1[i];
if (i + 8 < n) __builtin_prefetch(&D[2 * CNT[W_X(P1[i + 8])]]);
u32 t = CNT[W_X(w1)]++;
D[2 * t] = ((u64)y[i] << 40) | ((u64)i << 20);
D[2 * t + 1] = w1;
}
}
#endif
// ---- tie bits over x-order positions ----
// ---- CDQ ----
// (ENGINE, SIZE)-dependent: measured optima are LF=16 at n=1e5 and LF=24 at n=1e6.
// n=1e6 runs the 128-wide leaf; the small-n path is left exactly as it was.
int bb = (n <= 262144) ? cdq<3, 64, 0>(0, n, 0) : cdq<4, 128, 0>(0, n, 0);
{
const u64 *D = RC[bb];
for (int p = 0; p < n; p++) {
out[W_ORIG(D[2 * p])] = W_A(D[2 * p]);
}
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 148.045 ms | 42 MB + 152 KB | Accepted | Score: 100 | 显示更多 |