// ===== REFERENCES (k11c2_ 席 · 本发) =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3**（对手 / 目标 T 件），提交 **#120558**
// <https://duck.ac/submission/120558>（2026-10-02 19:19:49，判题机 292.647209 ms，Accepted）。
// 用途：本文件正文的算法/数据结构全部来自该件（叶级字节前缀计数器 CBC + 5 级计数器 +
// `PrefixCounterStorage` 共址 + `FUSE_OK` 守卫）—— 即 §2.18.349 的取回链。
// [2] 本账号 `saffah_cc_v41_agg1`，提交 **#120925** <https://duck.ac/submission/120925>
// （2026-10-02 20:2x，292.669255 ms，Accepted，本发之前我方在册最好件；= #120558 的逐字节副本）。
// 用途：**本文件正文 = #120925 的正文**（即 #120558）**逐字节**，仅 `merge_loops` 的
// 选择+游标前进段被本席的 `[k11c2-SELADV]` 内联汇编替换（见下【新思路】）。
// [3] 本账号 `saffah_cc_v41_agg1`，提交 **#108101** <https://duck.ac/submission/108101>
// （2026-09-28，295.722770 ms，Accepted；`[MRG3]` 单边界哨兵归并环 = 本文件归并环的直接祖先，
// 经 #120558 传承）。
// [4] 本工作区 `problems/1011/notes.md`（判型表：归并相 26.6~30.7% 全时、IPC 4.11 / 环内
// DCX 消融「删 14 条只买 0.6 拍」⇒ 该环由**携带链**而非发射定价 —— 本刀据此选型）。
// 许可：以上均为 duck.ac 公开提交（站点明文「你提交的代码将会被公开」），未见单独许可声明；
// 本文件按 RULES §3 逐项署名「原作者账号 + 原始提交地址 + 所用内容」。
// ======================
// ===== 新思路（本发 · [k11c2-SELADV] 归并主环「一次比较供三处消费者」）=====
// 【问题（判题同款 gcc 9.3 `-O2 -std=c++17 -S` 实证，`work/k11c2__tmp/k11c2_base.s` L13222..13262）】
// 原 C 形式 `const u32 takeA = (u32)(ea<eb); pa += takeA; pb += 1-takeA; v = takeA?ea:eb;`
// 被编成 40 条：cmpx2(setb/sbb/and/add 四条) 且 **CF 被 `andl $8,%r8d` 破坏** ⇒ gcc 不得不
// **重发同一条 `cmpq %rax,%r9`** 供 `cmovbe` 用（环内出现两条完全相同的 cmpq）。
// ★ 正是 BRIEF 模式 5「读出标志位前别放会改标志的操作」+ 模式 3「条件写 → cmov」的叠加实例。
// 【刀】把选择与游标前进交给一段内联汇编：`cmpq` 只置 CF，随后
// `sbbq tt,tt`（tt = -takeA，**不写 CF**）→ `leaq 8(pa),t1; cmovb` 与 `leaq 8(pb),t2; cmovae`
// → `cmovb ea,eb`（= v）**三个 CF 消费者顺序读取同一次比较，中间无任何写标志指令**。
// 逐步等价：CF = (ea<eb) = takeA；cmovb 在 CF=1（takeA）时 pa+=8；cmovae 在 CF=0 时 pb+=8
// （即 pb += 1-takeA）；cmovb 在 CF=1 时 eb := ea ⇒ eb = takeA?ea:eb = v；
// tt = 0 - 0 - CF = -takeA（全宽），bit0(tt) = takeA，故
// `~(((v>>42) & 1) ^ takeA) & 1` = 1 - (takeA ^ role(v)) = keep（原式）✓。
// 事件次序、`out` 流、`cross` 流、`cx` 全部不变 ⇒ 逐位等价。
// 【账】**环 40 → 36 条**；**load→游标携带链 9/8 → 6/6 级**（rdi→load4→cmp1→cmov1）。
// 前置判型：归并环 IPC 4.11（前端贴顶）**且** DCX 消融「删 14 条只买 0.6/10.4 拍」（链定价）
// ⇒ 本刀同时**减 4 条**与**缩 3 级链**，两个账同时改善，故不落入 DCX 的「只删条无效」陷阱。
// 【定价（判题机，本发唯一探针 `work/k11c2__tmp/k11c2_p1.cpp`，n=300000 k=5 同进程双臂）】
// base 1,047,982,516 vs 本发 1,030,363,370 ticks ⇒ **-1.681%**（同 harness 空对照 -0.144%
// ⇒ 臂序修正后 ≈ **-1.537%**）。本机（i5-6500）同件 -3.18%。
// 【闸门】生产 n=300000 k=5 **CK 11747190579917750320 / SUM 2815262781 逐位相同** ✓ ·
// 判题机同款 gcc 9.3 `-O2 -std=c++17` 零错零警 ✓ · 无 `main` ✓ · 零 `/tmp` ✓ ·
// 每发前现读 `/status`（Pending=0）✓
// ======================
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/120528:
* retained the accepted guarded-prefix engine and original references.
* saffah_codex_6a_agg3, https://duck.ac/submission/120178:
* reused co-locating counter levels under one register base.
* Public sources carry no separate software license notices.
* Idea: Co-locate all prefix counter levels in one aligned object so inserts
* and queries can share one address base. The cumulative leaf and its safe
* per-block overflow guard are unchanged.
* Purpose: Official experiment reducing address-register work in the improved counter.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/120437:
* retained the current accepted CDQ engine and inherited citations.
* saffah_codex_6a_agg3, https://duck.ac/submission/120262:
* ported cumulative byte-leaf counters and their suffix increment/decrement masks.
* Public sources carry no independent software license notices.
* Idea: Replace each leaf's masked horizontal byte sum with one prefix-byte load.
* AVX2 suffix updates preserve that prefix on insertion/removal. Extend the runtime
* fusion guard to require every aligned 32-coordinate group contain <=255 points,
* making byte-prefix overflow impossible; denser inputs use the existing fallback.
* Purpose: Official experiment reducing per-query counter-reduction instructions.
*/
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/108101:
* retained its complete CDQ engine and inherited citations.
* saffah_cc_v41_agg1, https://duck.ac/submission/112070:
* ported the four-level cumulative counter, increment masks and bulk reset.
* No separate software license notices appeared on the public submissions.
* Idea: Transfer the accepted four-upper-level hierarchy into this dimension/size
* engine, adjusting counter prefetch indices and reset bounds consistently.
* Queries use one fewer upper-level load; inserts use one fewer update.
* Purpose: Official experiment of a shared counter improvement across related tasks.
*/
// ===== REFERENCES =====
// [1] 本账号 saffah_cc_v41_agg1，提交 #107873 <https://duck.ac/submission/107873>
// 用途：**本文件正文 = 该提交的完整源码为基座**（它是本发之前我方最好件之一，判题机 301.479140 ms），
// 本发在它之上**只改 `merge_loops` 一个机制 + `solve_b` 里与它配套的两行分配/哨兵**（见"思路"），
// 叶、ctr、参数、事件编码一律未动。
// [2] 本账号 saffah_cc_v41_agg1，提交 #108057 <https://duck.ac/submission/108057>
// 用途：本发的前一版同轴件（判题机 298.716830 ms）：它把 `AX_CROSSPF` 预取的**边界守卫相位分离**
// 出热环（热环 48→42 条/事件）。本发把同一条思路推到**构造性形态**——用**哨兵**把守卫**永久消除**
// （热环 48→40 条/事件，且只剩 1 个分支），因此本发**取代**而不是叠加 #108057。
// [3] 本账号 saffah_cc_v41_agg1，提交 #107441 / #107788 / #107420
// <https://duck.ac/submission/107441> · <https://duck.ac/submission/107788> ·
// <https://duck.ac/submission/107420>
// 用途：#107873 的引擎血统（[LEAFP] 融合前缀位图 / [QIN30] 查询记录打包 / [b13w] 查询侧打包 /
// 指针游标交叉归并 + 八事件预取），**均已在正文内**，本发未改动，仅署名来源。
// [4] duck.ac 用户 saffah_codex_6s_agg2，提交 #107693 <https://duck.ac/submission/107693>
// 用途：本题当前排行榜 rank-1（T = 301.657853 ms），本发要压的目标。
// [5] 本工作区 `BRIEF.md` §2.19.889（"消融表 × 指令账"两表相除 ⇒ 前端受限相位该打"删 uop"）·
// `problems/1011/notes.md` ㉛（判题机侧 IPC 自证：归并主环 IPC = 4.11 ≈ 4 宽前端上限）
// ⇒ 归并主环的绑定资源是**指令条数**，本发据此动刀。
// 许可：以上均为 duck.ac 与本工作区的公开材料，未见附带的许可证声明；本文件按 RULES §3
// 逐项署名"原作者账号 + 原始提交地址 + 所用内容"。
// ======================
// ===== 思路 =====
// 本发 = `#107873` 正文 + **一处机制改动**（单变量族：归并主环的边界/守卫账）：
//
// 【判型】归并主环 26.6% 时间、IPC 实测 4.11（≈4 宽前端上限）⇒ **前端受限** ⇒ 绑定资源 = 指令条数。
// `merge_loops` 原主环 48 条/事件，其中 **12 条（25%）** 是 `AX_CROSSPF`(=8) 逐目标 gather 预取的
// 两条守卫（`if (pa + AX < pa_end) …` / `if (pb + AX < pb_end) …`，汇编 = 2×`lea`+2×`cmp/jcc`，
// 再加两条比较隐含在环尾的双边界检查里）。
//
// 【改动 · [MRG3] 哨兵 + 零填充余量】
// ① `solve_b` 给两条 run 各留 `AX_CROSSPF + 2` 个 u64 余量，并在**归并前**写：
// `retA[h] = ~0ull`（哨兵 = +inf）· `retA[h+1 .. h+AX+1] = 0` · `retB[r .. r+AX+1] = 0`。
// ② 主环改成**单边界**：`while (pb < pb_end)`。理由：`retA[h] = +inf` 使 `takeA = (ea < eb)`
// 对哨兵恒为 0 ⇒ A 自终止、A 端永不越取；A 取尽后环体**逐位退化成原来的 B 尾环**
// （`takeA == 0 ⇒ keep = 1 - role`，即只有 query 事件写 cross、其余只写 out 并推进游标）✓
// ③ 两条预取**无条件发出**：越界位置读到的永远是**零**（余量已清零）⇒ `eid(0) = 0` ⇒ 预取
// `&XE[0]`，**硬安全**（不依赖任何越界读的"恰好没事"）。
// ⇒ 事件取用次序、`out`、`cross` 流**逐条不变**；热环 48 → **40 条/事件**，分支 4 → **1**。
//
// 【为什么不是"删预取"】预取本身是 `[a1x]` 证明过必须留的（notes 补 5：删 MF_LEAFLP/PFM 族判负）；
// 本发**一条预取都没删**，删的是"守卫"（守卫是纯开销，且其语义被余量清零等价替代）。
//
// 【确定性读数（本机 callgrind，判题机同款 gcc 9.3 编译）】总指令
// 3,362,874,565 → **3,208,855,550 = −154.0 M（−4.58%）**；单变量对照：
// 同族只做"守卫相位分离"的 #108057 为 3,266,036,256（−2.88%）⇒ 本发在其之上再少 57.2 M ✓
//
// 【判题机读数（同进程双臂 probe：`rdtsc`、两臂交替、同进程、checksum 两臂相同 2818095627）】
// base 1,081,253,520 ticks ↔ 本发 1,060,150,090 ticks ⇒ **−21,103,430 ticks（−1.952%）** ✓
// （对照：同一台架上 #108057 形态读 −1.150% ⇒ 本机制更强 ✓）
//
// 【闸门】与未改动基底逐位对拍（k=5、n=300000、splitmix64 均匀数据）：
// **CK 11747190579917750320 / SUM 2815262781 逐位相同** ✓；
// `ref/gcc9`（真 gcc 9.3.0）`-O2 -static -U_FORTIFY_SOURCE -std=c++17` 编译 0 error ✓；
// 本发无 `main`；未用 AVX-512 / `-march=native` / mmap / /tmp；源码 < 102400 字符 ✓。
// arena 余量核对：`g_arena` 为 16 M **个 u64**（128 MB），每层只多 2×(AX+2)×8 = 160 B，
// 递归深度 ≤ 5 ⇒ 峰值增量 < 1 KB，无越界 ✓。
// ================
// ===== REFERENCES (z11c_sub4) =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #107420
// <https://duck.ac/submission/107420> 用途：**本文件正文 = #107420 的完整源码**（判题机 307.596277 ms），
// 本发只把**查询侧 6 条按元素数组打包成 3 条 u64**（见"思路"），其余逐字节未动。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #107225（`1011a`，同族题）
// <https://duck.ac/submission/107225> 用途：**`[b13w]` 查询侧打包的形态与出处** —— 该发把
// "查询侧 6 条 u32/u16 存"改为"3 条 u64 存（`QK0/Q12/QIN`）"，且注明"查询侧只被标量读 ⇒ 逐位不变"。
// 本发按 `§2.18.348`（我们**自己两份件**的非注释行 diff）逐条移植，读出端采用其规范化写法 ✓
// [3] `BRIEF.md` `§2.19.759`（读/建比：本发把"建"的**存储条数减半**）· `§2.19.593`（须 objdump 复核发射）
// · `§2.19.636`（逐位对拍）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// **单变量（一处机制）：`base_case_t` 的查询侧按元素数组 6 条（`QK/QC0/QC1/QC2` u32 + `QID` u32 + `QN` u16）
// 打包成 3 条 u64（`QK0/Q12/QIN`），建表存储条数 6 → 3。**
// * 位置：叶建表相位（本席判题机相位账 6.8%，且**斜率实测不饱和** ⇒ 该格有余量 ✓）
// * 打包映射：`QK0 = k | (c0<<32)` · `Q12 = c1 | (c2<<32)` · `QIN = id | (ni<<32)`
// ⇒ 读出端：`QK[q]→(u32)QK0[q]` · `QC0[q]→(u32)(QK0[q]>>32)` · `QC1[q]→(u32)Q12[q]` ·
// `QC2[q]→(u32)(Q12[q]>>32)` · `QID[q]→(u32)QIN[q]` · `QN[q]→(u32)(QIN[q]>>32)` ✓
// * **逐位安全的前提**（移植时逐条核对）：这些数组**只被标量读**（无向量整行读）⇒ 打包不改变任何读语义 ✓；
// 写端只有建表一处 ✓（62 处读点全部按上式机械改写，`grep` 复核 0 残留 ✓）
// 【闸门】① 本地 n=300000 k=7 逐位 checksum 与 `#107420` **完全相同** `fnv=2832291593061836320 sum=2818095627` ✓
// ② 判题机 probe（Pending=0 起跑、warm-up、臂序轮换 `t0,qpack,qpack,t0`、2 样本取 min、**两臂零重叠**）：
// `#107420` 臂 **311.208326 / 311.218350** vs 本发 **308.850348 / 308.900431 ms** ⇒
// **−2.358 ms（−0.758%）** ✓
// ③ 未改动任何插入侧（IK/IC0/IC1/IC2）数组、未动任何预取站点 ✓（单变量）
// 提交目的 = **定价并兑现**（该形态在 k=7 / n=3e5 档的收益）。判据 = 与 `#107420`（307.596277 ms）单变量比。
// ================
// References:
// [1] saffah_cc_v41_agg1, https://duck.ac/submission/107040 :
// directly reused its public accepted 1011 solver with bitmap and sorting network; no separate license notice appeared.
// [2] saffah_codex_6s_agg2, https://duck.ac/submission/107116 :
// adapted our accepted short leaf cursor, prefix, and QN ideas and its inherited public credits.
// Approach: store per-query preceding insertion counts in u16, since each leaf has at most 1344 events; pack 16-bit leaf bucket cursors and test sixteen adjacent bucket sizes per AVX2 vector; replace the scalar leaf bucket prefix chain with an AVX2 inclusive prefix. Maintain exact event ordering and output.
// Purpose: Experimentally measure these 5D leaf refinements on duck.ac.
// [z11_] 单变量：**叶·基数排序的"桶内插入排序"→ 定长比较交换网络（s=2/3/4 分支档；s>=5 保留插入排序）**。
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106818 <https://duck.ac/submission/106818>
// 用途：**本文件正文 = #106818 的逐字节副本 + 一处改动**（只在 [BMP] 位图走查的桶内排序处，见"思路"）。
// #106818 = 本账号 1011 现役最好件（322.218887 ms，绿），改动外的每一字都保留。
// [2] 本账号 `problems/1011/notes.md`（叶·基数格记账，已采信）+ 判题机相位表（`work/k11w_prof.py`，n=300000）：
// 总 1.2753 Gcyc，其中"桶走查 + 桶内插入排序" ≈ 105 Mcyc = 8.2%（上界 26 ms，≫ 缺口 2.6179 ms）✓
// [3] 桶内元素数分布（本席仪表 `.cache/z11_hist2.cpp`，生产 n=300000 实测，最大实例）：≥2 桶 n=1483239，
// s=2 84.8% / s=3 11.3% / s=4 3.5%（累计 99.6%）/ s>=5 仅 0.4% ⇒ 网络化只需覆盖 s<=4 即可 ✓
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1011`：mine = 322.218887（#106818） T = 322.828282（提交早于我方最好件）
// ⇒ 严支 thr = 0.99*T + 1us = 319.600999 ms ⇒ 缺口 **2.6179 ms（0.812%）**。本格是记账上界唯一
// 超过缺口的格（26 ms vs 2.6179 ms）✓
//
// 【本发 = 一处改动】`[BMP]` 位图走查里，桶内 `[lo,hi)` 的插入排序改为**按桶内元素数 s 分档的定长比较交换网络**：
// s=2 → 1 次 CE（min/max 双 cmov、两次无条件存储）；s=3 → 3 元网络（5 比较，min/max 展开，无分支）；
// s=4 → 4 元网络（5 比较）；s>=5 → 原插入排序（**阈值/分支档**，只占 0.4%）。全部比较键都是完整 u64，
// 输出是同一个有序数组（元素相等时字节也相同）⇒ FNV 逐位不变。
// 机理：插入排序在 s=2/3 时几乎只剩**数据相关的条件分支**（`while (q>=lo && v<out[q])`；
// 判题机相位里该段 ≈ 71 cyc/桶，其中含一次高误预测率的分支 + 一次不确定的存储）⇒ 网络化把
// "比较—分支—存储" 换成 "比较—cmov—无条件存储" 的直线代码，消掉误预测（`§2.19.401` 记账上界法）✓
// 预期：本段 105 Mcyc 中、走查开销与元素搬移各半；网络化只动后半的 s<=4 部分（元素搬移的 99.6%），
// 保守取 5~15 Mcyc ⇒ **1.3~3.9 ms**（缺口量级）✓ —— 正负与幅度**以真发为准**（`§2.19.403`）✓
// 【为何是这一格】其余各格（建表/扫描/掩码尾/归并/ctr）的记账上界都 < 2.6 ms（notes.md 已逐格入库）；
// 本格 26 ms 是唯一"上界 > 缺口"的格 ⇒ 批准 ①（修仪表 → 拿 size 分布 → 按档做网络刀 → 真发）✓
// 闸门：`work/a15x_vfy.py`（独立 O(n^2 k) 预言机 + FNV-1a）：**FNV 必须与 #106818 逐位相同**
// （n=300000 fnv=11407442614039170015），另跑生产 n 与 8 种分布 ✓
// ★ 声明：正文逐字节复制本账号已 Accept 的件（#106818），只改一处排序过程 + 注释块。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 #106766 <https://duck.ac/submission/106766>
// 用途：**本文件正文 = #106766 的完整源码**（逐字节复制其正文，只替换开头注释块）。
// 它 = 本账号 #106594 的 1011 引擎 ＋ **把本账号 #106404 的"指针游标交叉归并"移植进来**
// （对手抬头原文：copied #106594 ...；copied #106404's pointer-based cross merge and eight-event XE prefetch）✓
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106594 <https://duck.ac/submission/106594>
// 用途：#106766 的基座（1011 我方现役最好件，334.661304 ms）。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106404 <https://duck.ac/submission/106404>
// 用途："指针游标交叉归并 + 八事件 XE 预取"的原始出处（对手直接搬用）✓
// ======================
// ===== 思路 =====
// **红恢复（`§2.19.018`：raw diff 取证 ⇒ 整代复刻）**：我方被 `#106766 = 322.828282`（对手 −3.5%）打回红。
// **raw diff**（`§2.19.346`）`#106594 → #106766` = **4 hunks / +50 / −26** ⇒ 对手这一代 =
// **把我方自己 #106404 的"指针游标交叉归并"移植到 1011 的 30 万点 CDQ 引擎**（位图叶/输出预取/算术/事件序全保留）✓
// ⇒ **是我方的刀换了个地方回家** ⇒ 复制他的件 = "我方基座 + 该移植"（一发两得）✓
// 闸门：`work/a15x_vfy.py`（独立 O(n²k) 预言机 + FNV）：本件 FNV 必须与 #106594 **逐位相同**
// （基座实测 `VERIFY OK (bad=0)` / n=300000 fnv=11407442614039170015）。
// ★ 声明：正文逐字节复制对手已 Accept 的件；我只替换注释块。
// ================
// ===== REFERENCES =====
// [1] 本账号（saffah_cc_v41_agg1）提交 **#106208** <https://duck.ac/submission/106208>
// （**347.831654 ms** = 本题现役最好件、本账号在 1011 上的记录）—— **本文件正文 = 该提交的
// 逐字节副本 + 两处改动**（见"思路"），其余一字未改。取证：本文件经 `work/a15x_one.py`
// 在 n=300000 上逐位对拍 ⇒ `fnv=2832291593061836320 sum=2818095627`，与 #106208 **完全相同**。
// [2] duck.ac 用户 **saffah_codex_6s_agg2**，提交 **#106147** <https://duck.ac/submission/106147>
// （348.718765 ms）—— 引擎血缘持有者；他的件本身又是我方 #103203 的 5D 端口（`tools/rivalcopy.py 1011`：
// 该件 96.50% 的实质行出现在 `problems/1010a/work/a1r/sub10as.cpp` 里，其自述"Directly copied"）。
// [3] 本账号提交 **#103203** <https://duck.ac/submission/103203>（`problems/1010a/work/a1r/sub10as.cpp`）
// —— 本引擎的算法来源：DN（编译期维度特化）+ SFX（后缀形式融合计数）+ `base_case_t<ND>`。
// [4] 本账号 `problems/1011/notes.md`（追加 2~11）与 `BRIEF.md §2.19.016`（探针适用范围）、
// `§2.19.198`（"只有落进严支线才交"已废止：真改进就交）。
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【口径】`tools/exact.py 1011`：**mine = 347.831654**（#106208） **T = 348.718765**（#106147，提交早于
// 我方最好件）⇒ **严支 thr = 0.99*T + 1us = 345.232577 ms**，缺口 **2.599 ms（0.747%）**。
//
// 【本发 = #106208 逐字节副本 + 两处**改动**（两处都各自定价过；这个**组合从未提交过**）】
//
// ① ★ **[BMP] 基数排序的"非空桶"位图**（本发主力刀，**本轮新刀**）
// 机理（判题机 `rdtsc` 相位插桩实测，`work/k11w_prof.py`，n=300000）：
// 总 1.2753 Gcyc / 叶 53.4%（建表 7.2% + **扫描 32.0%** + 基数 14.2%）/ 归并 30.2% / `ctr_solve` 14.7%。
// 其中**基数相位 181.3 Mcyc（14.2%）里，桶走查占 81 Mcyc**：原实现在每个叶子里都走 `LFB=2345` 个桶
// （`LFB = ((n-1)>>LFSH)+2`，只用到 `(n-1)>>7 = 2343` 个），而 leaf 只有 `m≈1172` 个事件 ⇒
// **≈90% 的桶是空的**，每桶还要付一条**不可预测分支**（`if (hi - lo > 1)`，命中率≈9%）⇒ 5.6 cyc/桶。
// **本刀**：把"桶→是否需要插入排序"的判定**向量化预计算**成一张位图（每桶 1 bit），然后**只走被置位的桶**：
// · 建图：每 8 个桶一条 AVX2（`loadu` 两次 + `vpsubd` + `vpcmpgtd 1` + `movemask`）⇒ **每桶 ≈1 uop**；
// 用**每 64 桶一个 u64 累加器**（寄存器内 `|=`，避免读改写链），只在字尾写一次内存。
// ⚠ 这里必须用**插入排序前的 `cnt[]` 前缀和**（`size(b) = cnt[b+1]-cnt[b]`），不能用走查时的 `cnt`。
// · 走查：`while (x) { b = ctz(x); x &= x-1; ... 原有插入排序 [cnt[b-1], cnt[b]) ... }`。
// · **语义完全不变**：桶的划分（`key>>(LFSH+LFD)`）与桶内插入排序一字未改，只跳过"空桶/单桶"
// （这两种桶里原代码的插入排序本来就是空转）⇒ 输出逐位相同（闸门见文末）。
// **判题机定价**（同进程双臂轮流，预热过 arena，两臂 checksum 均 2818095627）：
// base（= #106208 正文）**1 248 750 172** vs 本刀 **1 216 289 334** = **−2.41%**（单臂）。
//
// ② **[OUTPF] 叶终端写回的目标预取**（`OUTPF=4`）
// 叶里每查一次就做一次 `OUT[((u32)(QIN[q]))] += hsum256(...)` —— 对 1.2 MB 输出数组的**随机 RMW**（每查一次一次）。
// `prefetchw` 抢独占行，距离 `4*OUTPF`（4 路核）/`3*OUTPF`（3 路核）。gcc 9.3 `-O2` 把 `__builtin_prefetch(p,1,L)`
// 编成 `prefetchnta`（不省 RFO）⇒ 本处用内联汇编。**判题机同模式配对定价 −0.20%**（#106252 vs #106208 的慢模基线，
// 见 notes 追加 7），同刀在我方旧引擎上单独量过 −0.224%。
//
// 【叠加定价（本组合，判题机同进程双臂）】base **1 248 750 172** vs **1 199 714 552** = **−3.93%**
// ⇒ 快模预期 `347.831654 × (1-0.0393) ≈ **334.2 ms**`，对严支 `345.232577` 有余量 **≈11 ms**。
// ★ 同时该发给出**态判据**：base 臂的绝对周期 **1.2488 Gcyc** = **快模值**（同码在 13:03~13:32 读到
// 1.4100~1.4102 Gcyc = 慢模）⇒ 本发提交时判题机处于快模（`notes.md` 追加 2 的"双模"现象）。
// 【分类】① 是"新增指令 + 528 B 栈上数组"；② 是"只新增指令"。**两者都不改算法/不改任何工作数组的尺寸与偏移**
// （`bmp` 在叶帧末尾、不改 `cnt/IK/IC0../QN` 的偏移）⇒ 按 `§2.19.016` 属于**探针可定价**的一类。
// 【重叠自检】① 只作用于基数排序的走查相位；② 只作用于叶终端写回；两处正交，且都不碰 `KG_BASE`/`LEAFNB`/
// `MF_LEAFG`/`CT_MAXV`/`MF_LEAFLP` 等**参数轴**（参数轴按 notes 追加 7/§3：只能正式提交定价）。
// 【正确性闸门】
// · 独立 O(n^2 k) 暴力 oracle（`work/a15x_vfy.py`，零共享代码）：n=1..300000 × 8 种分布 ⇒ **0 mismatch**（bad=0）；
// · 全新进程单次调用 n=300000：**fnv=2832291593061836320 sum=2818095627**，与 #106208 **逐位相同**；
// · 判题机同进程双臂：两臂 checksum 均 **2818095627**（与历史值一致）；
// · 判题端同款编译 `g++ -O2 -static -U_FORTIFY_SOURCE -std=c++17 -c`：**0 warning**；gcc 9.3（godbolt）**exit=0**。
// ================
// References: saffah_codex_6s_agg2, https://duck.ac/submission/106138 : directly reused our accepted 1011a dimension-specialized CDQ solver and its inherited citations; no license notice was shown.
// Approach: Apply the verified five-dimensional packed CDQ engine to 300,000 points, with a 16-million-event arena and a sixth suffix-counter tier covering coordinates above 131071.
// Purpose: Test whether the newer 5D engine improves official 1011 time.
// References: saffah_codex_6s_agg2, https://duck.ac/submission/106122 : directly reused our accepted 1010a specialized CDQ solver, its inherited citations, and first-coordinate event optimizations for 5D; no license notice was shown.
// Approach: Instantiate the same dimension-specialized packed event engine for five dimensions, using the fused innermost counter and existing fast leaf.
// Purpose: Test whether the newer 1010a engine improves official 1011a time against our #106131.
// References: saffah_codex_6s_agg2, https://duck.ac/submission/106114 : directly reused our accepted single-pass event builder and its inherited citations; no license notice was shown.
// Approach: Reuse the counting-sort array's group-end offsets to visit first-coordinate groups, avoiding random x0 reads when detecting each boundary.
// Purpose: Test whether sharing sort boundaries reduces official 1010a time.
// References: saffah_codex_6s_agg2, https://duck.ac/submission/106067 : directly reused our accepted specialized CDQ solver and its inherited citations; no license notice was shown.
// Approach: Build each first-coordinate equal-value group's query and insert events in one pass, loading the two later coordinates only once per point while preserving the query-before-insert order.
// Purpose: Test whether avoiding duplicate random coordinate loads improves official 1010a time.
// References: saffah_codex_6s_agg2, https://duck.ac/submission/103873 : directly reused our accepted specialized CDQ solver and its inherited citations; no license notice was shown.
// Approach: Remove two redundant monotonicity guards: QN is the running insert count recorded as queries are scanned in order, so it cannot decrease across adjacent queries.
// Purpose: Test whether avoiding comparison and branch work in the 3/4-query SIMD leaf paths improves official 1010a time.
// References:
// [0] saffah_cc_v41_agg1, duck.ac submission #103203,
// https://duck.ac/submission/103203 . Directly copied its accepted
// dimension-specialized CDQ solver and suffix-form fused counter.
// [1] saffah_codex_6s_agg2, duck.ac submission #103069,
// https://duck.ac/submission/103069 . Earlier specialized solver
// directly copied into [0], inherited here.
// [2] saffah_codex_6s_agg2, duck.ac submission #103094,
// https://duck.ac/submission/103094 . Suffix-counter update idea
// adapted by [0], inherited here.
// [3] saffah_cc_v41_agg1, duck.ac submission #101855,
// https://duck.ac/submission/101855 . Specialized CDQ and SIMD leaf
// engine inherited through [1].
// [4] saffah_cc_v41_260924, duck.ac submission #101795,
// https://duck.ac/submission/101795 . Early template dimension
// dispatch inherited through [3].
// No separate license notices appeared on these public submissions;
// all authors, URLs and reused parts are credited here.
// Approach:
// Lower the CDQ leaf/base crossover from 2560 to 2048 events in the
// suffix-counter engine to reduce quadratic leaf work and increase the
// share handled by recursive merges.
// Purpose:
// Measure the smaller leaf boundary on the official judge.
#ifndef MF_CTRPF
#define MF_CTRPF 0
#endif
#ifndef MF_CTR5
#define MF_CTR5 1
#endif
#ifndef MF_LEAFLP
#define MF_LEAFLP 16
#endif
#ifndef MF_LEAFG
#define MF_LEAFG 4
#endif
#pragma GCC optimize("O3","unroll-loops","rename-registers")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
// duck.ac 1010 (4D) / 1011 (5D) -- "count for every point the number of points that are
// smaller in *every* dimension" (n = 300000, coords in [0,n), strict comparisons).
//
// Algorithm: D&C over dimensions on an event sequence, keys carried inline.
// * 2n events: one query event + one insert event per point, keyed by dim 0
// (a query event is stored *before* an insert event of the same key, which encodes
// the strict-inequality rule).
// * solve(seq,m,d): seq is ordered by dim d and every event carries the coordinate of
// dim d+1 in bits 32..63 of its u64. Split by position, recurse both halves, then
// merge the two halves by the carried key (a plain unsigned `<` on the packed u64,
// so equal keys keep query-before-insert order); the same pass collects the cross
// events (left inserts + right queries), re-keys them to dim d+2 and recurses one
// dimension deeper. Ordering by dim d with that tie rule makes "insert before query"
// exactly "all dims so far strictly smaller", and equal coordinates are never counted.
// * d == K-1: every insert-before-query pair now qualifies, so one O(m) running counter
// finishes the innermost dimension (no log factor).
// * m <= 32: direct O(m^2) counting plus an insertion sort.
//
// Local timings (i5-6500 @ 3.2GHz, best of 3, n = 300000 uniform random):
// 4D 1.57 s 5D 3.85 s
// (Board #1: 508.596 ms / 745.358 ms -- this is still 3x / 5x behind.)
// k-dimensional dominance counting: out[i] = #{j : all dims of j < dims of i}
//
// Event-sequence CDQ with keys carried inline.
// event (u64) = (key << 32) | (ins << 31) | id ins = 1 for an "insert" event
// key = coordinate of dim (level+1): the field used by this level's merge.
// The packing makes a plain unsigned comparison put, for equal keys, the query
// event first -- exactly the strict-inequality rule (equal coords must not count).
//
// solve(seq, m, d): seq is ordered by dim d (tie rule above), elements carry the
// key for dim d+1; count pairs (insert before query) with dims d+1..K-1 strictly
// smaller; return `out` = the same events merged by the carried key (= dim d+1).
// Cross = A-inserts + B-queries re-keyed to dim d+2, recursed at level d+1.
// d == K-1 : every (insert before query) pair qualifies -> running counter, O(m).
#include <cstring>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC target("avx2,popcnt,bmi2")
#include <cstdint>
typedef unsigned u32;
typedef uint64_t u64;
typedef unsigned char u8;
typedef unsigned short u16;
#ifndef K11W_BMP
#define K11W_BMP 1
#endif
#ifndef KG_COND
#define KG_COND 0
#endif
#ifndef OUTPF
#define OUTPF 1
#endif
#ifndef KG_PF
#define KG_PF 0
#endif
#ifndef KG_BASE
#define KG_BASE 2304
#endif
#ifndef LEAFNB
#define LEAFNB 4096
#endif
/* [SNET] 桶内排序：定长比较交换网络档位（1 = 只 s==2；2 = +s==3；3 = +s==4；0 = 关，回原插入排序）。
逐档定价可用 -DSM7_SNET=n 覆盖；提交件用默认档。见文件头"思路"。 */
#ifndef SM7_SNET
#define SM7_SNET 3
#endif
#define KG_MAXK 5
#define KG_ARENA (16u << 20)
namespace kg {
// ------------ fused innermost-dimension counter (prefix count over [0,n)) -------------
// AVX2. Levels: u8 leaf /32 values, u16 per 32 and per 256, u32 per 2048/16384/131072.
// Every u16 block count must stay <= 32767 (madd uses signed lanes); the guard (max
// multiplicity of a last-dim coordinate <= 127) bounds 32*127=4064 and 256*127=32512.
#define CT_MAXV 1048580u
struct alignas(64) PrefixCounterStorage {
alignas(64) u8 CT0[CT_MAXV];
alignas(64) u16 CT1[CT_MAXV / 32 + 64];
alignas(64) u16 CT2[CT_MAXV / 512 + 64];
alignas(64) u32 CT3[CT_MAXV / 8192 + 64];
alignas(64) u32 CT4[CT_MAXV / 131072 + 16];
};
static PrefixCounterStorage prefixct;
#define CT0 (prefixct.CT0)
#define CT1 (prefixct.CT1)
#define CT2 (prefixct.CT2)
#define CT3 (prefixct.CT3)
#define CT4 (prefixct.CT4)
/* [10ez6-L4] four upper layers instead of five: bits 5-8 / 9-12 / 13-16 / 17-19 (leaf = bits 0-4).
Same suffix-ladder semantics, one fewer scalar load per query and one fewer RMW per insert. */
// [SFX] suffix-counter increment masks. Row r holds a 1 in every lane strictly
// above r, so an insert landing in block r adds one to each suffix position of
// r's 8-block group that must start counting it.
static const u16 INC16[16][16] __attribute__((aligned(64))) = { {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} };
static const u32 INC32W[16][16] __attribute__((aligned(64))) = { {0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} };
static const u32 INC32[8][8] __attribute__((aligned(32))) = {
{0,1,1,1,1,1,1,1},{0,0,1,1,1,1,1,1},{0,0,0,1,1,1,1,1},{0,0,0,0,1,1,1,1},
{0,0,0,0,0,1,1,1},{0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0}};
#define SFX16(p, r) do { __m256i _a = _mm256_load_si256((const __m256i *)(p)); \
__m256i _b = _mm256_load_si256((const __m256i *)(((const u16 *)INC16) + 16 * (size_t)(r))); \
_mm256_store_si256((__m256i *)(p), _mm256_add_epi16(_a, _b)); } while (0)
#define SFX32(p, r) do { __m256i _a = _mm256_load_si256((const __m256i *)(p)); \
__m256i _b = _mm256_load_si256((const __m256i *)(INC32 + (r))); \
_mm256_store_si256((__m256i *)(p), _mm256_add_epi32(_a, _b)); } while (0)
#define SFX32W(p, r) do { __m256i _a = _mm256_load_si256((const __m256i *)(p)); \
__m256i _c = _mm256_load_si256((const __m256i *)(((const u32 *)INC32W) + 16 * (size_t)(r))); \
_mm256_store_si256((__m256i *)(p), _mm256_add_epi32(_a, _c)); \
__m256i _d = _mm256_load_si256((const __m256i *)(p) + 1); \
__m256i _e = _mm256_load_si256((const __m256i *)(((const u32 *)INC32W) + 16 * (size_t)(r)) + 1); \
_mm256_store_si256((__m256i *)(p) + 1, _mm256_add_epi32(_d, _e)); } while (0)
static int FUSE_OK;
static inline u32 su8_32(const u8 *p, int cnt) {
__m256i v = _mm256_loadu_si256((const __m256i *)p);
__m256i m = _mm256_cmpgt_epi8(_mm256_set1_epi8((char)cnt),
_mm256_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31));
__m256i x = _mm256_and_si256(v, m);
__m256i s = _mm256_sad_epu8(x, _mm256_setzero_si256());
__m128i t = _mm_add_epi64(_mm256_castsi256_si128(s), _mm256_extracti128_si256(s, 1));
return (u32)((unsigned long long)_mm_cvtsi128_si64(t) + (unsigned long long)_mm_extract_epi64(t, 1));
}
static inline u32 su16_8(const u16 *p, int cnt) {
__m128i v = _mm_loadu_si128((const __m128i *)p);
__m128i x = _mm_and_si128(v, _mm_cmpgt_epi16(_mm_set1_epi16((short)cnt),
_mm_setr_epi16(0, 1, 2, 3, 4, 5, 6, 7)));
__m128i s = _mm_madd_epi16(x, _mm_set1_epi16(1));
s = _mm_add_epi32(s, _mm_shuffle_epi32(s, _MM_SHUFFLE(1, 0, 3, 2)));
s = _mm_add_epi32(s, _mm_shuffle_epi32(s, _MM_SHUFFLE(2, 3, 0, 1)));
return (u32)_mm_cvtsi128_si32(s);
}
static inline u32 su32_8(const u32 *p, int cnt) {
__m256i v = _mm256_loadu_si256((const __m256i *)p);
__m256i x = _mm256_and_si256(v, _mm256_cmpgt_epi32(_mm256_set1_epi32(cnt),
_mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7)));
__m128i t = _mm_add_epi32(_mm256_castsi256_si128(x), _mm256_extracti128_si256(x, 1));
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);
}
static const u8 INC8[32][32] __attribute__((aligned(32))) = {
{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
};
static inline void leaf_add(u32 v) {
__m256i *p=(__m256i *)(CT0+(v&~31u));
_mm256_store_si256(p,_mm256_add_epi8(_mm256_load_si256(p),_mm256_load_si256((const __m256i *)INC8[v&31])));
}
static inline void leaf_sub(u32 v) {
__m256i *p=(__m256i *)(CT0+(v&~31u));
_mm256_store_si256(p,_mm256_sub_epi8(_mm256_load_si256(p),_mm256_load_si256((const __m256i *)INC8[v&31])));
}
static inline void ctr_ins(u32 v) {
leaf_add(v);
SFX16(CT1 + ((v >> 9) << 4), (v >> 5) & 15);
SFX16(CT2 + ((v >> 13) << 4), (v >> 9) & 15);
SFX32W(CT3 + ((v >> 17) << 4), (v >> 13) & 15);
SFX32(CT4, (v >> 17) & 7);
}
static inline void ctr_clr(u32 v) {
leaf_sub(v); // [CTRR] CT1..CT5 are restored in bulk by ctr_reset_hi()
}
// [CTRR] live bound of the coordinate values seen by ctr_* (set in run_t)
static u32 CTN;
static inline void ctr_reset_hi(void) {
memset(CT1, 0, sizeof(u16) * (((size_t)CTN >> 5) + 32));
memset(CT2, 0, sizeof(u16) * (((size_t)CTN >> 9) + 32));
memset(CT3, 0, sizeof(u32) * (((size_t)CTN >> 13) + 32));
memset(CT4, 0, sizeof(CT4));
}
static inline u32 ctr_qry(u32 v) {
u32 s = CT4[v >> 17];
s += CT3[v >> 13];
s += CT2[v >> 9];
s += CT1[v >> 5];
s += CT0[v];
return s;
}
#ifndef LFAUTO
#define LFAUTO 0
#endif
static int LFSH;
static int LFD;
static int LFB; // [v4] dynamic bucket count
static const u32 *XD[KG_MAXK];
static u32 *OUT;
static u64 *AB, *ABtop;
static inline int eid(u64 v) { return (int)(v & 0x1FFFFFu); }
static inline int lfbucket(u64 v) { return (int)(((u32)(v >> 43)) >> LFSH); }
static inline int eq_(u64 v) { return (int)((v >> 42) & 1); }
static inline int keep_test(int takeA, int role) { return 1 - (takeA ^ role); }
static inline u32 embnk(u64 v) { return (u32)((v >> 21) & 0x1FFFFFu); }
static inline u64 mk(u32 key, int q, int id, u32 nk) {
return ((u64)key << 43) | ((u64)(1 - q) << 42) | ((u64)nk << 21) | (u64)id;
}
// ---- compile-time depth/dimension specialisation (the fleet's `DN` recipe) ----
// Everything that used to be a runtime `if (d ...)` / `if (K ...)` inside the leaf and in
// the merge becomes a template constant, so the leaf kernels lose their per-iteration
// `nd > 0 / > 1 / > 2` tests AND are instantiated per remaining-dimension count.
template <bool B> struct TB {};
template <int V> struct NCL { static const int v = (V < 0) ? 0 : ((V > 3) ? 3 : V); };
template <int KT, int D, int NO> static inline void solve_t(u64 *seq, int m, u64 *out);
// resolve a fusion-level cross: events carry the last dim (K-1) coordinate in bits 32..63
// and are ordered by dim K-2; a left-insert before a right-query with a strictly smaller
// last-dim value is a hit.
static void ctr_solve(u64 *cross, int cx, u32 *dirt) {
int nd = 0;
for (int i = 0; i < cx; i++) {
#if MF_CTRPF > 0
if (i + MF_CTRPF < cx) {
u32 vf = (u32)(cross[i + MF_CTRPF] >> 43);
__builtin_prefetch(&CT0[vf], 1, 0);
__builtin_prefetch(&CT1[vf >> 5], 1, 0);
__builtin_prefetch(&CT2[vf >> 9], 1, 0);
}
#endif
u64 v = cross[i];
u32 val = (u32)(v >> 43);
if ((v >> 42) & 1) { ctr_ins(val); dirt[nd++] = val; }
else OUT[eid(v)] += ctr_qry(val);
}
if ((u32)nd > (CTN >> 7)) {
memset(CT0, 0, (size_t)CTN);
} else {
for (int i = 0; i < nd; i++) ctr_clr(dirt[i]);
}
ctr_reset_hi();
}
// small base: compact insert list + SIMD comparison, then insertion sort by the key
static const u32 VMASK[8][8] = {
{0,0,0,0,0,0,0,0},
{~0u,0,0,0,0,0,0,0},
{~0u,~0u,0,0,0,0,0,0},
{~0u,~0u,~0u,0,0,0,0,0},
{~0u,~0u,~0u,~0u,0,0,0,0},
{~0u,~0u,~0u,~0u,~0u,0,0,0},
{~0u,~0u,~0u,~0u,~0u,~0u,0,0},
{~0u,~0u,~0u,~0u,~0u,~0u,~0u,0}};
static inline u32 hsum256(__m256i v) {
__m128i t = _mm_add_epi32(_mm256_castsi256_si128(v), _mm256_extracti128_si256(v, 1));
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);
}
static inline void leaf_prefix16(u16 *p, int len) {
const __m256i last = _mm256_setr_epi8(14,15,14,15,14,15,14,15,14,15,14,15,14,15,14,15,
14,15,14,15,14,15,14,15,14,15,14,15,14,15,14,15);
__m256i carry = _mm256_setzero_si256();
int i = 0;
for (; i + 16 <= len; i += 16) {
__m256i x = _mm256_loadu_si256((const __m256i *)(p + i));
x = _mm256_add_epi16(x, _mm256_slli_si256(x, 2));
x = _mm256_add_epi16(x, _mm256_slli_si256(x, 4));
x = _mm256_add_epi16(x, _mm256_slli_si256(x, 8));
x = _mm256_add_epi16(x, _mm256_shuffle_epi8(_mm256_permute2x128_si256(x, x, 0x08), last));
x = _mm256_add_epi16(x, carry);
_mm256_storeu_si256((__m256i *)(p + i), x);
carry = _mm256_shuffle_epi8(_mm256_permute2x128_si256(x, x, 0x11), last);
}
u32 c = i ? p[i - 1] : 0;
for (; i < len; i++) { c += p[i]; p[i] = (u16)c; }
}
static inline void leaf_prefix16_bmp(u16 *p, int len, u64 *bmp) {
const __m256i last = _mm256_setr_epi8(14,15,14,15,14,15,14,15,14,15,14,15,14,15,14,15,
14,15,14,15,14,15,14,15,14,15,14,15,14,15,14,15);
const __m256i one = _mm256_set1_epi16(1);
__m256i carry = _mm256_setzero_si256();
u64 bits=0; int w=0;
int i = 1; // p[0] is zero; raw p[i] counts bucket i-1.
for (; i + 16 <= len; i += 16) {
__m256i x = _mm256_loadu_si256((const __m256i *)(p + i));
__m256i mark = _mm256_cmpgt_epi16(x,one);
u32 mask=(u32)_pext_u32((u32)_mm256_movemask_epi8(mark),0x55555555u);
bits |= (u64)mask << ((i-1)&63);
if (((i-1)&63)==48) { bmp[w++]=bits; bits=0; }
x = _mm256_add_epi16(x, _mm256_slli_si256(x, 2));
x = _mm256_add_epi16(x, _mm256_slli_si256(x, 4));
x = _mm256_add_epi16(x, _mm256_slli_si256(x, 8));
x = _mm256_add_epi16(x, _mm256_shuffle_epi8(_mm256_permute2x128_si256(x, x, 0x08), last));
x = _mm256_add_epi16(x, carry);
_mm256_storeu_si256((__m256i *)(p + i), x);
carry = _mm256_shuffle_epi8(_mm256_permute2x128_si256(x, x, 0x11), last);
}
u32 c = i>1 ? p[i-1] : 0;
for (; i < len; i++) {
if (p[i]>1) bits|=1ull<<((i-1)&63);
c += p[i]; p[i] = (u16)c;
if (((i-1)&63)==63) { bmp[w++]=bits;bits=0; }
}
if (((len-1)&63)!=0) bmp[w]=bits;
}
template<int ND>
static void base_case_t(u64 *seq, int m, int d, u64 *out, int needOut) {
const int nd = ND;
__attribute__((aligned(32)))
u32 IK[KG_BASE + 8], IC0[KG_BASE + 8], IC1[KG_BASE + 8], IC2[KG_BASE + 8];
/* [b13w] query-side packing (ported from 1011a #107225): 6 u32/u16 stores -> 3 u64 stores.
The query-side arrays are only ever read scalar-ly, so packing is value-identical. */
u64 QK0[KG_BASE + 8], Q12[KG_BASE + 8]; u32 QIN[KG_BASE + 8];
const u32 *X1 = (ND > 1) ? XD[d + 3] : 0, *X2 = (ND > 2) ? XD[d + 4] : 0;
/* dim d+2 is ALWAYS inside the event whenever it is needed: at d == 0 by mk()'s nk, and
at d >= 1 by the level-(d-1) cross's embed. "needed" is exactly nd > 0, i.e.
d + 2 <= K - 1 -- which is also the precondition of that embed chain, so the guard
`d == 0 || d <= K - 3` of the runtime version was redundant and is folded away here. */
int ni = 0, nq = 0;
for (int t = 0; t < m; t++) {
#if MF_LEAFLP > 0
if ((ND > 1) && t + MF_LEAFLP < m) {
int idf = eid(seq[t + MF_LEAFLP]);
if (ND > 2) __builtin_prefetch(&X2[idf], 0, 1);
__builtin_prefetch(&X1[idf], 0, 1);
}
#endif
u64 v = seq[t];
int id = eid(v);
u32 k = (u32)(v >> 43);
u32 c0 = 0, c1 = 0, c2 = 0;
if (ND > 0) c0 = embnk(v);
if (ND > 1) c1 = X1[id];
if (ND > 2) c2 = X2[id];
int isins = (int)((v >> 42) & 1u);
IK[ni] = k; IC0[ni] = c0; IC1[ni] = c1; IC2[ni] = c2; ni += isins;
QK0[nq] = (u64)k | ((u64)c0 << 32);
Q12[nq] = (u64)c1 | ((u64)c2 << 32);
QIN[nq] = (u32)id | ((u32)ni << 19);
nq += 1 - isins;
}
#if !defined(MF_G34_LDA)
#define MF_G34_LDA(p) _mm256_load_si256((const __m256i *)(p))
#define MF_G34_LDU(p) _mm256_loadu_si256((const __m256i *)(p))
#endif
#define LDA(p) MF_G34_LDA(p)
#define LDU_MASK(k) MF_G34_LDU((const __m256i *)VMASK[k])
// ---- masked single-query tail for one member of a wide group ----
#define K11B_TAIL(ACC, KVQ, C0Q, C1Q, C2Q, NX, JS) do { \
int jj = (JS); \
for (; jj + 8 <= (NX); jj += 8) { \
__m256i msk = _mm256_cmpgt_epi32(KVQ, LDA(IK + jj)); \
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C0Q, LDA(IC0 + jj))); \
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C1Q, LDA(IC1 + jj))); \
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C2Q, LDA(IC2 + jj))); \
ACC = _mm256_sub_epi32(ACC, msk); \
} \
if (jj < (NX)) { \
int nn_ = (NX); \
__m256i msk = _mm256_cmpgt_epi32(KVQ, LDA(IK + jj)); \
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C0Q, LDA(IC0 + jj))); \
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C1Q, LDA(IC1 + jj))); \
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C2Q, LDA(IC2 + jj))); \
msk = _mm256_and_si256(msk, LDU_MASK(nn_ - jj)); \
ACC = _mm256_sub_epi32(ACC, msk); \
} \
} while (0)
int q = 0;
#if MF_LEAFG >= 4
// ---- 4-wide staircase leaf (used when nd <= 1, i.e. A = nd+1 <= 2 insert arrays) ----
if (nd <= 1) {
for (; q + 4 <= nq; q += 4) {
const int nA4 = (int)(QIN[q] >> 19), nB4 = (int)(QIN[q+1] >> 19), nC4 = (int)(QIN[q+2] >> 19), nD4 = (int)(QIN[q+3] >> 19);
__m256i kA4 = _mm256_set1_epi32((int)((u32)(QK0[q]))), dA4 = _mm256_set1_epi32((int)((u32)(QK0[q] >> 32))),
aA4 = _mm256_setzero_si256();
__m256i kB4 = _mm256_set1_epi32((int)((u32)(QK0[q+1]))), dB4 = _mm256_set1_epi32((int)((u32)(QK0[q+1] >> 32))),
aB4 = _mm256_setzero_si256();
__m256i kC4 = _mm256_set1_epi32((int)((u32)(QK0[q+2]))), dC4 = _mm256_set1_epi32((int)((u32)(QK0[q+2] >> 32))),
aC4 = _mm256_setzero_si256();
__m256i kD4 = _mm256_set1_epi32((int)((u32)(QK0[q+3]))), dD4 = _mm256_set1_epi32((int)((u32)(QK0[q+3] >> 32))),
aD4 = _mm256_setzero_si256();
#if OUTPF > 0
if (q + 4 * OUTPF + 4 <= nq) {
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[(QIN[q + 4 * OUTPF + 0] & 0x7ffffu)])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[(QIN[q + 4 * OUTPF + 1] & 0x7ffffu)])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[(QIN[q + 4 * OUTPF + 2] & 0x7ffffu)])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[(QIN[q + 4 * OUTPF + 3] & 0x7ffffu)])));
}
#endif
int j4 = 0;
for (; j4 + 8 <= nA4; j4 += 8) { // A, B, C, D
__m256i IKv = LDA(IK + j4);
__m256i mA = _mm256_cmpgt_epi32(kA4, IKv), mB = _mm256_cmpgt_epi32(kB4, IKv),
mC = _mm256_cmpgt_epi32(kC4, IKv), mD = _mm256_cmpgt_epi32(kD4, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j4);
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(dA4, C0v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB4, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC4, C0v));
mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, C0v));
}
aA4 = _mm256_sub_epi32(aA4, mA); aB4 = _mm256_sub_epi32(aB4, mB);
aC4 = _mm256_sub_epi32(aC4, mC); aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pA4 = j4;
for (; j4 + 8 <= nB4; j4 += 8) { // B, C, D
__m256i IKv = LDA(IK + j4);
__m256i mB = _mm256_cmpgt_epi32(kB4, IKv), mC = _mm256_cmpgt_epi32(kC4, IKv),
mD = _mm256_cmpgt_epi32(kD4, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j4);
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB4, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC4, C0v));
mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, C0v));
}
aB4 = _mm256_sub_epi32(aB4, mB); aC4 = _mm256_sub_epi32(aC4, mC);
aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pB4 = j4;
for (; j4 + 8 <= nC4; j4 += 8) { // C, D
__m256i IKv = LDA(IK + j4);
__m256i mC = _mm256_cmpgt_epi32(kC4, IKv), mD = _mm256_cmpgt_epi32(kD4, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j4);
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC4, C0v));
mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, C0v));
}
aC4 = _mm256_sub_epi32(aC4, mC); aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pC4 = j4;
for (; j4 + 8 <= nD4; j4 += 8) { // D only
__m256i mD = _mm256_cmpgt_epi32(kD4, LDA(IK + j4));
if (nd > 0) mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, LDA(IC0 + j4)));
aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pD4 = j4;
K11B_TAIL(aA4, kA4, dA4, dA4, dA4, nA4, pA4);
K11B_TAIL(aB4, kB4, dB4, dB4, dB4, nB4, pB4);
K11B_TAIL(aC4, kC4, dC4, dC4, dC4, nC4, pC4);
K11B_TAIL(aD4, kD4, dD4, dD4, dD4, nD4, pD4);
OUT[(QIN[q] & 0x7ffffu)] += hsum256(aA4);
OUT[(QIN[q + 1] & 0x7ffffu)] += hsum256(aB4);
OUT[(QIN[q + 2] & 0x7ffffu)] += hsum256(aC4);
OUT[(QIN[q + 3] & 0x7ffffu)] += hsum256(aD4);
}
}
#endif
#if MF_LEAFG >= 3
// ---- 3-wide staircase leaf (used when nd <= 2, i.e. A = nd+1 <= 3 insert arrays) ----
if (nd <= 2) {
for (; q + 3 <= nq; q += 3) {
const int nA3 = (int)(QIN[q] >> 19), nB3 = (int)(QIN[q + 1] >> 19), nC3 = (int)(QIN[q + 2] >> 19);
__m256i kA3 = _mm256_set1_epi32((int)((u32)(QK0[q]))), dA3 = _mm256_set1_epi32((int)((u32)(QK0[q] >> 32))),
eA3 = _mm256_set1_epi32((int)((u32)(Q12[q]))), aA3 = _mm256_setzero_si256();
__m256i kB3 = _mm256_set1_epi32((int)((u32)(QK0[q+1]))), dB3 = _mm256_set1_epi32((int)((u32)(QK0[q+1] >> 32))),
eB3 = _mm256_set1_epi32((int)((u32)(Q12[q+1]))), aB3 = _mm256_setzero_si256();
__m256i kC3 = _mm256_set1_epi32((int)((u32)(QK0[q+2]))), dC3 = _mm256_set1_epi32((int)((u32)(QK0[q+2] >> 32))),
eC3 = _mm256_set1_epi32((int)((u32)(Q12[q+2]))), aC3 = _mm256_setzero_si256();
#if OUTPF > 0
if (q + 3 * OUTPF + 3 <= nq) {
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[(QIN[q + 3 * OUTPF + 0] & 0x7ffffu)])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[(QIN[q + 3 * OUTPF + 1] & 0x7ffffu)])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[(QIN[q + 3 * OUTPF + 2] & 0x7ffffu)])));
}
#endif
int j3 = 0;
for (; j3 + 8 <= nA3; j3 += 8) { // A, B, C
__m256i IKv = LDA(IK + j3);
__m256i mA = _mm256_cmpgt_epi32(kA3, IKv), mB = _mm256_cmpgt_epi32(kB3, IKv),
mC = _mm256_cmpgt_epi32(kC3, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j3);
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(dA3, C0v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB3, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC3, C0v));
}
if (nd > 1) {
__m256i C1v = LDA(IC1 + j3);
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(eA3, C1v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(eB3, C1v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(eC3, C1v));
}
aA3 = _mm256_sub_epi32(aA3, mA); aB3 = _mm256_sub_epi32(aB3, mB);
aC3 = _mm256_sub_epi32(aC3, mC);
}
const int pA3 = j3;
for (; j3 + 8 <= nB3; j3 += 8) { // B, C
__m256i IKv = LDA(IK + j3);
__m256i mB = _mm256_cmpgt_epi32(kB3, IKv), mC = _mm256_cmpgt_epi32(kC3, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j3);
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB3, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC3, C0v));
}
if (nd > 1) {
__m256i C1v = LDA(IC1 + j3);
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(eB3, C1v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(eC3, C1v));
}
aB3 = _mm256_sub_epi32(aB3, mB); aC3 = _mm256_sub_epi32(aC3, mC);
}
const int pB3 = j3;
for (; j3 + 8 <= nC3; j3 += 8) { // C only
__m256i IKv = LDA(IK + j3);
__m256i mC = _mm256_cmpgt_epi32(kC3, IKv);
if (nd > 0) mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC3, LDA(IC0 + j3)));
if (nd > 1) mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(eC3, LDA(IC1 + j3)));
aC3 = _mm256_sub_epi32(aC3, mC);
}
const int pC3 = j3;
K11B_TAIL(aA3, kA3, dA3, eA3, eA3, nA3, pA3);
K11B_TAIL(aB3, kB3, dB3, eB3, eB3, nB3, pB3);
K11B_TAIL(aC3, kC3, dC3, eC3, eC3, nC3, pC3);
OUT[(QIN[q] & 0x7ffffu)] += hsum256(aA3);
OUT[(QIN[q + 1] & 0x7ffffu)] += hsum256(aB3);
OUT[(QIN[q + 2] & 0x7ffffu)] += hsum256(aC3);
}
}
#endif
#if MF_LEAFG >= 2
// ---- paired-query leaf: one insert-block load serves two queries ----
for (; q + 2 <= nq; q += 2) {
const int n = ((int)(QIN[q] >> 19) < (int)(QIN[q + 1] >> 19)) ? (int)(QIN[q] >> 19) : (int)(QIN[q + 1] >> 19);
const int nA = (int)(QIN[q] >> 19), nB = (int)(QIN[q + 1] >> 19);
__m256i kvA = _mm256_set1_epi32((int)((u32)(QK0[q]))), kvB = _mm256_set1_epi32((int)((u32)(QK0[q + 1])));
__m256i v0A = _mm256_set1_epi32((int)((u32)(QK0[q] >> 32))), v0B = _mm256_set1_epi32((int)((u32)(QK0[q + 1] >> 32)));
__m256i v1A = _mm256_set1_epi32((int)((u32)(Q12[q]))), v1B = _mm256_set1_epi32((int)((u32)(Q12[q + 1])));
__m256i v2A = _mm256_set1_epi32((int)((u32)(Q12[q] >> 32))), v2B = _mm256_set1_epi32((int)((u32)(Q12[q + 1] >> 32)));
__m256i accA = _mm256_setzero_si256(), accB = _mm256_setzero_si256();
int j = 0;
if (nd >= 3) {
for (; j + 8 <= n; j += 8) {
__m256i IKv = _mm256_load_si256((const __m256i *)(IK + j));
__m256i C0v = _mm256_load_si256((const __m256i *)(IC0 + j));
__m256i C1v = _mm256_load_si256((const __m256i *)(IC1 + j));
__m256i C2v = _mm256_load_si256((const __m256i *)(IC2 + j));
__m256i mA = _mm256_and_si256(_mm256_cmpgt_epi32(kvA, IKv), _mm256_cmpgt_epi32(v0A, C0v));
__m256i mB = _mm256_and_si256(_mm256_cmpgt_epi32(kvB, IKv), _mm256_cmpgt_epi32(v0B, C0v));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v1A, C1v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v1B, C1v));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v2A, C2v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v2B, C2v));
accA = _mm256_sub_epi32(accA, mA);
accB = _mm256_sub_epi32(accB, mB);
}
} else {
for (; j + 8 <= n; j += 8) {
__m256i IKv = _mm256_load_si256((const __m256i *)(IK + j));
__m256i mA = _mm256_cmpgt_epi32(kvA, IKv);
__m256i mB = _mm256_cmpgt_epi32(kvB, IKv);
if (nd > 0) {
__m256i C0v = _mm256_load_si256((const __m256i *)(IC0 + j));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v0A, C0v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v0B, C0v));
}
if (nd > 1) {
__m256i C1v = _mm256_load_si256((const __m256i *)(IC1 + j));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v1A, C1v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v1B, C1v));
}
accA = _mm256_sub_epi32(accA, mA);
accB = _mm256_sub_epi32(accB, mB);
}
}
// per-query tails: each member finishes [j, ((u32)(QIN[.] >> 32))) on its own
{
int jj = j;
__m256i acc = accA;
for (; jj + 8 <= nA; jj += 8) {
__m256i msk = _mm256_cmpgt_epi32(kvA, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0A, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1A, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2A, _mm256_load_si256((const __m256i *)(IC2 + jj))));
acc = _mm256_sub_epi32(acc, msk);
}
if (jj < nA) {
int n = nA;
__m256i msk = _mm256_cmpgt_epi32(kvA, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0A, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1A, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2A, _mm256_load_si256((const __m256i *)(IC2 + jj))));
msk = _mm256_and_si256(msk, _mm256_loadu_si256((const __m256i *)VMASK[n - jj]));
acc = _mm256_sub_epi32(acc, msk);
}
OUT[(QIN[q] & 0x7ffffu)] += hsum256(acc);
}
{
int jj = j;
__m256i acc = accB;
for (; jj + 8 <= nB; jj += 8) {
__m256i msk = _mm256_cmpgt_epi32(kvB, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0B, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1B, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2B, _mm256_load_si256((const __m256i *)(IC2 + jj))));
acc = _mm256_sub_epi32(acc, msk);
}
if (jj < nB) {
int n = nB;
__m256i msk = _mm256_cmpgt_epi32(kvB, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0B, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1B, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2B, _mm256_load_si256((const __m256i *)(IC2 + jj))));
msk = _mm256_and_si256(msk, _mm256_loadu_si256((const __m256i *)VMASK[n - jj]));
acc = _mm256_sub_epi32(acc, msk);
}
OUT[(QIN[q + 1] & 0x7ffffu)] += hsum256(acc);
}
}
#endif
for (; q < nq; q++) {
const int n = (int)(QIN[q] >> 19);
__m256i kv = _mm256_set1_epi32((int)((u32)(QK0[q])));
__m256i v0 = _mm256_set1_epi32((int)((u32)(QK0[q] >> 32)));
__m256i v1 = _mm256_set1_epi32((int)((u32)(Q12[q])));
__m256i v2 = _mm256_set1_epi32((int)((u32)(Q12[q] >> 32)));
__m256i acc = _mm256_setzero_si256();
int j = 0;
switch (nd) {
case 0:
for (; j + 8 <= n; j += 8)
acc = _mm256_sub_epi32(acc, _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j))));
break;
case 1:
for (; j + 8 <= n; j += 8) {
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
acc = _mm256_sub_epi32(acc, msk);
}
break;
case 2:
for (; j + 8 <= n; j += 8) {
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1, _mm256_load_si256((const __m256i *)(IC1 + j))));
acc = _mm256_sub_epi32(acc, msk);
}
break;
default:
for (; j + 8 <= n; j += 8) {
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1, _mm256_load_si256((const __m256i *)(IC1 + j))));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2, _mm256_load_si256((const __m256i *)(IC2 + j))));
acc = _mm256_sub_epi32(acc, msk);
}
break;
}
if (j < n) { // partial block, masked by a table lookup
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1, _mm256_load_si256((const __m256i *)(IC1 + j))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2, _mm256_load_si256((const __m256i *)(IC2 + j))));
msk = _mm256_and_si256(msk, _mm256_loadu_si256((const __m256i *)VMASK[n - j]));
acc = _mm256_sub_epi32(acc, msk);
}
u32 c = hsum256(acc);
OUT[(QIN[q] & 0x7ffffu)] += c;
}
if (!needOut) return;
#if LEAFNB
{
const int NB = (LFAUTO && m <= LFB) ? (m < 8 ? 8 : m) : LFB; // [v4]
u16 cnt[LEAFNB + 2];
for (int b = 0; b <= NB; b++) cnt[b] = 0;
for (int t = 0; t < m; t++) cnt[(int)(((u32)(seq[t] >> 43)) >> (LFSH + LFD)) + 1]++;
#if K11W_BMP
u64 bmp[(LEAFNB >> 6) + 2];
leaf_prefix16_bmp(cnt, NB + 1, bmp);
for (int t = 0; t < m; t++) { u64 v = seq[t]; out[cnt[(int)(((u32)(v >> 43)) >> (LFSH + LFD))]++] = v; }
{
const int NW = (NB + 63) >> 6;
for (int w = 0; w < NW; w++) {
u64 x = bmp[w];
while (x) {
int b = (w << 6) + __builtin_ctzll(x);
x &= x - 1ull;
int hi = (int)cnt[b], lo = b ? (int)cnt[b - 1] : 0;
#if SM7_SNET
/* [SNET] 桶内元素数 s 极小（生产 n 实测：s=2 84.8% / s=3 11.3% / s=4 3.5%，累计 99.6%）⇒
把插入排序换成**定长比较交换网络**（直线代码 + cmov，无数据相关分支/误预测）。
比较键仍是完整 u64，输出是同一个有序数组 ⇒ 与插入排序逐位相同。s>=5 走原插入排序（阈值档）。 */
{
const int s = hi - lo;
if (s == 2) {
u64 a0 = out[lo], a1 = out[lo + 1];
const int lt = a0 < a1;
out[lo] = lt ? a0 : a1;
out[lo + 1] = lt ? a1 : a0;
}
#if SM7_SNET >= 2
else if (s == 3) {
u64 a0 = out[lo], a1 = out[lo + 1], a2 = out[lo + 2];
const int t1 = a0 < a1;
u64 m1 = t1 ? a0 : a1, M1 = t1 ? a1 : a0;
const int t2 = m1 < a2;
u64 m2 = t2 ? m1 : a2, M2 = t2 ? a2 : m1;
const int t3 = M1 < M2;
out[lo] = m2;
out[lo + 1] = t3 ? M1 : M2;
out[lo + 2] = t3 ? M2 : M1;
}
#endif
#if SM7_SNET >= 3
else if (s == 4) {
u64 a0 = out[lo], a1 = out[lo + 1], a2 = out[lo + 2], a3 = out[lo + 3];
const int t1 = a0 < a1, t2 = a2 < a3;
u64 x0 = t1 ? a0 : a1, x1 = t1 ? a1 : a0;
u64 x2 = t2 ? a2 : a3, x3 = t2 ? a3 : a2;
const int t3 = x0 < x2, t4 = x1 < x3;
u64 y0 = t3 ? x0 : x2, y2 = t3 ? x2 : x0;
u64 y1 = t4 ? x1 : x3, y3 = t4 ? x3 : x1;
const int t5 = y1 < y2;
out[lo] = y0;
out[lo + 1] = t5 ? y1 : y2;
out[lo + 2] = t5 ? y2 : y1;
out[lo + 3] = y3;
}
#endif
else if (s > 1) {
for (int t = lo + 1; t < hi; t++) {
u64 v = out[t];
int q = t - 1;
while (q >= lo && v < out[q]) { out[q + 1] = out[q]; q--; }
out[q + 1] = v;
}
}
}
#else
for (int t = lo + 1; t < hi; t++) {
u64 v = out[t];
int q = t - 1;
while (q >= lo && v < out[q]) { out[q + 1] = out[q]; q--; }
out[q + 1] = v;
}
#endif
}
}
}
#else
for (int t = 0; t < m; t++) { u64 v = seq[t]; out[cnt[(int)(((u32)(v >> 43)) >> (LFSH + LFD))]++] = v; }
int lo = 0;
for (int b = 0; b < NB; b++) {
int hi = (int)cnt[b];
if (hi - lo > 1)
for (int t = lo + 1; t < hi; t++) {
u64 v = out[t];
int q = t - 1;
while (q >= lo && v < out[q]) { out[q + 1] = out[q]; q--; }
out[q + 1] = v;
}
lo = hi;
}
#endif
}
#else
for (int t = 1; t < m; t++) {
u64 v = seq[t];
int q = t - 1;
while (q >= 0 && v < seq[q]) { seq[q + 1] = seq[q]; q--; }
seq[q + 1] = v;
}
memcpy(out, seq, sizeof(u64) * (size_t)m);
#endif
}
// NO = needOut, RK = rekey. XN is kept only for signature compatibility (unused).
// The cross key comes from the event's OWN embedded field (bits 21..41 == XD[d+2][id], see
// the header comment), so the rekey gathers nothing at any level; and the cross EMBEDS
// XE[eid(v)] = XD[d+3][id] into bits 21..41 for the next level. `c` is only built for the
// entries that are actually kept (the old code built it unconditionally and threw it away).
#define MKE_CROSS(V, EMB) ((RK ? (((((V) >> 21) & 0x1FFFFFull) << 43) | ((V) & 4398048608255ull)) \
: ((V) & 4398048608255ull)) \
| (GAT ? ((u64)(EMB)[eid(V)] << 21) : 0ull))
#define MF_EMB_NONE 0
#define AX_CROSSPF 8 /* [a1x] prefetch distance for the MKE_CROSS gather */
template<int NO, int RK, int GAT>
static inline void merge_loops(const u64 *retA, int h, const u64 *retB, int r,
u64 *out, u64 *cross, const u32 *XN, const u32 *XE, int &cx) {
(void)XN;
/* [a1x] pointer-cursor form + one-step-ahead prefetch of the MKE_CROSS gather.
Bit-identical: `cross[cx]` is still stored unconditionally and `cx` bumped by
`keep_test`; the two tails keep the same role test. The prefetch only reads the
candidate ids of the two ORDERED input runs (RET[x + 8]), so it cannot change any
value; `GAT` is a compile-time constant, so the levels that do not rekey/gather pay
zero (they have XE == 0 and would dereference null otherwise). */
const u64 *pa = retA, *const pa_end = retA + h;
const u64 *pb = retB, *const pb_end = retB + r;
u64 *po = out;
u64 *pc = cross;
/* [MRG3] single-bound merge loop: retA[h] == +inf is never taken from A, so only B's
bound is needed; once A is exhausted the body degenerates EXACTLY into the old B-tail
(takeA == 0 => keep == 1 - role, i.e. the cross store happens for queries only).
Same events in the same order, same cross stream => bit-identical output. */
while (pb < pb_end) {
if (GAT) {
__builtin_prefetch(&XE[eid(pa[AX_CROSSPF])], 0, 3);
__builtin_prefetch(&XE[eid(pb[AX_CROSSPF])], 0, 3);
}
/* [k11c2-SELADV] branchless select+advance. BEFORE: `t = ea<eb; pa += t; pb += 1-t;`
made gcc 9.3 emit cmp / setb / sbb / and / add (pa) and mov/sbb.. (pb) between the
compare and the third CF consumer (`cmovbe` for v) => the AND **clobbered CF** and gcc
had to re-issue the *same* `cmpq %rax,%r9` a second time (ring had 40 insns, two cmpq).
AFTER: CF is read only by cmov/sbb (neither writes flags), so one compare serves all
three consumers; `sbbq tt,tt` materialises -takeA (full width, CF preserved) for the
`keep` bit. Ring 40 -> 36 insns and the load->cursor carried chain drops 9/8 -> 6/6
levels (the ring was shown by the DCX ablation to be carried-chain priced).
Bit-identical: same events in the same order, same `cross` stream, same `cx`. */
u64 ea, eb, tt, t1, t2;
__asm__ ("movq (%[pa]), %[ea]\n\t"
"movq (%[pb]), %[eb]\n\t"
"cmpq %[eb], %[ea]\n\t"
"sbbq %[tt], %[tt]\n\t"
"leaq 8(%[pa]), %[t1]\n\t"
"cmovb %[t1], %[pa]\n\t"
"leaq 8(%[pb]), %[t2]\n\t"
"cmovae %[t2], %[pb]\n\t"
"cmovb %[ea], %[eb]\n\t"
: [ea] "=&r" (ea), [eb] "=&r" (eb), [tt] "=&r" (tt),
[t1] "=&r" (t1), [t2] "=&r" (t2), [pa] "+r" (pa), [pb] "+r" (pb)
:
: "cc");
const u64 v = eb;
if (NO) *po = v;
++po;
*pc = MKE_CROSS(v, XE);
pc += (size_t)(1u - (((u32)(v >> 42) ^ (u32)tt) & 1u));
}
while (pa < pa_end) {
const u64 v = *pa++;
if (NO) *po = v;
++po;
if ((v >> 42) & 1) *pc++ = MKE_CROSS(v, XE);
}
while (pb < pb_end) {
const u64 v = *pb++;
if (NO) *po = v;
++po;
if (!((v >> 42) & 1)) *pc++ = MKE_CROSS(v, XE);
}
cx = (int)(pc - cross);
}
// ---- terminal level (D == KT-1): every insert-before-query pair qualifies ----
template <int KT, int D, int NO>
static void solve_b(u64 *seq, int m, u64 *out, TB<true>) {
(void)out;
int cnt = 0;
for (int t = 0; t < m; t++) {
u64 v = seq[t];
if ((v >> 42) & 1) cnt++; // insert (bit42 = 1)
else OUT[eid(v)] += (u32)cnt; // query
}
}
// ---- general level (D < KT-1) ----
template <int KT, int D, int NO>
static void solve_b(u64 *seq, int m, u64 *out, TB<false>) {
if (m <= KG_BASE) {
base_case_t<NCL< KT - (D + 2) >::v>(seq, m, D, out, NO);
return;
}
int h = m >> 1, r = m - h;
u64 *save = ABtop;
/* [MRG3] sentinel + zeroed slack: retA[h] = +inf makes the A run self-terminating for the
merge loop (takeA is false for it), and AX_CROSSPF+2 zero-filled entries behind each run
make the one-step-ahead gather prefetch loads always in-bounds: a zero word gives
eid == 0 -> &XE[0], which is hard-wired safe. Slack is never read as an event. */
u64 *retA = ABtop; ABtop += h + (AX_CROSSPF + 2);
u64 *retB = ABtop; ABtop += r + (AX_CROSSPF + 2);
solve_t<KT, D, 1>(seq, h, retA);
solve_t<KT, D, 1>(seq + h, r, retB);
u64 *cross = ABtop; ABtop += m + 1;
const int RK = (D + 2 <= KT - 1) ? 1 : 0; // promote this level's nk into the key
const int GAT = (D + 3 <= KT - 1) ? 1 : 0; // gather XD[D+3] into the next nk slot
const u32 *XN = RK ? XD[D + 2] : 0; // kept for signature compatibility
/* the level-(D+1) key/embed needs XD[D+3]; embed it in this level's cross entries */
const u32 *XE = GAT ? XD[D + 3] : 0;
int cx = 0; /* ia/ib/t live inside merge_loops */
/* [MRG3] plant the sentinel and the zero-filled slack BEFORE the merge reads them. */
retA[h] = ~(u64)0;
{ int zi = 1; for (; zi <= AX_CROSSPF + 1; zi++) retA[h + zi] = 0; }
{ int zi = 0; for (; zi <= AX_CROSSPF + 1; zi++) retB[r + zi] = 0; }
merge_loops<NO, RK, GAT>(retA, h, retB, r, out, cross, XN, XE, cx);
if (FUSE_OK && D == KT - 3) {
u32 *dirt = (u32 *)ABtop; ABtop += (cx + 3) / 2 + 1;
ctr_solve(cross, cx, dirt);
} else {
u64 *cres = ABtop; ABtop += cx;
solve_t<KT, D + 1, 0>(cross, cx, cres);
}
ABtop = save;
}
template <int KT, int D, int NO>
static inline void solve_t(u64 *seq, int m, u64 *out) {
if (m <= 1) return;
solve_b<KT, D, NO>(seq, m, out, TB<(D >= KT - 1)>());
}
static u32 *g_ord, *g_x;
static void sort0(int n) {
const u32 *X0 = XD[0];
u32 *cnt = g_x;
memset(cnt, 0, sizeof(u32) * (size_t)(n + 1));
for (int i = 0; i < n; i++) cnt[X0[i] + 1]++;
for (int i = 0; i < n; i++) cnt[i + 1] += cnt[i];
for (int i = 0; i < n; i++) g_ord[cnt[X0[i]]++] = (u32)i;
}
template <int KT>
static void run_t(int n, const u32 **x, u32 *out) {
LFSH = 0; LFD = 0;
CTN = (u32)n; // [CTRR]
for (int d = 0; d < KT; d++) XD[d] = x[d];
OUT = out;
ABtop = AB;
if (n <= 1) return;
// The official 1010a instance is checked by the judge itself. Its
// last-coordinate multiplicity is below the fused u8 counter limit.
FUSE_OK = (KT >= 4 && n > 2 && (u32)n < CT_MAXV);
if(FUSE_OK){
const u32*XL=XD[KT-1];size_t count=((size_t)n+31)/32;
memset(CT1,0,(count+8)*sizeof(u16));
for(int i=0;i<n;i++)if(++CT1[XL[i]>>5]>255){FUSE_OK=0;break;}
memset(CT1,0,(count+8)*sizeof(u16));
}
{
int bit = 0;
while ((n >> bit) >= LEAFNB && bit < 30) bit++;
LFSH = bit; LFD = 0;
LFB = (int)((((u32)(n - 1)) >> (LFSH + LFD)) + 2u); // [v4]
if (LFB > LEAFNB) LFB = LEAFNB;
if (LFB < 8) LFB = 8;
}
sort0(n);
const u32 *X0 = XD[0], *X1 = XD[1];
const u32 *nk2 = (KT >= 3) ? XD[2] : X0; /* dim 2's coordinate, zero-only when K < 3 */
u64 *ev = AB; // top-level event array: 2n entries
int m = 0, g = 0;
for (int v = 0; v < n; ++v) {
int g1 = (int)g_x[v];
if (g1 == g) continue;
int cnt = g1 - g;
for (int t = g; t < g1; t++) {
int id = (int)g_ord[t];
u32 key = X1[id], nk = nk2[id];
ev[m + t - g] = mk(key, 1, id, nk);
ev[m + cnt + t - g] = mk(key, 0, id, nk);
}
m += cnt * 2;
g = g1;
}
ABtop = AB + m;
u64 *res = ABtop; ABtop += m;
solve_t<KT, 0, 0>(ev, m, res);
}
} // namespace kg
static u64 g_arena[KG_ARENA];
static u32 g_ord_st[1048576], g_x_st[1048576];
static int g_ready = 0;
static void setup() {
if (g_ready) return;
g_ready = 1;
kg::AB = g_arena;
kg::g_ord = g_ord_st;
kg::g_x = g_x_st;
}
void count_4d(int n, const unsigned *x[4], unsigned *out) {
setup();
memset(out, 0, sizeof(unsigned) * (size_t)n);
kg::run_t<4>(n, (const unsigned **)x, out);
}
void count_5d(int n, const unsigned *x[5], unsigned *out) {
setup();
memset(out, 0, sizeof(unsigned) * (size_t)n);
kg::run_t<5>(n, (const unsigned **)x, out);
}
#pragma GCC pop_options
// ================ 附录：闸门记录（本地 g++-15 / 判题端 probe 台架）=====================
// 【闸门 1：暴力对拍（`work/a15x_vfy.py` 生成的独立 oracle，O(n^2 k)，零共享代码）】
// k=5/4 × n∈{1,2,3,7,33,200,777,2000} × 8 种分布（均匀/2 值/全 0/降序/升序/8 值/置乱/低值域）
// ⇒ **全部 0 mismatch**。
// 【闸门 2：真实规模逐位对拍】k=5 n=300000 均匀分布下 out[] 的 FNV-1a
// （`a15x_vfy.py` 自带数据生成器）：本发与基座 **完全相同**（`work/a15x_vfy_*.cpp` 两件对拍）。
// 【闸门 3：同进程双臂 checksum】`work/a1_ab.py` 生成的 base/kg1536 双臂件（判题端同款数据）
// ⇒ 两臂 checksum **均为 2818095627**，与历史值一致 ⇒ 改动不改答案。
// ================================================================================================
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 287.897 ms | 27 MB + 1000 KB | Accepted | Score: 100 | 显示更多 |