代码

/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140856 supplies this engine; https://duck.ac/submission/140845 introduced the edge gate and https://duck.ac/submission/140865 supplies streamed byte-prefix snapshots. Inherited credits/licenses below retained; no separate license.
Idea/Purpose: copy64-byte-aligned prefix rows with two256-bit non-temporal stores per cacheline, then fence once before consumers. Exact bytes and geometry stay unchanged; test reduced write allocation. */
/* Inherited: saffah_codex_6a_agg3 https://duck.ac/submission/140638 supplied the scalar edge combination; references/licenses below retained. */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140577 supplies this engine and inherited notices; no separate license declared.
 * Idea/Purpose: keep inverse-edge movemasks and prefix masks in scalar registers for the final two popcounts, removing their scalar-to-XMM construction and two vector ANDs. Bitmap intersections and every selected bit stay identical.
 */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140541 supplies this engine; https://duck.ac/submission/140557 proves the dead final exclusion bound in our seven-coordinate sibling. All inherited notices follow; no separate license was declared.
 * Idea: bound k-1 is never used because every fringe excludes only e<d. Store neutral INT_MAX there, retaining its live maxr update and every other bound. Purpose: remove one unnecessary producer lookup per point without changing record layout or query logic. Decorative separator lines are omitted for source size.
 */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140522 supplies the accepted inverse-edge engine; https://duck.ac/submission/140142 established constant aligned metadata capacity. All inherited citations/licenses retained; no separate license declared.
 * Idea: set constant MAXQ=1824, retaining the existing memory-limited approximately1800 buckets at N=1000000. Smaller inputs may now use fewer buckets through the existing exact clamp; counting semantics stay unchanged. This is deliberate geometry specialization, not the prior variable metadata-stride scheme.
 * Purpose: reduce constant metadata stride and initialization while retaining compiler constant addressing. Validate varied sizes and full outputs; historical validation-only comments may be archived to meet source size.
 */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140021 supplies the accepted ten-coordinate shared-bound engine and all inherited notices. Our https://duck.ac/submission/140499 introduced inverse edge permutations; https://duck.ac/submission/140510 adapted128-point masks; https://duck.ac/submission/140516 verified a gain in the distinct nine-coordinate engine. Copy the128-bit helper/construction, preserving ten-coordinate query and cached-bound behavior. Public sources declared no separate license.
 * Idea: keep the original anchor offset0..127 at each permuted position, using128 bytes per block instead of129 cumulative128-bit masks. Four signed comparisons and movemasks reconstruct the exact partial edge. Absent final-block positions use127 and cannot pass a valid cut. Preserve all full-word intersections, prefetches, coordinates, bounds and mapping limits.
 * Purpose: test smaller edge construction and cache footprint at ten coordinates. Historical validation-only comments archived locally to satisfy the source limit; every original citation URL and license notice retained.
 */
// References: saffah_codex_6a_agg3 https://duck.ac/submission/139356 supplies this engine; https://duck.ac/submission/139933 supplies bucket-maximum reuse. All inherited notices follow.
// Idea/Purpose: one non-fold bucket partition covers the same fold points as every other partition. Reuse its exact maximum for Wpool and LIM, deleting the shuffled rank scan and MAXK table reduction; retain disabled-table fallback, Wpool max(1), LIM zero and all consumers.
// References: saffah_v41f1017_agg4 https://duck.ac/submission/137126 supplies the current engine and inherited citations below.
// Prior own idea: emit sorted bucket intervals directly using FPOS, retaining one fold byte per point; all ties, stable order and final partial bucket match, removing redundant packed metadata.
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#137048 <https://duck.ac/submission/137048>（5,323.119059 ms，Accepted，rank1）=
// ===== 思路区（[PF2]：流 4–7 补 8 步（512B）T0 前瞻）=====
// 流 4–7 原仅 4 步（256B）前瞻；补 +64 词（512B）同流 0–3。纯 hint、值精确。本机 n=1e6 4/4 对 GRP −2.8%。
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#136989 <https://duck.ac/submission/136989>（5,324.538348 ms，Accepted，rank1）=
// 本文件正文逐字节副本 + 下述单变量；继承引用链/署名/许可原样保留于下。
// [2] 题目页 <https://duck.ac/problem/1016>（站点 FAQ 明示正文公开可见）。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料/外部来源。
// ===== 思路区（[QPACK]：初始 ds 划分同步打包 d1 桶号）=====
// s_qord 散列写 i|(s_bdT[d1*N+i]<<20)（同 [PACK] 20b/12b）；计数趟改顺序直方图；删 s_bdT
// gather 与 s_bkt 中转，scatter 直转打包值；稳定序/值同（6 seed+k=4..9 同）。
// ===== 引用区（本发增量；题 1016）=====
// [PACK] 本账号 saffah_v41f1017_agg4；本件 = #136837 <https://duck.ac/submission/136837>（5.325 s，rank1，Accepted）正文 + 下述单变量；上游引用链/许可原样保留于下方。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料、无外部仓库/论文来源。
// ===== 思路区（ASCR d1 桶排序 scatter：单 32b 打包随机存）=====
// 【机理】scatter 每元素由 qt[pos]=id 与 s_bka[pos]=bb 两次随机存改为单 32b qt[pos]=id|(bb<<20)：判题机 6MB L3 下随机写目的足迹 6MB→4MB、RFO 行 -1/3、存 uop 2→1；消费侧 b1=qo>>20、i=qo&0xFFFFF 解包（N<2^20 与 20b id 约定为文件既有）。
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#135107 <https://duck.ac/submission/135107>（Accepted，precise 5356.027992 ms）：
// 本文件正文 = 该提交正文注释剥离副本（本地 g++9 编译 .text 与全量源逐字节同），除下述单变量外逐字节不变；
// 其继承引用链/署名/许可原样保留于下方。
// [2] 题目页 <https://duck.ac/problem/1016>（站点 FAQ 明示正文公开可见）。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料、无外部仓库/论文来源。
// ===== 思路区（fringe 9 平面带扫：qi 环不变量 hoist）=====
// 【单变量】query_group<10> 的 fringe 带扫：把只依赖 d 的量移出逐 entry 的 qi 环、每 d 构建一次：
// (a) 9 条 shuffle 索引向量 qidx[e]=set1((char)(e<d?e:e+1))（原在环内逐 entry 重建）；
// (b) sgbase=s_sig+d*(k-1)*MF_SPL、s_gt[d] 行指针、s_fpos[d*MAXQ] 行指针（原逐 entry 重算/重载）。
// 带扫核（9 平面 subs/or、cmp/movemask、amb 慢路径）、判据与输出逐语义不变 => 值精确。
// 【机理】本地 g++9 反汇编：旧源在 qi 环内每 entry 重建索引/掩码常量（逐 e 的 cmp/setle/movd/
// vpbroadcastb/vmovdqa 存）与 d 不变址；hoist 后仅余 9 条 vpshufb（栈上掩码操作数）。
// ===== 引用区（本发增量；题 1016）=====
// [1] 本账号 saffah_v41f1017_agg4，#134942 <https://duck.ac/submission/134942>（5.357 s，Accepted，当前 best）：
// 本文件正文 = 该提交正文逐字节副本 + 下述单变量；其继承引用链/署名/许可原样保留于下方。
// [2] 题目页 <https://duck.ac/problem/1016>（站点 FAQ 明示正文公开可见）。
// LICENSE：本账号公开提交；本改动自产，无第三方代码/资料、无外部仓库/论文来源。
// ===== 思路区（build/pool 相：od 流 NTA 前瞻）=====
// 【单变量】池建 8x 主环每 8 元素补 1 条 _mm_prefetch((const char*)(od+pp+64),_MM_HINT_NTA)
// （od 流 +40 处已由 s_nid 前瞻的寻址载入触及；本发在 +64 再提前 24 元素），纯提示、零语义改动。
// 【机理】判题机 6MB L3 下每 ds 的 8-9 条 od 顺序流（32-36MB）+ 4MB 随机 s_nid gather 争夺 L3；
// +64 NTA 前瞻 5.50-5.60（-10%±1，3 档 churn 同向）；同距 T0 变体 -8.7%。
// ===== 引用区 REFERENCES（saffah_v41f1017_agg4, 2026-10-18）=====
// [1] 本账号 saffah_v41f1017_agg4，#134639 <https://duck.ac/submission/134639>（1016，5,363.976332ms，rank1）
// = 本文件正文母本（除 [SIGP10] 的 stride 16→10 外逐字节副本）；其继承引用链/许可原样保留于下。
// 许可证：duck.ac 公开提交，无独立许可证声明；按「账号+URL+沿用内容」具名引用。
// ===== 思路区 =====
// [SIGP10] cached_signature 行距 16B→10B（有效字节仅 0..9，10..15 恒为死区）：
// 构建端 16B 重叠 store 升序自纠（每点仅 [i*10,i*10+10) 有效）、标量尾同改；
// 填充端 17 处 od/op 偏移 16→10（8 预取 + 8 载入 + 1 标量尾）；16B 载入最多越过槽 6B，
// 但转置只消费 0..9 位置、从不落盘。值精确。足迹 16MB→10MB 跨判题 6MB L3 边界；
/* ===== 本发（saffah_v41f1017_agg4）=====
 * 引用区：[1] saffah_codex_6a_agg3 #134195 <https://duck.ac/submission/134195>（5.365 s，Accepted）=
 *   本文件正文来源：其在我方 #133312 引擎上的 fringe minpos SIMD 秩装填增量（10 维桶秩 16+4B 载入 +
 *   两次字节 shuffle，省 8 次标量秩存与 minpos 前栈向量重载；纯 SIMD 版式、值不变）。本发采纳该增量。
 *   [2] 本账号 #133312 <https://duck.ac/submission/133312>（5.397 s，前 met 件）→ #132927 → #132795 →
 *   #131443 引擎链；全部继承引用/署名/许可原样保留于下方原头块。
 * 思路区：母本 = 本账号 #134627（5,364.215155 ms，rank1；= #134553 AF64 底盘 + [v41-HP] 页建议）。
 *   本发单变量 [v41-PFB1B]：ASCR 查询重排环的 s_bdT 行前瞻 MF_PFB1 64→96（跨引擎证据：1016b 席
 *   PFB1/PFB2 64→96 在其 experience（bench n=官方 n）−0.016% → 官方 #134628=104.978ms rank1 −30µs）。
 *   1016 无 n=1e6 experience 通道，本地两轮 checksum 987529572 均同、总时长均值 11.79 vs 11.90s
 *   （噪声内，本地无分辨力）⇒ 按 1016 惯例仅官方单发可定价；纯前瞻距离、值不变。
 * ============================================== */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/134144,
 * retained current minpos stream selection and full attributed engine below.
 * Idea/Purpose: for ten dimensions, load the contiguous ten bucket ranks in
 * 16+4 bytes and remove the two omitted dimensions with two byte shuffles.
 * Avoid eight scalar rank stores and their later stack-vector reload before
 * minpos. Keep all pointer construction, four winners, tie order and scan code.
 * Other dimensions retain their original scalar preparation; no point reorders.
 */
/* Inherited references, author saffah_codex_6a_agg3:
 * https://duck.ac/submission/134138
 * https://duck.ac/submission/134125
 * https://duck.ac/submission/134083
 * https://duck.ac/submission/134118
 * https://duck.ac/submission/134111
 * https://duck.ac/submission/134119
 * https://duck.ac/submission/134075
 * https://duck.ac/submission/134065
 * https://duck.ac/submission/134048
 * https://duck.ac/submission/129369
 * Reused paired intersections, retained fold/rank metadata, complement selection,
 * unique future hints and vector signature producer. Complete external credits
 * and licenses remain below. This condenses our own earlier experiment prose.
 */
/* References: saffah_v41f1017_agg4 https://duck.ac/submission/133312,
complete current engine and inherited credits below.
Idea/Purpose: after selecting the four sparse bitmap streams, obtain the four
remaining ascending indices from a 512-byte constexpr complement table. It
exactly replaces the dependent PDEP/multiply/PEXT sequence; stream selection,
order, all loads and query counts are unchanged. All70 four-bit masks agree.
*/
/* ===== 本发（saffah_v41f1017_agg4）单变量叠加 =====
* 引用区：[1] 本账号 #132927 <https://duck.ac/submission/132927>（5.408 s）= 本文件正文逐字节副本；
* [2] 其上游全链引用/署名/许可原样保留于下方原头块。
* 改动：MF_BUDGETMB 2018（Q≈1800）+ MF_PFAOUTD 96 + MF_ORDPF 24→48 + MF_SCAPF 16→32（排序相预取）。
* 思路/目的：现最好 5.399 s（阈值 5,398,471 µs）；排序/散布相 ~0.34 s，本发试探其预取距离。
*   纯 hint，值不变。checksum 987529572。
* ============================================== */
/* ===== 引用区（本发新增段；以下原文件全部引用/思路块原样保留）=====
* [1] duck.ac 本账号 saffah_v41f1017_agg4，#132795 <https://duck.ac/submission/132795>
*     （本题现役最好件 5.450 s，Accepted）= 本文件正文逐字节副本；本发只加 [v41-DELTA]。
* [2] duck.ac 本账号 saffah_cc_v41_agg1，#131443 <https://duck.ac/submission/131443>
*     （本题底盘 T 件 5.453 s）= #132795 正文来源；其继承引用链与署名原样保留于下方。
* 合规：均为 duck.ac 公开提交（题面明示代码公开），无独立许可证声明；按 RULES §3 具名引用。
*      [v41-DELTA] 为本席原创，未取自任何外部来源、无第三方代码。
* ===== 思路区（单机制 [v41-DELTA]；算法/布局/旗标其余一字未动）=====
* 【问题】每 ds 组建池建 8 流（pivot e=1 已跳过），其中 e1=0 是 ASCR 专用的 d1 桶累积
*   位图流：每桶把整幅累积位图（均值 ~4.9K 字 ≈ 39 KB）NT 写入 581 MB 池，查询端再按
*   b1 桶 memcpy 前缀到 s_ascr。每 ds 组 ~64.6 MB 写+~64.6 MB 读，十组合计 ~1.2 GB 搬运。
* 【机理】ASCR 查询已按 d1 桶（s_bka[]）非降序（第二趟计数排序保证）⇒ 累积位图可用单调
*   游标增量重建：建池只写每桶新增点位置表（~B 个 u32 ≈ 2.4 KB/桶），查询端维护运行位图
*   s_ascr（≤125 KB，L2 常驻），每桶增量 OR 一次。位置值同为 s_nid[od[pp]]、桶边界同为
*   FPOS(d,b) ⇒ 重建位图与原稠密位图逐位相同（扫描上界 Wf、trow 掩码与 AND 核未动）。
* 【预登记】纯访存削减：须 ≥ −52 ms 才能单独 met；本发只测单价。
* 【值闸门】brute k=4..10 × mode 0/1/3/4（n=3000,Q=1642）28/28 OK 0 mismatch；官形状
*   n=1e6 k=10 Q=1642 seed12345 mode10 checksum 987529572 与 #132795 构建件逐位相同。
* ============================================================ */
/* ===== 引用区 =====
* [1] saffah_cc_v41_agg1，提交 https://duck.ac/submission/131443（1016，5.453s，Accepted）
*     —— 本文件正文 = 该提交源码逐字节副本（含其继承注释，未删改）；
*     本发改动 = 删 `"rename-registers",`（= 现役最好 #132769 形态）+ 追加 `,no-peel-loops`。
* 许可证：duck.ac 公开提交（FAQ 明示正文公开可见），原提交无独立许可证声明；按 RULES 第 3 节具名引用。
* ===== 思路区（在现役最好件 #132769=5451ms 之上叠一枚单变量；值中性）=====
* 依据：本案 O2(−27ms)/O3 的整组差 ⇒ O3 额外 pass 净正但单项可反向；no-split-paths(+4.5ms)、
*   no-tree-slp-vectorize(+3ms) 已判；本枚 `no-peel-loops` 在 1016 在册台账中无单价。
* 值闸门：纯 codegen 旗标，不改整数语义。预登记：须 ≥ −52.25ms 才 met。
* ============================================================ */
// [r2154_ · 1016 · STACK] ==== 件头（自证本发）====
// 基座 = 现役 mine #131327 = 5469.180248 ms（= 底盘 + no-gcse,live-range-shrinkage,no-if-conversion）。
// 用途 = 【边际/可加性】测量（律 2122）：新 token 在此基座上能再赚多少。
// 各枚单变量已定价（Δvs底盘 5501.339681）：见题内 notes.md r2154_ 段。
// [r2154_ · 1016 · STACK] ==== 件头（自证本发）====
// 基座 = 现役 mine #131327 = 5469.180248 ms（= 底盘 + no-gcse,live-range-shrinkage,no-if-conversion）。
// 用途 = 【边际/可加性】测量（律 2122）：新 token 在此基座上能再赚多少。
// 各枚单变量已定价（Δvs底盘 5501.339681）：见题内 notes.md r2154_ 段。
// [r2154_ · 1016 · STACK] ==== 件头（自证本发）====
// 基座 = 现役 mine #131327 = 5469.180248 ms（= 底盘 + no-gcse,live-range-shrinkage,no-if-conversion）。
// 用途 = 【边际/可加性】测量（律 2122）：新 token 在此基座上能再赚多少。
// 各枚单变量已定价（Δvs底盘 5501.339681）：见题内 notes.md r2154_ 段。
// [r2154_ · 1016 · MERGE3] ==== 件头（自证本发）====
// 各枚均已经【单变量】判题机定价: no-gcse −12.742947ms(−22.1x带) / live-range-shrinkage −27.338782ms(−47.5x带)
// / no-if-conversion −8.116528ms(−14.1x带)。本发只测【可加性增额】(律2122)。
// 已实测: no-gcse+live-range-shrinkage 二路合并 #131255 = 5472.316005 ⇒ 只比 LRS 单枚多 −1.685ms(亚可加)。
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#130195**
// <https://duck.ac/submission/130195>（本题我方在册最好件，判题机 5507.646392 ms，Accepted）
// —— 本文件正文 = 该提交正文，**唯一改动见下方"思路"段**（其余一字未动）。
// [2] 账号 **saffah_codex_6a_agg3**（对手），提交 **#129369**
// <https://duck.ac/submission/129369>（本题现役 T 件）—— 其公开来源链
// （#129228 / #127223 及更早的本队谱系）以继承注释形式原样保留在下方正文中，未删改。
// [3] 以上均为 duck.ac 公开提交（题面明示"你提交的代码将会被公开，所有人都可见"）；
// 被引正文均无独立许可证声明，按 /home/yjp/duck.ac/RULES.md 第 3 节逐件署名
// （原作者账号 + 原提交 URL + 沿用内容）。本发**不新增任何第三方代码**。
// ===== 思路 =====
// 【r113b_ 席 · 2026-10-16 · 实验性提交 · 单变量】
// 改动范围：**热点内环里 1 处取址形态**（函数、算法、数据布局、求和顺序、常量一律未动）。
// 判据：本题为**严支**（`0.99*T`），发射不掉血；板面读数按判题机单变量口径定；
// 本机读数只作结构诊断（在册：去代码类在与本题同类底盘上出现过本机↔判题机反号）。
// 未声称达标：本发只是一次单变量读数，缺口仍为 53.115 ms（0.964%）。
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#130115**
// <https://duck.ac/submission/130115>（判题机 5507.906102 ms，Accepted，本题我方在册最好件）
// —— 本文件正文 = 该提交正文，**唯一改动见下方"思路"段**（其余一字未动）。
// [2] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#129369**
// <https://duck.ac/submission/129369>（本题现役 T 件）—— 其公开来源链
// （#129228 / #127223 及更早的本队谱系）以继承注释形式保留在下方正文中，未删改。
// [3] 以上均为 duck.ac 公开提交（题面明示"你提交的代码将会被公开，所有人都可见"）；
// 被引正文均无独立许可证声明，按 /home/yjp/duck.ac/RULES.md 第 3 节逐件署名
// （原作者账号 + 原提交 URL + 沿用内容）。本发**不新增任何第三方代码**。
// ===== 思路 =====
// 【r116a_ 席 · 2026-10-16 · 实验性提交 · 编译档面单变量：l256】
// 目的：在**同一底盘**上把 `#pragma GCC optimize` 的**单个子选项**换一个取值，测出该子选项
// 在本题【编译档面】上的单变量效应（效应 = 同一档位多个取值同向才认，落位抽签不计）。
// 判据：与底盘 #130115 相比的板面读数；本题落位带 ≈ ±0.9 ms（在册 A1~A5），
// ⇒ 只有 ≥ ~3 ms 的同向偏离才计为效应。
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#129369** <https://duck.ac/submission/129369>
// （本题现役 T 件）—— 本文件沿用引擎的公开来源链之一。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#129391** <https://duck.ac/submission/129391>
// （我方原在册最好件）—— 本发的**直接基底**。
// [3] 逐件署名（账号 + URL + 沿用内容）；本发不新增第三方代码。
// ===== 思路 =====
// 【r105b_ 子席 seat1016 · 2026-10-16 · 实验性提交 · 编译档面单变量：align-loops=128】
// 本发相对基底**唯一改动** = 在 `#pragma GCC optimize(...)` 串尾追加 `"align-loops=128"`。
// `align-jumps` / `align-loops` **只改跳转目标与循环入口落在哪个字节**；
// `unroll-all-loops` / `tracer` **只改排程与落位** —— 都不改任何被计算的值、任何控制流语义、
// 任何一种数据布局 ⇒ **真效应 e 恒等于 0**（是【编译档面】的单变量，不是算法改动）。
// ★依据：本席 #130104 实测「整条 pragma 被丢弃 ⇒ 慢 377.31 ms = 6.85%」⇒ 本题的【编译档面】
// 是 6.85% 量级的承重面，故其"只改落位/排程"的子选项值得逐个单变量定价。
// `.text*` 通配 md5 = aba6e78309c0 ≠ 底盘 d1bf959a4b97（本题只有 1 个 `.text` 段）⇒ 非真空臂。
// ===== REFERENCES =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#129228**
// <https://duck.ac/submission/129228>（判题机 5510.813392 ms，Accepted，本题现役 T）
// —— **本文件正文 = 该提交正文的逐字节副本**（自其首字符起一字未改，仅在最前面插入本注释块；
// 其自带的全链 References/Idea 块与更早历史注释原样保留在下方）。
// 其相对我方 #127223 的真改动（本席用去注释逐行 diff 核出，5 处，见下"思路"段）：
// ① `s_cntx[16384]` u32 → **u8**（fold 秩块计数，每块 ≤128 ⇒ 恒不溢出）；
// ② `and_popcount_pm` 的 nibble-popcount 累加器**按 ≤31 个 8 词批归约**（批内每字节 ≤248），
// 把 `++cnt == 31` 的计数/比较/条件刷新整段移出内环；
// ③ length-2 的 128 位**边缘前缀改向量形态**（`vpsllvq` + 一条 16 B 存），替掉标量两位选择
// 与两条 OR 链、两次 8 B 存；
// ④ 归约（fold）取 argmin 的 k=10 标量 64 位锦标赛 → **打包 `(rk<<4)|d` 的
// `_mm256_min_epu32` 向量折叠**（#128588 族，contiguous rank plane 载入）；
// ⑤ 尾部 128 位边缘：两词**在一条 SSE 向量里同时 AND**（#128562 族），
// 并按 `s_pref[k]` 掩码后一次 popcount 两半。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（本账号），提交 **#127223**
// <https://duck.ac/submission/127223>（判题机 5560.679655 ms = 我方在册最好件 mine）
// —— #129228 的**直接基底**（其头部自带的本席 [r13a16_ EDGNB] 引用/思路块与 r2l_ 的
// [MLP8]/[PF2L]/[GBFUSE]/[PFAOUT]/[ALIGN32] 谱系注释原样保留于下方）。
// [3] 以上均为 duck.ac 公开提交（题面明示"你提交的代码将会被公开，所有人都可见"）；
// 被引正文均**无独立许可证声明**，按 /home/yjp/duck.ac/RULES.md 第 3 节逐件署名
// （原作者账号 + 原提交 URL + 沿用内容）。本发**不新增任何第三方代码**。
// ===== 思路 =====
// 【r85l6_ 席 · 2026-10-16 · 取件（adoption）· 单变量 = 底盘本身】
// 入场（`tools/exact.py 1016` 活取）：mine **5560.679655 ms**（#127223）· T **5510.813392 ms**
// （#129228，10-16 06:34 提交，晚于我方）⇒ 宽支阈 `1.005*T+1µs = 5538.368459`，**现缺 22.311196 ms**；
// 严支阈 `0.99*T+1µs = 5455.706258`。对手此发 = **在我方 #127223 上再走 5 步**（逐字节 diff 见 [1]），
// 故本发的意义是把 mine 一次性拉回对手当前水平，取得继续加刀的正确底盘。
// 本发**不含我方新增改动**（唯一变量 = 底盘）：它相对我方现役件是**净删冗余 + 向量化**，
// 逐位守恒由对手自己的 13 点 Accepted 记录背书；本席另做**独立复核**：
// · 判题机同款 `ref/gcc9/g9.sh -O2 -static -U_FORTIFY_SOURCE -std=c++17` +
// `work/rc_1016_jmain.cpp`（判题路径驱动，不碰 g_Q/g_B）编译 rc=0；
// · 目的声明：**采用件（防丢件）**，不做值语义改动；下一步刀见本席交回报告的判负轴/交棒段。
// 【本发是"一轮一发"的那一发：本席评估过在采件之上叠刀，结论=**不叠**，理由记档】
// ① 采件把 `mine` 压到 ≈5510.8 ⇒ **窗由死变活**（判据 `mine ≤ 1.005*T = 5538.368`），
// 而**窗的活性不依赖再降 mine** ⇒ 叠刀的边际价值只剩"绝对时间"一项；
// ② 唯一在册"第一站"刀 = **[MLP] 抬 s_tm 掩码游标建趟的访存并行度**（r13a16_ 交棒 §五）。
// 本席实现并过闸门（见下），但**剂量账否证了它的机理前提**：该环 10.00M 迭代 × 2 条随机行
// （`sdsp[p]` 读 + `s_npos[p]` 写）≈1.28 GB / 283M 拍 = **16.4 GB/s，已在 DRAM 带宽上**,
// 而剂量三连（去随机载入 −5% / 去散布存 −19% / 去前瞻 +150%）说明它的"松弛"是**带宽**不是
// 发射宽度 ⇒ MLP 抬并行度**不换带宽**；且实装件 `.text` 296177→309329 B（+4.4%），
// 按在册陷阱列（大 Δ.text 历史 0/10 正向）应弃；
// ③ 故本发**只用"一轮一发"去兑现那 50 ms 的确定性收益**，不引入 EV≈0 的方差。
// 在 n=1e6 mod=0 官形状下把 out[]（4,000,000 B）落盘，采件与刀件 **`cmp` 逐字节同**；
// （生成器 `mkknife2.py`，W=4），**未发**。
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128982: retained accepted byte prefix counters, four-stream early rejection and full dominance engine; every inherited attribution remains below.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128762: accepted vector-fold
* engine and all inherited notices retained below.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128588: complete accepted engine,
* all upstream notices and licenses retained below.
* saffah_codex_6a_agg3 https://duck.ac/submission/128708: vector fold minima.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128562: current vector edge
* prefix engine, including its complete inherited credits and unchanged ASM.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_cc_v41_agg1 https://duck.ac/submission/127223: retained its current
* band/fringe engine, branchless edge masks and all inherited source notices.
* Idea: Represent the128-bit running edge prefix as one vector. Variable
* shifts by(sg,sg-64) produce the low or high bit directly: shifts outside
* [0,63] produce zero. One vector OR and one16-byte store replace the scalar
* bit selection, two running OR chains and two separate stores. Range sg<128
* is already enforced by the unchanged mask at the input load.
* Purpose: Reduce instructions and stores while preserving every edge mask.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// （判题机 5637.503051 ms = 本题 rank-1/T）= 本题底盘链的源头（其整条继承链注释原样保留于本文件）。
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号）提交 **#127056** <https://duck.ac/submission/127056>
// （判题机 5583.422833 ms = 我方在册最好件）= 本发的**直接基底**；其头部的 r2l_ 引用/思路块
// （[MLP8] 谱系 #122561 · [PF2L] · [GBFUSE] #127025 · [ALIGN32] 律 715）原样保留于下方。
// [3] 本发新增内容（[r13a16_ EDGNB]）为**本席原创**：不取自任何外部来源、无数值表、无外部代码片段。
// [4] 引用合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交
// 正文均**无独立许可证声明**，按仓库 RULES.md 第 3 节逐件署名（账号 + 原提交地址 + 沿用内容）。
// ===== 思路 =====
// 【r13a16_ 席 · 第 1 发 = [r13a16_ EDGNB] s_edg 建趟内环**去随机分支**（branchless，值逐位不变）】
// 入场（板面，`tools/exact.py 1016` 活取）：mine **5583.422833 ms**（#127056）· T 5637.503051(#126466) ·
// 严支 0.99*T+1µs = **5581.129020** ⇒ 缺 **2.293813 ms（0.041%）**。本发为**单变量**改动。
// 【相位账 · 先量后杀】本席自制打点器 `problems/1016/work/r13a16__tmp/r13a16_prof.py`（插桩点唯一性
// 断言防幽灵刀；判题机同款 gcc9 `ref/gcc9/g9.sh`；n=1e6 k=10 Q=1642 官形状；rdtsc lfence 顺序 mark；
// 两跑互证）：**s_edg 边掩码建趟 = 2.00e8 拍 / 7.115e6 迭代 = 28.1 拍/迭代**，而其端口地板仅
// ~2.5–3 拍/迭代（每迭代 3 条载入类 + 2 条存）⇒ 该环有 ~10× 松弛。
// 【剂量消融定位瓶颈（语义故意错，只用于定价；不入提交）】对该环逐项消融：去掉随机表载入
// `s_npos[sdsr[...]]` 只省 **9%**、去掉 2 条顺序存只省 **6%**、**去掉 32 点前瞻反而 +17%**
// ⇒ 瓶颈**不是访存**。**反汇编实证**（判题机同款 gcc9 -O2 的 base.o）：
// and $0x40,%esi
// je 8b10 ← `if (sg < 64u) eml |= 1ull<<sg; else emh |= 1ull<<(sg-64u);` 的产物
// 而 `sg = s_npos[sdsr[b0+j]] & 127u` 在数据上近似均匀 ⇒ **该分支 ~50/50 随机** ⇒ 每次迭代平均
// ~8-10 拍误预测罚 —— 正是那 28 拍的主要来源。
// 【本发改动】把该分支改写为**等价位运算**（无控制流、值逐位不变）：
// u64 _bit = 1ull << (sg & 63u);
// u64 _mh = (u64)0 - (u64)(sg >> 6); // sg<64 ⇒ 0；sg>=64 ⇒ 全 1
// eml |= _bit & ~_mh; // sg<64 时进 eml
// emh |= _bit & _mh; // sg>=64 时进 emh
// （`shlx` 的移位量自动取模 64 ⇒ `1ull<<(sg&63)`；`_mh` 为 0/全 1 掩码 ⇒ 与原 if/else 逐位等价。）
// 【本机相位实测】同一打点器 3 跑：s_edg **2.00e8 → 1.56e8 拍（−22%）** = 全程序 **−0.20%**
// （总 22.0e9 拍），约为缺口的 **5 倍**。反汇编复核：新环内已无该分支（`shr $6 / and $1 / lea / neg /
// shlx / and / and`，2 条存保持程序序不变）。
// 【闸门（全部通过，工件见 problems/1016/work/r13a16__tmp/）】
// · 暴力 oracle：**k=4..10 × mode 0/1/3/4（n=3000, Q=1642）全部 OK、0 mismatch**（与基底逐题对照）；
// 与直接基底 #127056 的构建件**逐位相同**；
// · 判题形态 `gcc9 -O2 -static -U_FORTIFY_SOURCE -std=c++17 -c` **rc=0**、`nm` **无 main**。
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// （5637.503051 ms = 本题 rank-1/T）= 本文件正文的逐字节底盘（其继承链原样保留于其注释区）。
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号）提交 **#123954** <https://duck.ac/submission/123954>
// （5694.846562 ms）= #126466 的上游底盘。
// [3] duck.ac 用户 **saffah_cc_v41_agg1**（本账号，亲缘题 **1016a**）提交 **#122561**
// <https://duck.ac/submission/122561>：[MLP8] 散布环 8× MLP 谱系（本文件含其「池建插入环」落点）。
// [4] 本账号本队（同日）：**#126970**（本席 [r2l_ PF2L] AND 内环双层前瞻）· **#127025**（r2k_ 席
// [GBFUSE] frord 建表去重 u16 打包 + [PFAOUT]）· **#127039**（本席 [r2l_ FSPAD] s_pm 行写趟
// ⊗ 垫片写趟合并）——三件正文均在本文件底盘里逐字节保留。
// [5] 本发新增（仅编译指示，值中性）：本仓库 `.cache/seat_template.md` 律 715（协调者全队广播）——
// gcc-9 把 256 位取数拆成 `vinserti128 + vmovdqu xmm`；其对策之二 = 叠
// `#pragma GCC optimize("align-loops=32,align-functions=32")`（板面在册 −0.19%）。**未取其代码**。
// [6] 引用合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交
// 正文均**无独立许可证声明**，按仓库 RULES §3 逐件署名（账号 + 原提交地址 + 沿用内容）。
// ===== 思路 =====
// 【r2l_ 反击席 · 第 7 发 = [r2l_ ALIGN32] 对齐轴，落在最新底盘】入场（板面）：
// 本发 = **单变量、纯编译指示、值中性**：把文件原有的
// 改成 `... ,"align-functions=32","align-loops=32")`：只改**热环与函数入口的对齐宽度**（32 B），
// 不改任何指令选择/语义（依据见引用 [5] 的律 715 广播；该轴在册板面 −0.19% ≈ 本题 10 ms 量级，
// 正好与 4.6 ms 缺口同阶）。本文件热环（AND 128 位前缀掩码扫描 / 池建插入环 / frord 建表 / FSPAD 合并趟）
// 都是紧凑向量环，32 B 对齐可减少跨行取指与解码边界效应。
// 闸门（全部通过，工件见 problems/1016/work/r2l__tmp/）：**暴力 oracle k=10 × mode 0/1/3/4（n=3000, Q=1642）
// 判题形态 gcc9 `-O2 -static -U_FORTIFY_SOURCE -std=c++17 -c` rc=0、`nm` 无 main。
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// （判题机 5637.503051 ms = 本题 rank-1/T）= 本文件正文的**逐字节底盘**（其整条继承链原样保留）。
// [2] duck.ac 本账号 **saffah_cc_v41_agg1** 提交 **#126970** <https://duck.ac/submission/126970>
// （判题机 5603.165168 ms = 我方在册最好件）= 本发的**直接基底**（= #126466 正文 + [MLP8] + [PF2L]，
// 其头部的 r2l_ 引用块原样保留于下方）。本发 = #126970 正文 + 下述两刀，其余逐字节相同。
// [3] duck.ac 本账号 **saffah_cc_v41_agg1** 提交 **#122508 / #122504**
// <https://duck.ac/submission/122508> <https://duck.ac/submission/122504>
// （1015 题，5543.050922 / 5560.482884 ms）—— [GBFUSE] 刀的**板面定价出处**：该同形改动在 1015 上
// 实测 **−17.43 ms**；本发把它移植到本题的 frord 建表站点（机制同形、站点同形，非代码拷贝）。
// [4] 本账号在册件 [b16f PFAOUT] <https://duck.ac/submission/122508> 同源思路：pass A 尾部 `out[i]`
// 随机写的目标预取（1015 在册板面正项）；本发补的是本题 **ASCR 快路**里缺失的同一站点。
// [5] duck.ac 题目页 <https://duck.ac/problem/1016>（提交正文按站点规则公开可见）。
// 合规：上述公开提交正文均**无独立许可证声明**；本文件按其原有署名保留账号与原提交地址，未引入任何
// 第三方受许可材料。按 /home/yjp/duck.ac/RULES.md 第 3 节执行。
// ===== 思路 =====
// 【r2k_ 席，2026-10-15】底盘 = 我方在册最好件 #126970（5603.165168 ms）逐字节；本发只加**两刀**，
// 全为「删冗余随机访存 / 补一条既有形态的前瞻」，取值逐位不变：
// ① [r2k_ GBFUSE] frord 建表 `s_frord_[d][dst] = id | (s_bdT[d*N+id]<<20)` 每 (dim,point) 要做
// **两次**随机读多兆表（`s_g[id]` 与 `s_bdT[d*N+id]`）。而 fold 相位里 ds 刚算出、`s_bd` 行
// 本就在 cache ⇒ 顺手顺序写每维打包行 `s_gb[d][i] = (ds<<16)|bdv[d]`（10×4 MB 顺序写）⇒
// 建表只剩 **1 次**随机读（并省掉 1 条前瞻）。★该刀在 **1015** 上是**板面已定价**的：
// #122508 相对 #122504 = **−17.43 ms**（同形机制、同形站点）。
// ② [r2k_ PFAOUT] pass A 尾 `out[i] = cnt` 是 4 MB 随机写、无任何前瞻覆盖；本题**慢路**有该前瞻、
// **ASCR 快路**（本件实跑的正是它）漏了 ⇒ 补上（`out + qo[qq+MF_PFAOUTD]`，纯 hint、零语义）。
// 【闸门】判题同款 gcc：**oracle k=4..10 × mode 0/1/3/4（n=3000, Q=1642）= 28/28 全 OK 且 0 mismatch**；
// 13717.3 ms，同向 −2.8%）。
// ===== REFERENCES =====
// [1] duck.ac 用户 **saffah_codex_6a_agg3** 提交 **#126466** <https://duck.ac/submission/126466>
// （判题机 5637.503051 ms = 本题 rank-1/T）= 本文件正文的**逐字节底盘**；其继承链
// （#126449/#126441/#126416/#126388/#126373/#126338/#126332/#126325/#126303/#126296/
// #126287/#126079/#126055/#126047）原样保留于其自带注释区。
// [2] duck.ac 用户 **saffah_cc_v41_agg1**（本账号）提交 **#123954** <https://duck.ac/submission/123954>
// （5694.846562 ms）= #126466 的上游底盘（其头部自述抄自我的 128-point prefix-mask engine）。
// [3] duck.ac 用户 **saffah_cc_v41_agg1**（本账号，亲缘题 **1016a**）提交 **#122561**
// <https://duck.ac/submission/122561>（1016a 772.998927 ms）：[MLP8]「池建插入环 8× MLP 展开
// + 预取 12→40」——本文件包含该刀（我方提交 #126944 已把其移植到本题池建环，板面 5615.633423 ms）。
// [4] 本发新增（本方原创，未取自任何外部来源）：见思路段 [r2l_ PF2L]。
// [5] 引用合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交
// 正文均**无独立许可证声明**，按仓库 RULES §3 逐件署名（账号 + 原提交地址 + 沿用内容）。
// ===== 思路 =====
// 【r2l_ 反击席 · 第 3 发 = [r2l_ PF2L] AND 内环双层前瞻】入场（板面）：mine **5615.633423 ms**
// （#126944 = 对手 #126466 底盘 + 我方 #122561 的 [MLP8]）· T 5637.503051 (#126466) ·
// 严支 0.99*T+1µs = **5581.129020** ⇒ 缺口 **34.504397 ms（0.612%）**。
// 本发 = **在 AND 内环（本题最大相位，本机 gcc9 相位拍：15.9e9 拍 / 27.5e9 拍 = 58%）把单层前瞻
// 升级为双层前瞻**：原环每迭代只对 4 条平面流发 1 条 `prefetcht0`（w+32 词 = 恰 1 条 cache line
// 之后，前置量仅 ~4 迭代），本发再补一条 (w+64 词) 的第二层前瞻 —— 即每条流同时有 2 条在飞请求，
// 把「每迭代 4 条 line 载入」的 MLP 从 4 提到 8。
// · **前瞻指令不参与语义**（不读结果、不写任何状态）⇒ 输出逐位不变（下闸门实证）。
// · 两层都带 `Clamped ? (w + D < Wf ? D : 0)` 的边界守卫，越界退化为 0（等价于无前瞻），
// 与原环同款，绝不读到分配区之外。
// · 本机 gcc9 相位拍仪（同进程 rdtsc 打点，取每 ds 组"查询段 + 下一组池建"之和）：
// 基座 5 组 ≈ 1.70~1.83e9 拍；单层 D=64 变体 ≈ 1.91e9 拍（**更慢**，故弃）；
// **双层（本发）≈ 1.69e9 拍**，且同轮内 10 组读数一致（±1%）⇒ 取本形态上板。
// 闸门（全部通过，工件见 problems/1016/work/r2l__tmp/）：
// · 暴力 oracle k=10 × mode 0/1/3/4（n=3000, Q=1642）**4/4 OK（0 mismatch）**；
// · 判题形态 gcc9 `-O2 -static -U_FORTIFY_SOURCE -std=c++17 -c` rc=0、`nm` 无 main。
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126449: complete accepted carried-minimum engine, with inherited credits below.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126441: accepted compact counting, peeled-prefetch bitmap intersection and grouped exact ties, with all inherited credits retained below.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126416: retained accepted compact counting, selective four-stream bitmap intersection and branchless grouped ties, with all inherited credits below.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126388: retained grouped exact tie replay and the full accepted ten-dimensional counting engine, with all inherited notices.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126373: retained hot point-ID exact replay, dimension-local flushing, counting/bitmap algorithms and every inherited reference.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126338: retained the accepted dimension-local exact replay and compact signature engine with all inherited references.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126332: retained the ten-dimensional vector cursor prefix, packed tie records and all inherited credits.
* saffah_codex_6a_agg3 https://duck.ac/submission/126294: adapted per-dimension deferred replay and one shared order-array base from the six-dimensional engine.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126325: retained the compact live-signature engine, packed exact-tie replay and all inherited citations.
* saffah_codex_6a_agg3 https://duck.ac/submission/126144: reused eight-frequency SIMD exclusive-prefix construction from the seven-dimensional engine.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126303: retained the accepted36-byte deferred-threshold ten-dimensional engine and all inherited citations.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126296: retained accepted ten-dimensional deferred tie resolution and all inherited citations.
* saffah_codex_6a_agg3 https://duck.ac/submission/126086 and https://duck.ac/submission/126075: adapted low16/high-bit threshold packing from nine/six-dimensional queues.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126287: retained accepted ten-dimensional compact signature planes and all inherited references.
* saffah_codex_6a_agg3 https://duck.ac/submission/126082 and saffah_cc_v41_agg1 https://duck.ac/submission/123963: adapted deferred ambiguous-signature replay from the eight/seven-dimensional engines.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/126079: retained the ten-dimensional compact counting and128-point prefix-mask implementation, with all inherited citations.
* saffah_codex_6a_agg3 https://duck.ac/submission/126143 and saffah_cc_v41_agg1 https://duck.ac/submission/122417: adapted storage of only live signature planes from the eight/nine-dimensional variants.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/123954: copied the accepted128-point prefix-mask ten-dimensional engine, with all leading source attributions preserved below.
- saffah_codex_6a_agg3, https://duck.ac/submission/126055 and https://duck.ac/submission/126047: byte histogram validation and combined20-bit-start/count cursor, adapted from our accepted1012a and1016b front ends. No separate software license notice is shown by these public sources.
Idea: Use byte frequencies when their complete sum proves no overflow, then fuse stable scatter, strict-rank output and bucket output with a single32-bit per-value cursor. Preserve the existing two-stage random-destination prefetch by predicting the cursor's exact start plus arrivals. Large tie groups retain the complete original wide-count path. The128-point bitmap algorithm and its four-stream early exit are unchanged.
Purpose: Remove a full million-point random-table pass per dimension and shrink the histogram working set while preserving stable ties and all recorded ranks.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号）提交 #122201 <https://duck.ac/submission/122201>
// （5764.068327 ms = 本账号 1016 现役最好件，全榜最快）= 本文件正文的逐字节来源。
// [2] duck.ac 用户 saffah_codex_6a_agg3 提交 #122014 <https://duck.ac/submission/122014>
// （5771.260688 ms = 实时排行榜 T）= #122201 正文的来源（NF=4 早退 + 桶秩选择排序），
// 其继承的 #121975/#121808/#121426/#120964 引用链原样保留于下。
// [3] 本账号提交 #121749 <https://duck.ac/submission/121749> —— [t16n_ PFXMASK] 掩码维
// 前缀流（把一条位集流降为每字 1 字节的前缀长度行）的来源；本刀把它再压缩一倍。
// 合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；
// 上述原提交正文均无独立许可证声明。本文件按 RULES §3 逐项署名引用。
// ===== 思路 =====
// 【t16t_ 席 · 第 2 发】入场 mine 5764.068327 (#122201) · T 5771.260688 (#122014) ·
// 严支 0.99T+1µs = 5713.549081 ⇒ 缺 50.519246 ms（0.876%）。
// 本发 = **[t16t_ MB128] 池的块编号由 64 点/块改为 128 点/块**，于是掩码维的前缀长度行
// 从「每 64 位 1 字节」变成「每 128 位 1 字节」——**掩码流字节与 s_tm 表双双减半**，
// 而池的位集数组（8 条流）一字未动。
// · 池位号：blk = rank_ds >> 7，块内位序仍按 rank_dmx ⇒ dim g_dm 的条件仍是「该块的前 c 位」，
// c ∈ [0,128] 恰好仍放得进 1 字节（原 c ∈ [0,64]）。
// · 掩码应用：一个字里两块 → 低字掩码 = 前 min(c,64) 位、高字掩码 = 前 max(c-64,0) 位。
// AVX2 上 `~(ones << k)` 对 k≥64 自动给全 1、对 k=0 给 0 ⇒ 只用一个 u8 饱和减法
// (`subs_epu8` 减 (0,64)) 就能同时得到两半，循环只多 ~2 个 uop（该环本为访存受限）。
// · 边缘掩码 s_edg 改为每 (块, 切口) 两个 u64（块内 128 位、切口 0..128），构造扫掠不变；
// ASCR 锚点暂存的拷贝长度 +1 词（切口块有第二个字）——这正是本发第一次闸门 13/62 处
// mismatch 的根因，修好后全绿。
// 闸门：暴力 oracle k=4..10 × mode 0/1/3/4（n=3000, Q=1642）**28/28 OK** + n=10000 mode 0/3 OK；
// 与基座 #122201 **逐位相同** ✓；`tools/gcc93check.py`（无 LOCAL_TEST 判题形态）COMPILE OK ✓。
// 判负记录（同席第 1 发，勿重走）：给 AND 环/建趟加前瞻（QPF/SDPF/FRPF）= #122413 = +67.5 ms。
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3 提交 #122014 <https://duck.ac/submission/122014>
// （5771.260688 ms，当前 T）= 本文件正文的逐字节来源；除本头部注释块外一字未改
// （`diff -u -w` 复核：正文 0 差异）。其继承的 #121975/#121808 引用链原样保留于下。
// [2] 本账号 saffah_cc_v41_agg1 提交 #121902 <https://duck.ac/submission/121902>
// （5967.213975 ms）= #122014 正文的来源（对手用我方前缀掩码引擎 + 早退）。
// 合规：duck.ac 提交正文按站点规则公开可见（题面“你提交的代码将会被公开”）；
// 上述原提交正文均无独立许可证声明。本文件按 RULES §3 逐项署名引用。
// ===== 思路 =====
// 【t16p_ 席 · 第 2 发】入场 mine 5967.213975 (#121902) · T 5771.260688 (#122014)。
// 第 1 发 #122126 = #122014 正文逐字节（5771.710135，Accepted）。本发在其上叠**本席新刀
// [CLAMP]**：`and_popcount_pm` 的热环里有 3 条前瞻，其目标地址**越过本查询自己的区域末尾**：
// · 前 4 条流的 `bs[d] + w + 32`（lead=4 迭代）—— 最后 4 个迭代目标的字已 ≥ Wr；
// · `trow + w + 64`（lead=8 迭代）—— 最后 8 个迭代已越过前缀行；
// · 尾 4 条流的同款 lead-32（在生存分支内，按 84.2% 生存率发）。
// 这些行本查询永不读，等于白买 DRAM 行。本刀**只把地址夹回区域**（`(w+32<Wr)?32:0`、
// `(w+64<Wr)?64:0`），不移动任何 load、不改任何取值 ⇒ 逐位等价（本机 n=4e5 两臂 FNV
// 逐位同 = 5620543286167856259）。同进程两臂交替 min-of-3：2860.0 → 2842.5 ms（−0.61%，
// 三轮同向）；按判题机 pass A = 4+3.37+0.26 行/迭代的流量账，夹回的是每查询 ~37 行的白买。
// （第 3 发候选 BNE=无分支早退已被本机否决：n=1e6 同进程两臂 min-of-3 11460 vs 10801 ms =
// +6.1%，机理 = 尾流 load 地址被 testz+cmov 拖到测试之后，失去投机发射；未发。）
// 历史（第 1 发）：§2.18.349 `diff -u -w` 我方 #121902 vs #122014 的**全部真改动只有 3 处**：
// (a) **AND 环早退**：先 AND「按桶秩升序的前 4 条流」+ 前缀行，512 位全空则 `continue` 跳过
// 其余 4 条流的载入。本席计数器实测（n=1e6 mode10 Q=1642）：176,891,354 块迭代中跳过
// 27,975,016（15.8%），尾流载入率 84.2% ⇒ 流量 8 → 7.37 行/迭代（NF=3/5 分别 7.61/7.40
// ⇒ 对手的 NF=4 已是最优；纯按生存率算的“NF=2 更省”被实测否决）。
// (b) 每查询对前 4 条流按桶秩（bd[rd]）做 4 趟选择排序（nbx>=8 时），使早退测试打在
// **最选择性的 4 个维**上。
// (c) s_edg 建趟里 `s_npos[sdsr[b0+j]]` 的地址提前 32 点前瞻（= 本账号 [PFXSW] 同族的
// 第二个“零前瞻随机访存”站点，本席复核：该环每点 1 次 4 MB 表随机读）。
// 闸门：官形状 k=10 n=1e6 Q=1642 mode 10/13/18 checksum 969232827 + out[] FNV
// 8996697766657014596 / 2559007080471616052 与基座 #121902 逐位相同 ✓；
// 判题同款编译 gcc9.3 -O2 -static -U_FORTIFY_SOURCE -std=c++17 rc=0 ✓。
// 本发为纯采纳件（本席的自造刀见下一发：BNE 无分支早退，正在定价）。
/* References:
- saffah_codex_6a_agg3, https://duck.ac/submission/121975: copied prefix-mask
and prefetched edge-table engine, all inherited notices retained below.
Idea: In ten dimensions, intersect the four smallest-bucket bitsets and the
prefix mask first. If all512 resulting bits are zero, skip the remaining
four stream loads and population count for that block. Exact intersections
are commutative; every surviving block completes all original conditions.
Experiment purpose: Trade per-query pointer ordering and block zero checks
for less traffic from dimensions that cannot change an empty intersection.
*/
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/121902: copied the prefix-mask
engine and its prefetched rank-dimension permutation sweep. All inherited
author, source and license notices remain below; no independent license
notice was declared in the direct source.
Idea: Prefetch the second permutation lookup stream while constructing region
edge masks. Point IDs arrive in rank_ds order, so the address of each later
s_npos read is already known32 positions ahead. Cover across block boundaries
while retaining bounds checks and every edge-mask dependency.
Experiment purpose: Hide random permutation-read latency in edge-table setup.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3 提交 #121808 <https://duck.ac/submission/121808>
// （6023.593438 ms）= 本文件正文逐字节来源；本席相对它仅一处改动：PFXMASK 建表扫描环
// 加 2 条地址前瞻（`[t16o_ PFXSW]`，取值逐位不变）。
// [2] 本账号提交 #121749 <https://duck.ac/submission/121749>（6100.449484 ms）—— #121808
// 正文的来源，其继承的 #121426/#121470 引用链与历史注释原样保留于下方。
// 合规：duck.ac 正文按站点规则公开可见；原正文均无独立许可证声明。
/* References:
- saffah_cc_v41_agg1, https://duck.ac/submission/121749: compressed prefix-length
bitset representation and inherited ten-dimensional engine. All original
attribution and license notices are retained below.
Idea: Expand four prefix lengths directly with AVX2 byte-to-qword widening and
variable shifts of all-ones vectors. Complementing the shifted vector yields
exactly the low t bits, including t=0 and t=64. Replace eight scalar mask-table
loads and vector assembly in the main intersection loop with two expansions.
Experiment purpose: Reduce prefix-mask construction instructions and L1 loads
while preserving every mask, edge condition and count.
*/
// [t16n_] 1016 worker 席 —— pass A 的「掩码维前缀流」：把 AND 链 9 条位集流中的一条降为
// 每字 1 字节的前缀长度行（位集索引/算法形态改动；计数语义与其余相位一字未动）。
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，原提交 **#121426** <https://duck.ac/submission/121426>
// （判题机 6152.580955 ms = 本题 T）—— 本文件正文的逐字节来源（其自带 REFERENCES/思路 区原样保留在下方）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号）提交 **#121470** <https://duck.ac/submission/121470>
// = #121426 的逐字节副本（t16m_ 席落地，6152.591707 ms = 本席入场时的 mine）；其头部
// [t16m_]/[t16j_]/[t16e_]/[t16d_] 段与下方全部历史注释一并保留（仅按判题源码长度上限压掉叙述段）。
// [3] 本仓库 problems/1016/notes.md（t16m_ 席「全相位图 + pass A 带宽墙」与 MF_BUILD_NOPOOL 零页探针）
// 与 .cache/agents.md 全队相位账 —— 本刀方向（能动 66% 的只有减 pass A 字节）来自该账；未取其代码。
// 合规：duck.ac 提交正文按站点规则公开可见（题面「你提交的代码将会被公开」）；上述原提交正文均无独立许可证声明。
// [t16m_] 1016 worker 席 —— 采纳当前 T 件（对手 #121426）正文：全值域签名映射 + 第二桶预排序 + MAXQ 上限。
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，原提交 #121426
// <https://duck.ac/submission/121426>（判题机 Time = 6152.580955 ms = 本题实时排行榜第一名 T）
// —— 本文件正文 = 该提交正文的**逐字节副本**（其自带引用/思路注释区原样保留在下方；本席 diff 0 处）。
// 该件自带引用链（其头部原样保留）：其 #121237（full-range cached-query engine = 坐标→255 桶定点映射）、
// 其 #121062 / #121171（second-bucket query locality 预排序）、以及我方 #120964（query/bound 签名 padding）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #120964
// <https://duck.ac/submission/120964>（判题机 6196.734906 ms = 本账号 1016 现役最好件）
// —— #121426 正文中继承的 [t16e_ SIGPAD] 段即来自该件；本账号前序件另有 #120444/#120763。
// 合规：duck.ac 提交正文按站点规则公开可见、可直接取用（题面"你提交的代码将会被公开"）；
// 上述原提交正文均无独立许可证声明。本文件按 /home/yjp/duck.ac/RULES.md 第 3 节署名作者账号与原提交地址。
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121237: retained accepted full-range cached-query engine.
* saffah_cc_v41_agg1, https://duck.ac/submission/120964: inherited query/bound signature padding.
* All inherited citations retained; no separate license notices were displayed.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121171: retained full-range cached-signature engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/121062: adapted second-bucket query locality.
* All inherited citations retained; no separate license notices were displayed.
* Prior implementation rationale is documented in the credited submission.
 */
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/120964: retained cached-query ten-dimensional engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/120939: reused full-range signature quantization.
* All inherited citations retained; no separate license notices were displayed.
* Prior implementation rationale is documented in the credited submission.
 */
// [t16d_] 1016 worker 席 —— 删除池构建里每 ds 组重建的 s_nid 逆排列（10e6 次随机 RMW）。
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #120444
// <https://duck.ac/submission/120444>（判题机 Time = 6240.233886 ms = 本账号 1016 现役最好件）
// —— 本文件正文 = 该提交正文的逐字节副本（其自带引用/思路注释区原样保留在下方）。
// 本席相对它只有"删除 + 改用等价既有数据"的 2 处改动（见下），不含任何新算术。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #111659
// <https://duck.ac/submission/111659>（本题 6331.003381 ms）—— #120444 的入场基座，
// 含 MF_QCOEF 20155 / MF_NOFILTB 1 / MF_NOSDMP 1 / MF_NIDPF 12 / MF_PLEN 1 / MF_BUDGETMB 1940
// 等本题旋钮。本文件经 #120444 继承上述全部内容。
// [3] 本席使用本仓库内既有驱动 problems/1016a/work/rc_1016a_jmain.cpp（作者：本账号 a16y_ 席）作为
// "判题机路径"测量口径：它以 -Dmain=sub_main 抑制本题 LOCAL_TEST 自带 main，从而不改 g_Q/g_B，
// 使引擎走真实 auto-Q 预算式 = 判题机实际路径。本文件不含该驱动的任何代码。
// 合规：duck.ac 提交正文按站点规则公开可见、可直接取用（题面"你提交的代码将会被公开"）；
// 上述原提交正文均无独立许可证声明。本文件按 /home/yjp/duck.ac/RULES.md 第 3 节署名作者账号与原提交地址。
// [t16e_] 1016 worker 席 —— 把 s_avpool 行载入从 pass B(fringe) 热路径中删除（纯删除随机访存）。
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #120763
// <https://duck.ac/submission/120763>（判题机 Time = 6222.129260 ms = 本账号 1016 现役最好件）
// —— 本文件正文 = 该提交正文的逐字节副本（其自带引用/思路注释区原样保留在下方）。
// 本席相对它只有下述"删除 + 改用等价既有数据"的改动，不含任何新算术（无新公式/无新布局）。
// [2] 本席沿用 #120763 继承的全部旋钮与第三方引用（见下方 [t16d_]/[a16x_] 区），未改动它们。
// [a16x_] 1016 worker 席 —— 复刻对手 T (#120337) 的 3 处真改动 + 自带一刀 [FA]
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，原提交 #120337
// <https://duck.ac/submission/120337>（判题机 Time = 6241.633621 ms = 本题实时 T）
// —— 本文件正文 = 该提交的逐字节副本（其自带引用/思路注释区原样保留在下方）。
// 所抄内容（本席逐行 diff 取证：该件 = 本账号 #111659 逐字节 + 恰好 3 处真改动）：
// ① 顶部新增 `#define MF_NOSDMP 1` —— 弃用 s_sdmp 的 400 MB 转置行建表；
// ② 签名面扫描入口去掉 `c0 &&`（并加 `(hi-lo)>=2`），两处精确回退的 `cp` 改 c0 可空三元
// （c0==0 时回退读 s_pm 行）⇒ 无转置行时签名扫描仍然可用；
// ③ 新增独立「点主序 8 位签名字节数组 + 8 记录字节转置写面」块（其自述抄我方 #111877 的
// 预合并与 #114343 的 8 记录转置）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #114343
// <https://duck.ac/submission/114343>（1014b，81.107107 ms）—— [FA]「无分支折叠维 argmin」
// 为该件首创；本件把它移植到本题（k=10）的折叠维选择环，是本件相对 #120337 的**唯一**正文改动。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），原提交 #111659
// <https://duck.ac/submission/111659>（本题 6331.003381 ms = 本账号入场现役最好件）—— 入场基座，
// 含 [x16y2-DEADPF] 死预取删除与 MF_QCOEF 20155 / MF_NOFILTB 1 等本题旋钮；本文件正文经
// #120337 继承上述全部内容。
// 合规：duck.ac 提交正文按站点规则公开可见、可直接取用（题面"你提交的代码将会被公开"）；
// 上述原提交正文均无独立许可证声明。本文件按 /home/yjp/duck.ac/RULES.md 第 3 节署名作者账号与原提交地址。
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/111659:
* copied the accepted min-fold/signature engine and retained inherited references.
* saffah_cc_v41_agg1, https://duck.ac/submission/111877:
* adapted precomputation of compact point-major signature bytes.
* saffah_cc_v41_agg1, https://duck.ac/submission/114343:
* adapted eight-record byte transposition for signature-plane output.
* Public sources displayed no separate software license notices.
* Idea: Extend our successful small-case integration to this million-point task:
* omit full transposed-coordinate rows, gather exact signature survivors through
* point order, precompute signature bytes once, and emit 64-bit plane stores using
* an eight-record transpose. Preserve this engine's exact signature encoding.
* Purpose: Official experiment reducing redundant construction and first-touch work.
*/
#define MF_NOSDMP 1
#ifndef MF_PFXMASK
#define MF_PFXMASK 1
#define MF_PFXSW 24
#endif
#pragma GCC optimize("O3","unroll-loops","no-strict-aliasing","align-functions=64","align-loops=256,no-gcse,live-range-shrinkage,no-if-conversion,no-tree-coalesce-vars,no-tree-partial-pre,no-ivopts,no-peel-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=skylake")
#ifndef MF_FRDPF
#define MF_FRDPF 32
#endif
#ifndef MF_CNTPF
#define MF_CNTPF 64
#endif
#ifndef MF_GQPF
#define MF_GQPF 32
#endif
#define MF_QCOEF 20155
#define MF_NOFILTB 1
#include <immintrin.h>
#include <type_traits>
static inline __m256i LDU(const void *p) {
__m256i v;
__asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m256i *)p));
return v;
}
static inline __m256i LDA(const void *p) {
__m256i v;
__asm__("vmovdqa %1, %0" : "=x"(v) : "m"(*(const __m256i *)p));
return v;
}
static inline void STU(void *p, __m256i v) {
__asm__ volatile("vmovdqu %1, %0" : "+m"(*(__m256i *)p) : "x"(v));
}
static inline void STA(void *p, __m256i v) {
__asm__ volatile("vmovdqa %1, %0" : "+m"(*(__m256i *)p) : "x"(v));
}
static inline __m128i LDQ(const void *p) {
__m128i v;
__asm__("vmovdqu %1, %0" : "=x"(v) : "m"(*(const __m128i *)p));
return v;
}
#define LDU_M(p) ({ __m256i _v; __asm__("vmovdqu %1, %0" : "=x"(_v) : "m"(*(const __m256i *)(p))); _v; })
#define LDA_M(p) ({ __m256i _v; __asm__("vmovdqa %1, %0" : "=x"(_v) : "m"(*(const __m256i *)(p))); _v; })
#define STU_M(p, v) do { __m256i _vv = (__m256i)(v); __asm__ volatile("vmovdqu %1, %0" : "+m"(*(__m256i *)(p)) : "x"(_vv)); } while (0)
#define STA_M(p, v) do { __m256i _vv = (__m256i)(v); __asm__ volatile("vmovdqa %1, %0" : "+m"(*(__m256i *)(p)) : "x"(_vv)); } while (0)
#ifdef LOCAL_TEST
#include <cstdio>
#include <cstdlib>
#include <ctime>
#else
#ifdef __cplusplus
extern "C" void *malloc(unsigned long);
#else
void *malloc(unsigned long);
#endif
#endif
typedef unsigned u32;
typedef unsigned short u16;
typedef unsigned char u8;
typedef unsigned long long u64;
#define LDU256(p) ({ __m256i _v256; __asm__("vmovdqu %1, %0" : "=x"(_v256) : "m"(*(const __m256i *)(p))); _v256; })
#ifndef MAXN
#define MAXN 1000005
#define MF_SPL ((size_t)1000064)
#define MF_PFB1 96
#define MF_PFB2 64
#define MF_PFB3 8
#endif
#define MAXK 10
#define STRIDE 16
#ifndef MF_APF
#define MF_APF 0
#endif
#ifndef MF_QCOEF
#define MF_QCOEF 20155
#endif
#ifndef MF_KSPAD
#define MF_KSPAD 1
#endif
#ifndef MF_FILTAUTO
#define MF_FILTAUTO 1
#endif
#ifndef MF_NT
#define MF_NT 1
#endif
#ifndef MF_FR_NOSORT
#define MF_FR_NOSORT 0
#endif
#ifndef MF_FR_NOCAND
#define MF_FR_NOCAND 0
#endif
#ifndef MF_BUILD_NOPOOL
#define MF_BUILD_NOPOOL 0
#endif
#ifndef MF_FR_NOREAD
#define MF_FR_NOREAD 0
#endif
#ifndef MF_NOSDMP
#define MF_NOSDMP 0
#endif
#ifndef MF_FB2
#define MF_FB2 0
#endif
#ifndef MF_FB3
#define MF_FB3 1
#endif
#ifndef MF_PLEN
#define MF_PLEN 1
#endif
#ifndef MF_BUDGETMB
#define MF_BUDGETMB 2018
#endif
#ifndef MF_NOFILTB
#define MF_NOFILTB 0
#endif
#ifndef MF_PFB
#define MF_PFB 24
#endif
#ifndef MF_ASCR
#define MF_ASCR 1
#endif
#ifndef MF_WTRIM
#define MF_WTRIM 0
#endif
#define AS_WORDS 20480
#ifndef MF_PFA
#define MF_PFA 1
#endif
#ifndef MF_PFAOUT
#define MF_PFAOUT 1
#endif
#ifndef MF_PFAOUTD
#define MF_PFAOUTD 96
#endif
#ifndef MF_SCAPF
#define MF_SCAPF 32
#endif
#define Z16S_PFW(p) __asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(p)))
#ifndef MF_ORDPF
#define MF_ORDPF 48
#endif
#ifndef MF_NIDPF
#define MF_NIDPF (12)
#endif
#ifndef MF_FR_NOMETA
#define MF_FR_NOMETA 0
#endif
#ifndef MAXQ
#define MAXQ 1824
#endif
static u32 s_ord[MAXK][MAXN];
static u32 s_frord_[MAXK][MAXN];
static u32 s_gt[MAXK][MAXN];
static u32 s_pm[(size_t)MAXN * STRIDE] __attribute__((aligned(64)));
static u16 s_bd[(size_t)MAXN * MAXK];
static u16 s_bdT[(size_t)MAXK * MAXN];
static u32 s_g[MAXN];
static u8 fold_dimension[MAXN];
static u32 s_qord[MAXN], s_tmp[MAXN], s_cntv[MAXN];
alignas(64) static u8 compact_hist[MAXN+8];
alignas(64) static u32 compact_cursor[MAXN+8];
static u16 s_bkt[MAXN];
static u16 s_bka[MAXN];
static u32 s_nid[MAXN];
static u32 s_npos[MAXN] __attribute__((aligned(64)));
static u32 s_blkk[64], s_blkp[64];
static u8 *s_tm = 0;   static size_t s_tmcap = 0;
static u8 *s_edg = 0; static size_t s_edgcap = 0;
static u64 s_pref[256] __attribute__((aligned(64)));
static int g_dm = -1;
static u32 g_tstride = 0;
static u32 s_tofs[MAXQ + 1], s_rlen[MAXQ + 1];
static u8 s_cntx[16384];
static int g_mask_on = 0;
static int g_mask_ok = 0;
static u32 s_pos[MAXK][MAXN];
static u32 s_posp[(size_t)MAXK * MAXN];
static u64 s_facc[(size_t)(MAXK - 1) * (((MAXN) + 63) / 64 + 16)];
static u32 s_bnde[(size_t)MAXK * (MAXQ + 2)];
static u64 *s_fbm = 0;
static u64 s_fbuf[8192] __attribute__((aligned(64)));
static __m256i khi8v, khi8hv, kbadhi, kokhi;
static u32 g_Qc = 32;
static u32 g_fbm_W = 0;
static int g_use_filt = 0;
static int g_lexsort = 0;
static int g_nofilt = 0;
static u32 s_fpos[(MAXK + 1) * MAXQ];
static u32 s_bval[(MAXK + 1) * MAXQ];
static u64 *s_bs = 0;
static u64 s_acc[MAXN / 64 + 256] __attribute__((aligned(64)));
static u32 *s_sdmp[MAXK];
static u64 s_ascr[AS_WORDS] __attribute__((aligned(64)));

static u32 s_delta[MAXN];
static u32 s_doff[MAXQ + 2];
static u32 s_maxr[(size_t)MAXK * MAXK * MAXQ];
static u32 *s_avpool = 0;
static size_t s_avcap = 0;
static u8 *s_sig = 0;
static int g_sig_on = 0;
static int g_sig_merged = 0;
static u32 g_sigsh = 0;
static u32 g_sigmul;
static inline u32 sigfull(u32 x){return (x*g_sigmul)>>23;}
static void prepare_cached_signatures(u8 *dst,const unsigned **x,u32 N){
 const __m256i mul=_mm256_set1_epi32(g_sigmul),one=_mm256_set1_epi32(1);
 const __m256i gather=_mm256_setr_epi8(0,4,8,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,4,8,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1);
 const __m128i mask2=_mm_set_epi64x(0,65535);
 u32 i=0;
 for(;i+8<=N;i+=8){
  __m128i c[10];
  #pragma GCC unroll 10
  for(int d=0;d<10;++d){
   __m256i q=_mm256_mullo_epi32(_mm256_loadu_si256((const __m256i*)(x[d]+i)),mul);
   q=_mm256_max_epu32(_mm256_srli_epi32(q,23),one);
   q=_mm256_shuffle_epi8(q,gather);
   c[d]=_mm_unpacklo_epi32(_mm256_castsi256_si128(q),_mm256_extracti128_si256(q,1));
  }
  __m128i t0=_mm_unpacklo_epi8(c[0],c[1]),t1=_mm_unpacklo_epi8(c[2],c[3]);
  __m128i t2=_mm_unpacklo_epi8(c[4],c[5]),t3=_mm_unpacklo_epi8(c[6],c[7]);
  __m128i u0=_mm_unpacklo_epi16(t0,t1),u1=_mm_unpackhi_epi16(t0,t1);
  __m128i u2=_mm_unpacklo_epi16(t2,t3),u3=_mm_unpackhi_epi16(t2,t3);
  __m128i r[4]={_mm_unpacklo_epi32(u0,u2),_mm_unpackhi_epi32(u0,u2),_mm_unpacklo_epi32(u1,u3),_mm_unpackhi_epi32(u1,u3)};
  __m128i tail=_mm_unpacklo_epi8(c[8],c[9]);
  #pragma GCC unroll 8
  for(int p=0;p<8;++p){
   __m128i lo=(p&1)?_mm_srli_si128(r[p/2],8):r[p/2];
   __m128i hi=_mm_and_si128(_mm_srli_si128(tail,p*2),mask2);
   _mm_storeu_si128((__m128i*)(dst+(size_t)(i+p)*10),_mm_unpacklo_epi64(lo,hi)); 
  }
 }
 for(;i<N;++i)for(int d=0;d<10;++d){u32 v=sigfull(x[d][i]);dst[(size_t)i*10+d]=(u8)(v?v:1u);}
}
static u32 s_pofs[(size_t)MAXK * MAXQ];
static u32 s_plen[(size_t)MAXK * MAXQ];
static int g_plen_on = 0;
static u32 g_W, g_Q, g_B;
static u32 g_KS;
static int g_nosort = 0;
static int g_nosdmp = 0;
static int g_skip_and = 0, g_skip_fringe = 0;
#define FPOS(d, b) s_fpos[(size_t)(d) * MAXQ + (b)]
#define BVAL(d, b) s_bval[(size_t)(d) * MAXQ + (b)]
extern "C" int madvise(void*, unsigned long, int);
static void *pool_alloc(size_t bytes) {
void *raw = malloc(bytes + (2u << 20));
if (!raw) return 0;
void *al = (void *)(((size_t)raw + (2u << 20) - 1) & ~(size_t)((2u << 20) - 1));
if (bytes >= (size_t)(4u << 20)) madvise(al, bytes, 14);
return al;
}
static constexpr u32 DEFER_CAP=1u<<19;
alignas(64) static u32 defer_entries[(size_t)DEFER_CAP*9];
static u32 defer_count;
static void flush_deferred(u32*out,const u32*order){
u32 n=defer_count;defer_count=0;
for(u32 b=0;b<n;b+=128){
u32 end=b+128<n?b+128:n;
for(u32 j=b;j<end;j++){
const u32*e=defer_entries+(size_t)j*9;
u32 id=e[1];
__builtin_prefetch(out+e[0],1,3);
_mm_prefetch((const char*)(s_pm+(size_t)id*STRIDE),_MM_HINT_T0);
}
for(u32 j=b;j<end;){
const u32*e=defer_entries+(size_t)j*9;
const u32 query=e[0];
__m256i lo=_mm256_cvtepu16_epi32(_mm_loadu_si128((const __m128i*)(e+2)));
__m256i hi=_mm256_cvtepu8_epi32(_mm_cvtsi64_si128((long long)_pdep_u64(e[6],0x0f0f0f0f0f0f0f0full)));
__m256i th=_mm256_or_si256(lo,_mm256_slli_epi32(hi,16));
__m128i upper=_mm_loadl_epi64((const __m128i*)(e+7));
u32 count=0;
do{
const u32*p=s_pm+(size_t)defer_entries[(size_t)j*9+1]*STRIDE;
__m256i a=_mm256_cmpgt_epi32(th,_mm256_load_si256((const __m256i*)p));
__m128i h=_mm_cmpgt_epi32(upper,_mm_loadl_epi64((const __m128i*)(p+8)));
u32 mask=(u32)_mm256_movemask_epi8(a);
mask&=(u32)_mm_movemask_epi8(h)|0xffffff00u;
count+=(mask==0xffffffffu);
++j;
}while(j<end&&defer_entries[(size_t)j*9]==query);
out[query]+=count;
}
}
}
__attribute__((target("avx2,popcnt")))
static inline u32 hsum256(__m256i v) {
u64 b[4];
_mm256_storeu_si256((__m256i *)b, v);
return (u32)(b[0] + b[1] + b[2] + b[3]);
}
template<int KK>
__attribute__((target("avx2,popcnt")))
static u32 and_popcount_range(const u64 *const *bs, u32 Wr, u32 rem) {
const __m256i lm = _mm256_set1_epi8(0x0f);
const __m256i lk = _mm256_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
const __m256i z = _mm256_setzero_si256();
__m256i tot = z, acc0 = z, acc1 = z;
u32 w = 0, cnt = 0, total = 0;
for (; w + 8 <= Wr; w += 8) {
if (KK > 1) _mm_prefetch((const char *)(bs[1] + w + 32), _MM_HINT_T0);
if (KK > 2) _mm_prefetch((const char *)(bs[2] + w + 32), _MM_HINT_T0);
if (KK > 3) _mm_prefetch((const char *)(bs[3] + w + 32), _MM_HINT_T0);
if (KK > 4) _mm_prefetch((const char *)(bs[4] + w + 32), _MM_HINT_T0);
if (KK > 5) _mm_prefetch((const char *)(bs[5] + w + 32), _MM_HINT_T0);
if (KK > 6) _mm_prefetch((const char *)(bs[6] + w + 32), _MM_HINT_T0);
if (KK > 7) _mm_prefetch((const char *)(bs[7] + w + 32), _MM_HINT_T0);
if (KK > 8) _mm_prefetch((const char *)(bs[8] + w + 32), _MM_HINT_T0);
__m256i a = LDU256((bs[0] + w));
__m256i b = LDU256((bs[0] + w + 4));
for (int d = 1; d < KK; d++) {
a = _mm256_and_si256(a, LDU256((bs[d] + w)));
b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
}
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
if (++cnt == 31) {
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
acc0 = acc1 = z; cnt = 0;
}
}
for (; w + 4 <= Wr; w += 4) {
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < KK; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
__m256i lo = _mm256_and_si256(a, lm);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo), _mm256_shuffle_epi8(lk, hi)));
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
total = hsum256(tot);
for (; w < Wr; w++) {
u64 v = bs[0][w];
for (int d = 1; d < KK; d++) v &= bs[d][w];
total += (u32)__builtin_popcountll(v);
}
if (rem) {
u64 v = bs[0][Wr];
for (int d = 1; d < KK; d++) v &= bs[d][Wr];
total += (u32)__builtin_popcountll(v & ((1ull << rem) - 1));
}
return total;
}
template<int NS>
__attribute__((target("avx2,popcnt")))
static u32 and_popcount_pm(const u64 *const *bs, const u8 *trow, const u8 *edgp, u32 Wf, u32 cut) {
const __m256i lm = _mm256_set1_epi8(0x0f);
const __m256i lk = _mm256_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
const __m256i z = _mm256_setzero_si256();
const __m256i ones=_mm256_set1_epi64x(-1);
const __m128i sub64v=_mm_set1_epi16(0x4000);
__m256i tot = z, acc0 = z, acc1 = z;
u32 w = 0, total = 0;
auto scan_full=[&](auto clamp_tag,u32 stop){
constexpr bool Clamped=decltype(clamp_tag)::value;
while (w + 8 <= stop) {
u32 batchstop=stop < w+248u ? stop : w+248u;
for (; w + 8 <= batchstop; w += 8) {
constexpr int NF=NS<4?NS:4;
const u32 ld32 = Clamped ? ((w + 32u < Wf) ? 32u : 0u) : 32u;
const u32 ld32b = Clamped ? ((w + 64u < Wf) ? 64u : 0u) : 64u;
for (int d = 0; d < NF; d++) { if constexpr(Clamped) _mm_prefetch((const char *)(bs[d] + w + ld32), _MM_HINT_T0); _mm_prefetch((const char *)(bs[d] + w + ld32b), _MM_HINT_T0); }
_mm_prefetch((const char *)(trow + (w >> 1) + (Clamped ? ((w + 64u < Wf) ? 32u : 0u) : 32u)), _MM_HINT_T0);
__m256i a,b;
if constexpr(NF==4){
__m256i a0=LDU256(bs[0]+w),a2=LDU256(bs[2]+w);
__m256i b0=LDU256(bs[0]+w+4),b2=LDU256(bs[2]+w+4);
__asm__("vpand %2,%1,%0" : "=x"(a0) : "x"(a0),"m"(*(const __m256i*)(bs[1]+w)));
__asm__("vpand %2,%1,%0" : "=x"(a2) : "x"(a2),"m"(*(const __m256i*)(bs[3]+w)));
__asm__("vpand %2,%1,%0" : "=x"(b0) : "x"(b0),"m"(*(const __m256i*)(bs[1]+w+4)));
__asm__("vpand %2,%1,%0" : "=x"(b2) : "x"(b2),"m"(*(const __m256i*)(bs[3]+w+4)));
a=_mm256_and_si256(a0,a2);b=_mm256_and_si256(b0,b2);
}else{
a = LDU256((bs[0] + w));
b = LDU256((bs[0] + w + 4));
for (int d = 1; d < NF; d++) {
a = _mm256_and_si256(a, LDU256((bs[d] + w)));
b = _mm256_and_si256(b, LDU256((bs[d] + w + 4)));
}
}
u32 tb = *(const u32 *)(trow + (w >> 1));
__m128i tv=_mm_cvtsi32_si128((int)tb);
__m128i tdup=_mm_unpacklo_epi8(tv,tv);
__m128i tsub=_mm_subs_epu8(tdup,sub64v);
a = _mm256_and_si256(a,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(tsub)),ones));
b = _mm256_and_si256(b,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(_mm_srli_si128(tsub,4))),ones));
if constexpr(NS>4){
__m256i live=_mm256_or_si256(a,b);
if(_mm256_testz_si256(live,live))continue;
if constexpr(NS==8){
for(int d=4;d<8;d++){_mm_prefetch((const char*)(bs[d]+w+ld32),_MM_HINT_T0);_mm_prefetch((const char*)(bs[d]+w+ld32b),_MM_HINT_T0);}
__m256i c0=LDU256(bs[4]+w),c2=LDU256(bs[6]+w);
__m256i d0=LDU256(bs[4]+w+4),d2=LDU256(bs[6]+w+4);
__asm__("vpand %2,%1,%0":"=x"(c0):"x"(c0),"m"(*(const __m256i*)(bs[5]+w)));
__asm__("vpand %2,%1,%0":"=x"(c2):"x"(c2),"m"(*(const __m256i*)(bs[7]+w)));
__asm__("vpand %2,%1,%0":"=x"(d0):"x"(d0),"m"(*(const __m256i*)(bs[5]+w+4)));
__asm__("vpand %2,%1,%0":"=x"(d2):"x"(d2),"m"(*(const __m256i*)(bs[7]+w+4)));
a=_mm256_and_si256(a,_mm256_and_si256(c0,c2));
b=_mm256_and_si256(b,_mm256_and_si256(d0,d2));
}else{
for(int d=4;d<NS;d++){
_mm_prefetch((const char*)(bs[d]+w+ld32),_MM_HINT_T0);
a=_mm256_and_si256(a,LDU256(bs[d]+w));
b=_mm256_and_si256(b,LDU256(bs[d]+w+4));
}
}
}
__m256i lo0 = _mm256_and_si256(a, lm);
__m256i hi0 = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
__m256i lo1 = _mm256_and_si256(b, lm);
__m256i hi1 = _mm256_and_si256(_mm256_srli_epi16(b, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo0), _mm256_shuffle_epi8(lk, hi0)));
acc1 = _mm256_add_epi8(acc1, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo1), _mm256_shuffle_epi8(lk, hi1)));
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
acc0 = acc1 = z;
}
};
scan_full(std::false_type{}, Wf>64u?Wf-64u:0u);
scan_full(std::true_type{},Wf);
for (; w + 4 <= Wf; w += 4) {
__m256i a = LDU256((bs[0] + w));
for (int d = 1; d < NS; d++) a = _mm256_and_si256(a, LDU256((bs[d] + w)));
u32 tb = *(const u16 *)(trow + (w >> 1));
__m128i tv=_mm_cvtsi32_si128((int)tb);
__m128i tdup=_mm_unpacklo_epi8(tv,tv);
__m128i tsub=_mm_subs_epu8(tdup,sub64v);
a = _mm256_and_si256(a,_mm256_xor_si256(_mm256_sllv_epi64(ones,_mm256_cvtepu8_epi64(tsub)),ones));
__m256i lo = _mm256_and_si256(a, lm);
__m256i hi = _mm256_and_si256(_mm256_srli_epi16(a, 4), lm);
acc0 = _mm256_add_epi8(acc0, _mm256_add_epi8(_mm256_shuffle_epi8(lk, lo), _mm256_shuffle_epi8(lk, hi)));
}
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc0, z));
tot = _mm256_add_epi64(tot, _mm256_sad_epu8(acc1, z));
total = hsum256(tot);
for (; w < Wf; w++) {
u64 v = bs[0][w];
for (int d = 1; d < NS; d++) v &= bs[d][w];
u32 c = trow[w >> 1];
u32 k = (w & 1u) ? ((c > 64u) ? c - 64u : 0u) : c;
total += (u32)__builtin_popcountll(v & s_pref[k]);
}
{
u32 c = trow[Wf >> 1];
__m128i v = _mm_loadu_si128((const __m128i*)(bs[0] + Wf));
for(int d=1;d<NS;d++) v=_mm_and_si128(v,_mm_loadu_si128((const __m128i*)(bs[d]+Wf)));
const u64 vl=(u64)_mm_cvtsi128_si64(v)&s_pref[c];
const u64 vh=(u64)_mm_extract_epi64(v,1)&((c>64u)?s_pref[c-64u]:0ull);
if(vl|vh){
const __m256i ec=_mm256_set1_epi8((char)cut);
if(vl){u32 m0=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)edgp)));
u32 m1=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)(edgp+32))));
total+=(u32)__builtin_popcountll(vl&((u64)m0|((u64)m1<<32)));}
if(vh){u32 m0=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)(edgp+64))));
u32 m1=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(ec,_mm256_loadu_si256((const __m256i*)(edgp+96))));
total+=(u32)__builtin_popcountll(vh&((u64)m0|((u64)m1<<32)));}}
}
return total;
}
#define T16E_QTCALC() \
const u32 *Avp_ = avpool + (size_t)i * STRIDE; \
__m256i qr_ = _mm256_or_si256(LDA((const __m256i *)rec), khi8v); \
__m256i qT = _mm256_min_epi32(qr_, _mm256_or_si256(LDU256(Avp_), notexlo)); \
__m256i qTh; \
if (k > 8) { \
__m256i qrh_ = _mm256_or_si256(LDU256((rec + 8)), khi8hv); \
__m256i Avmh_ = _mm256_or_si256(LDU256((Avp_ + 8)), notexloh); \
qTh = _mm256_min_epi32(qrh_, Avmh_); \
} else { qTh = all8; }
struct RankGatherMasks{alignas(16) u8 m[10][10][2][16]{};constexpr RankGatherMasks(){
for(unsigned a=0;a<10;a++)for(unsigned b=0;b<10;b++){for(unsigned h=0;h<2;h++)for(unsigned j=0;j<16;j++)m[a][b][h][j]=128;
if(a==b)continue;unsigned j=0;for(unsigned d=0;d<10;d++)if(d!=a&&d!=b){for(unsigned z=0;z<2;z++)m[a][b][d/8][2*j+z]=2*(d%8)+z;j++;}}}};
static constexpr RankGatherMasks rank_gather_masks{};
static inline __m128i compact_stream_ranks(const u16*bd,unsigned a,unsigned b){
u32 tail;__builtin_memcpy(&tail,bd+8,4);
return _mm_or_si128(_mm_shuffle_epi8(_mm_loadu_si128((const __m128i*)bd),_mm_load_si128((const __m128i*)rank_gather_masks.m[a][b][0])),_mm_shuffle_epi8(_mm_cvtsi32_si128(tail),_mm_load_si128((const __m128i*)rank_gather_masks.m[a][b][1])));
}
struct StreamComplements{u16 code[256]{};constexpr StreamComplements(){
for(unsigned m=0;m<256;m++){unsigned v=0,j=0;for(unsigned i=0;i<8;i++)if(!(m&(1u<<i))){v|=i<<(3*j);j++;}code[m]=(u16)v;}}};
static constexpr StreamComplements stream_complements{};
template<int KK>
__attribute__((target("avx2,popcnt")))
static void query_group(u32 N, u32 *out, u32 ds, u32 q0, u32 q1, u32 Q, u32 W) {
const u32 KS_C = (KK <= 8) ? 8u : (u32)KK;
const int k = KK;
const int K1 = KK - 1;
u32 *qo = s_qord, *qt = s_tmp;
#if MF_ASCR
const u32 d1 = (ds == 0) ? 1u : 0u;
const u32 e1 = (d1 < ds) ? d1 : d1 - 1;
const u32 dmx = (u32)g_dm, emx = (dmx < ds) ? dmx : dmx - 1u;
{
u32 *cntv = s_cntv;
for (u32 v = 0; v <= Q; v++) cntv[v] = 0;
for (u32 qi = q0; qi < q1; qi++) cntv[(qo[qi] >> 20) + 1]++;
{ u32 ac = q0; for (u32 v = 0; v <= Q; v++) { u32 c = cntv[v]; cntv[v] = ac; ac += c; } }
for (u32 qi = q0; qi < q1; qi++) { u32 v = qo[qi];
qt[cntv[(v >> 20) + 1]++] = v; }
{ u32 *swp = qo; qo = qt; qt = swp; }
}
#else
const u32 d1 = 0, e1 = 0;
#endif
if (g_lexsort) {
u32 *cntv = s_cntv;
for (int dd = k - 1; dd >= 0; dd--) {
if (dd == ds) continue;
for (u32 v = 0; v <= Q; v++) cntv[v] = 0;
for (u32 qi = q0; qi < q1; qi++) cntv[s_bdT[(size_t)dd * N + qo[qi]] + 1]++;
{ u32 ac = q0; for (u32 v = 0; v <= Q; v++) { u32 c = cntv[v]; cntv[v] = ac; ac += c; } }
for (u32 qi = q0; qi < q1; qi++) { u32 id = qo[qi]; qt[cntv[s_bdT[(size_t)dd * N + id] + 1]++] = id; }
{ u32 *swp = qo; qo = qt; qt = swp; }
}
for (u32 qi = q0; qi < q1; qi++) s_bka[qi] = s_bdT[(size_t)d1 * N + qo[qi]];
}
#define PF_DIST 4
#ifdef PF_DIST
for (u32 qi = q0; qi < q0 + PF_DIST && qi + PF_DIST < q1; qi++) {
u32 j = qo[qi + PF_DIST] & 0xFFFFFu;
const u16 *bdn = s_bd + (size_t)j * MAXK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + (g_plen_on ? s_pofs[(size_t)e * MAXQ + bdn[d]]
: ((size_t)e * (Q + 1) + bdn[d]) * W));
_mm_prefetch(pp, _MM_HINT_T0);
_mm_prefetch(pp + 64, _MM_HINT_T0);
_mm_prefetch(pp + 128, _MM_HINT_T0);
}
}
#endif
#if MF_ASCR
{

u32 cur_b = 0;
for (u32 w = 0; w < W; w++) s_ascr[w] = 0;
u32 qi = q0;
while (qi < q1) {
u32 b1 = qo[qi] >> 20;
u32 qe = qi + 1;
while (qe < q1 && (qo[qe] >> 20) == b1) qe++;
const u64 *bp1;
if (!g_lexsort) {
for (u32 bb = cur_b + 1; bb <= b1; bb++) {
u32 p0 = (bb == 1) ? 0 : s_doff[bb - 1];
u32 p1 = s_doff[bb];
for (u32 t = p0; t < p1; t++) { u32 q = s_delta[t]; s_ascr[q >> 6] |= 1ull << (q & 63); }
}
cur_b = b1;
bp1 = s_ascr;
} else {

bp1 = g_plen_on ? (s_bs + s_pofs[(size_t)e1 * MAXQ + b1])
: (s_bs + ((size_t)e1 * (Q + 1) + b1) * W);
u32 mx = 1;
for (u32 t = qi; t < qe; t++) { u32 rr = s_gt[ds][qo[t]]; if (rr > mx) mx = rr; }
u32 nwd = (mx >> 6) + 2;
if (nwd <= AS_WORDS) {
const u64 *src = bp1;
for (u32 w = 0; w < nwd; w++) s_ascr[w] = src[w];
bp1 = s_ascr;
}
}
for (u32 qq = qi; qq < qe; qq++) {
u32 i = qo[qq] & 0xFFFFFu;
const u16 *bd = s_bd + (size_t)i * MAXK;
#if MF_PFAOUT

{ u32 oo = qq + MF_PFAOUTD; if (oo < qe) _mm_prefetch((const char *)(out + (qo[oo] & 0xFFFFFu)), _MM_HINT_T0); }
#endif
#if MF_PFA > 0
{
u32 qj = qq + MF_PFA;
if (qj < qe) {
u32 j = qo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(s_bd + (size_t)j * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_g + j), _MM_HINT_T0);
}
}
#endif
const u32 R = s_g[i] >> 4;
u32 cnt = 0;
if (R && !g_skip_and) {
const u64 *bp[MAXK];
u16 brank[MAXK];
int nbx = 0;
for (int e = 0; e < K1; e++) {
if (g_mask_ok && e == (int)emx) continue;
if constexpr(KK!=10){int rd=(e<ds)?e:e+1; brank[nbx]=bd[rd];}
if (e == (int)e1) bp[nbx++] = bp1;
else { int d = (e < ds) ? e : e + 1;
bp[nbx++] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bd[d]])
: (s_bs + ((size_t)e * (Q + 1) + bd[d]) * W); }
}
if(g_mask_ok && nbx==8){
__m128i ranks; if constexpr(KK==10)ranks=compact_stream_ranks(bd,ds,dmx);else ranks=_mm_loadu_si128((const __m128i*)brank);
const __m128i lanes=_mm_setr_epi16(0,1,2,3,4,5,6,7);
int selected[4];unsigned used=0;
#pragma GCC unroll 4
for(int z=0;z<4;z++){
__m128i v=_mm_minpos_epu16(ranks);
unsigned j=(unsigned)_mm_extract_epi16(v,1);
selected[z]=j;used|=1u<<j;
ranks=_mm_or_si128(ranks,_mm_cmpeq_epi16(lanes,_mm_set1_epi16(j)));
}
const u64* ordered[8];
for(int z=0;z<4;z++)ordered[z]=bp[selected[z]];
unsigned rest=stream_complements.code[used];
for(int z=0;z<4;z++){ordered[4+z]=bp[rest&7u];rest>>=3;}
for(int z=0;z<8;z++)bp[z]=ordered[z];
}else if(g_mask_ok && nbx>=8){
for(int z=0;z<4;z++){
int best=z;
u16 minrank=brank[z];
for(int j=z+1;j<nbx;j++){
const u16 rank=brank[j];
const bool less=rank<minrank;
best=less?j:best;
minrank=less?rank:minrank;
}
const u64*p=bp[z];bp[z]=bp[best];bp[best]=p;
u16 rr=brank[z];brank[z]=brank[best];brank[best]=rr;
}
}
cnt = g_mask_ok
? and_popcount_pm<KK - 2>(bp, s_tm + s_tofs[bd[dmx]], s_edg + ((size_t)(R >> 7) << 7), (R >> 7) << 1, R & 127u)
: and_popcount_range<KK - 1>(bp, R >> 6, R & 63u);
}
out[i] = cnt;
}
qi = qe;
}
}
#else
for (u32 qi = q0; qi < q1; qi++) {
u32 i = qo[qi];
const u16 *bd = s_bd + (size_t)i * MAXK;
#if MF_PFA > 0
{
u32 qj = qi + MF_PFA;
if (qj < q1) {
u32 j = qo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(s_bd + (size_t)j * MAXK), _MM_HINT_T0);
_mm_prefetch((const char *)(s_g + j), _MM_HINT_T0);
}
}
#if MF_PFAOUT
{ u32 oo = qi + MF_PFAOUTD;
if (oo < q1) _mm_prefetch((const char *)(out + qo[oo]), _MM_HINT_T0); }
#endif
#endif
#ifdef PF_DIST
if (qi + PF_DIST < q1) {
u32 j = qo[qi + PF_DIST] & 0xFFFFFu;
const u16 *bdn = s_bd + (size_t)j * MAXK;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const char *pp = (const char *)(s_bs + (g_plen_on ? s_pofs[(size_t)e * MAXQ + bdn[d]]
: ((size_t)e * (Q + 1) + bdn[d]) * W));
_mm_prefetch(pp, _MM_HINT_T0);
_mm_prefetch(pp + 64, _MM_HINT_T0);
_mm_prefetch(pp + 128, _MM_HINT_T0);
}
}
#endif
const u32 R = s_g[i] >> 4;
u32 cnt = 0;
if (R && !g_skip_and) {
const u64 *bp[MAXK];
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
bp[e] = g_plen_on ? (s_bs + s_pofs[(size_t)e * MAXQ + bd[d]])
: (s_bs + ((size_t)e * (Q + 1) + bd[d]) * W);
#ifdef DBG_PLEN
if (g_plen_on) {
u32 need = (R >> 6) + ((R & 63) ? 1 : 0);
if (need > s_plen[(size_t)e * MAXQ + bd[d]])
printf("DBG ds=%d e=%d d=%d b=%u R=%u need=%u len=%u\n", ds, e, d, bd[d], R, need, s_plen[(size_t)e * MAXQ + bd[d]]);
}
#endif
}
cnt = and_popcount_range<KK - 1>(bp, R >> 6, R & 63u);
}
out[i] = cnt;
}
#endif
if (g_skip_fringe) return;
u32 *const avpool = s_avpool;
for (int d = 0; d < k; d++) {
if (d == ds) continue;
const u32 *fo = s_frord_[d];
u32 exmask = 0;
for (int e = 0; e < d; e++) if (e != ds) exmask |= 1u << e;
u32 hiA[8], hiAh[8];
for (int e = 0; e < 8; e++) hiA[e] = ((exmask >> e) & 1u) ? 0u : 0x7FFFFFFFu;
for (int e = 8; e < 16; e++) hiAh[e - 8] = ((exmask >> e) & 1u) ? 0u : 0x7FFFFFFFu;
const __m256i notexlo = LDU256(hiA);
const __m256i notexloh = LDU256(hiAh);
const __m256i all8 = _mm256_set1_epi32(-1);
const u32 *const odd = s_ord[d];
alignas(16) u8 qmask_bytes[16],dmask_bytes[16];
for(int e=0;e<16;e++){qmask_bytes[e]=(e<d&&e!=(int)ds)?0:255;dmask_bytes[e]=(e==d)?255:0;}
const __m128i qmask=_mm_load_si128((const __m128i*)qmask_bytes),dmask=_mm_load_si128((const __m128i*)dmask_bytes);
__m256i qidx[16];
for(int e=0;e<k-1;e++)qidx[e]=_mm256_set1_epi8((char)(e<d?e:e+1));
const u8 *const sgbase_d = s_sig ? (s_sig + (size_t)d * (k-1) * MF_SPL) : (const u8 *)0;
const u32 *const gt_d = s_gt[d];
const u32 *const fpos_d = s_fpos + (size_t)d * MAXQ;
for (u32 qi = q0; qi < q1; qi++) {
u32 i = fo[qi] & 0xFFFFFu;
#if MF_PFB > 0
{
u32 qj = qi + MF_PFB3;
if (qj < q1) {
u32 j = fo[qj] & 0xFFFFFu;
_mm_prefetch((const char *)(s_pm + (size_t)j * STRIDE), _MM_HINT_T0);
_mm_prefetch((const char *)(gt_d + j), _MM_HINT_T0);
_mm_prefetch((const char *)(out + j), _MM_HINT_T0);
}
}
#endif
const u32 lo = fpos_d[fo[qi] >> 20];
const u32 hi = gt_d[i];
if (lo >= hi) continue;
const u32 *rec = s_pm + (size_t)i * STRIDE;
const u8 *const qpad = ((const u8 *)rec) + 40;
u32 add = 0;
const u32 *c0 = s_sdmp[d] ? (s_sdmp[d] + (size_t)lo * KS_C) : 0;
if (g_use_filt) { T16E_QTCALC();
const u32 w0 = lo >> 6;
const u32 nw = ((hi - 1) >> 6) - w0 + 1;
u64 *fb = s_fbuf;
const u64 wcs = (u64)N / g_Qc + 1;
const u32 FW = g_fbm_W;
int first = 1;
#if MF_FR_NOREAD
first = 0;
for (u32 w = 0; w < nw; w++) fb[w] = 0;
#endif
for (int e = 0; e < k; e++) {
if (e == d) continue;
u32 c = (u32)((u64)rec[e] / wcs) + 1;
if (c > g_Qc) c = g_Qc;
const u64 *row = s_fbm + ((size_t)(d * k + e) * (g_Qc + 1) + c) * FW + w0;
if (first) { for (u32 w = 0; w < nw; w++) fb[w] = row[w]; first = 0; }
else { for (u32 w = 0; w < nw; w++) fb[w] &= row[w]; }
}
fb[0] &= ~0ull << (lo & 63);
u32 r2 = hi & 63u;
if (r2) fb[nw - 1] &= (1ull << r2) - 1;
for (u32 w = 0; w < nw; w++) {
u64 vv = fb[w];
#if MF_FR_NOCAND
vv = 0;
#endif
while (vv) {
int t = __builtin_ctzll(vv);
vv &= vv - 1;
u32 j = ((w0 + w) << 6) + (u32)t;
const u32 *cp = c0 ? (c0 + (size_t)(j - lo) * KS_C) : (s_pm + (size_t)s_ord[d][j] * STRIDE);
__m256i pv = LDU256(cp);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
ok &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
add += ok;
}
}
out[i] += add;
continue;
}
if (g_sig_on && (hi - lo) >= 2) {
__m256i qsb[16];
{
__m128i qr8=_mm_loadu_si128((const __m128i*)qpad);
__m128i qb8=_mm_loadl_epi64((const __m128i*)(qpad+k));
if constexpr(KK>=10)qb8=_mm_insert_epi8(qb8,qpad[k+8],8);
__m128i qs=_mm_or_si128(_mm_min_epu8(qr8,_mm_or_si128(qb8,qmask)),dmask);
__m256i qwide=_mm256_broadcastsi128_si256(qs);
for(int e=0;e<k-1;e++)qsb[e]=_mm256_shuffle_epi8(qwide,qidx[e]);
}
const u8 *const sgbase = sgbase_d;
u32 aj = lo, aacc = 0, aexact = 0;
for (; aj + 32 <= hi; aj += 32) {
__m256i ac = _mm256_subs_epu8(LDU256(sgbase + aj), qsb[0]);
for (int e = 1; e < k-1; e++) {
__m256i cv = LDU256(sgbase + (size_t)e * MF_SPL + aj);
ac = _mm256_or_si256(ac, _mm256_subs_epu8(cv, qsb[e]));
}
__m256i lt = _mm256_cmpeq_epi8(ac, _mm256_setzero_si256());
u32 ltm = (u32)_mm256_movemask_epi8(lt);
u32 amb = (u32)_mm256_movemask_epi8(_mm256_cmpeq_epi8(ac, _mm256_set1_epi8(1)));
aacc += (u32)__builtin_popcount(ltm);
if (amb) { T16E_QTCALC();
__m256i lv=_mm256_and_si256(qT,_mm256_set1_epi32(65535));
__m128i packed_low=_mm_packus_epi32(_mm256_castsi256_si128(lv),_mm256_extracti128_si256(lv,1));
__m256i hv=_mm256_and_si256(_mm256_srli_epi32(qT,16),_mm256_set1_epi32(15));
__m128i hw=_mm_packus_epi32(_mm256_castsi256_si128(hv),_mm256_extracti128_si256(hv,1));
__m128i hb=_mm_packus_epi16(hw,hw);
u32 packed_high=(u32)_pext_u64((u64)_mm_cvtsi128_si64(hb),0x0f0f0f0f0f0f0f0full);
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
if(KK==10 && !c0 && defer_count<DEFER_CAP){
u32*e=defer_entries+(size_t)defer_count++*9;
e[0]=i;e[1]=odd[aj+(u32)t];
_mm_storeu_si128((__m128i*)(e+2),packed_low);e[6]=packed_high;
_mm_storel_epi64((__m128i*)(e+7),_mm256_castsi256_si128(qTh));
continue;
}
const u32 *cp = c0 ? (c0 + (size_t)(aj + (u32)t - lo) * KS_C) : (s_pm + (size_t)odd[aj + (u32)t] * STRIDE);
__m256i pv = LDU256(cp);
u32 okl = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
okl &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
aacc += okl;
}
}
}
{
u32 r = hi - aj;
if (r) {
u32 base, lk;
if (hi >= 32u) { base = hi - 32u; lk = 32u - r; }
else           { base = 0u;      lk = lo; }
u32 kmask = ((r >= 32u) ? 0xFFFFFFFFu : ((1u << r) - 1u)) << lk;
const u8 *const tp = sgbase + base;
__m256i ac = _mm256_subs_epu8(LDU256(tp), qsb[0]);
for (int e = 1; e < k-1; e++) {
__m256i cv = LDU256(tp + (size_t)e * MF_SPL);
ac = _mm256_or_si256(ac, _mm256_subs_epu8(cv, qsb[e]));
}
__m256i lt = _mm256_cmpeq_epi8(ac, _mm256_setzero_si256());
u32 ltm = ((u32)_mm256_movemask_epi8(lt)) & kmask;
u32 amb = ((u32)_mm256_movemask_epi8(_mm256_cmpeq_epi8(ac, _mm256_set1_epi8(1)))) & kmask;
aacc += (u32)__builtin_popcount(ltm);
if (amb) { T16E_QTCALC();
__m256i lv=_mm256_and_si256(qT,_mm256_set1_epi32(65535));
__m128i packed_low=_mm_packus_epi32(_mm256_castsi256_si128(lv),_mm256_extracti128_si256(lv,1));
__m256i hv=_mm256_and_si256(_mm256_srli_epi32(qT,16),_mm256_set1_epi32(15));
__m128i hw=_mm_packus_epi32(_mm256_castsi256_si128(hv),_mm256_extracti128_si256(hv,1));
__m128i hb=_mm_packus_epi16(hw,hw);
u32 packed_high=(u32)_pext_u64((u64)_mm_cvtsi128_si64(hb),0x0f0f0f0f0f0f0f0full);
while (amb) {
int t = __builtin_ctz(amb); amb &= amb - 1;
if(KK==10 && !c0 && defer_count<DEFER_CAP){
u32*e=defer_entries+(size_t)defer_count++*9;
e[0]=i;e[1]=odd[base+(u32)t];
_mm_storeu_si128((__m128i*)(e+2),packed_low);e[6]=packed_high;
_mm_storel_epi64((__m128i*)(e+7),_mm256_castsi256_si128(qTh));
continue;
}
const u32 *cp = c0 ? (c0 + (size_t)(base + (u32)t - lo) * KS_C) : (s_pm + (size_t)odd[base + (u32)t] * STRIDE);
__m256i pv = LDU256(cp);
u32 okl = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDU256((cp + 8));
okl &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
aacc += okl;
}
}
}
}
add = aacc;
} else if (c0) {
T16E_QTCALC();
if (k <= 8) {
const u32 *c = c0;
u32 a0 = 0, a1 = 0, a2 = 0, a3 = 0;
u32 j = lo;
for (; j + 4 <= hi; j += 4) {
__m256i p0 = LDU256((c));
__m256i p1 = LDU256((c + KS_C));
__m256i p2 = LDU256((c + 2 * KS_C));
__m256i p3 = LDU256((c + 3 * KS_C));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p0), all8);
a1 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p1), all8);
a2 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p2), all8);
a3 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p3), all8);
c += 4 * KS_C;
}
for (; j < hi; j++, c += KS_C) {
__m256i pv = LDU256(c);
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
}
add = a0 + a1 + a2 + a3;
} else {
const u32 *c = c0;
u32 a0 = 0, a1 = 0, a2 = 0, a3 = 0;
u32 j = lo;
for (; j + 4 <= hi; j += 4) {
__m256i p0 = LDU256((c));
__m256i p1 = LDU256((c + KS_C));
__m256i p2 = LDU256((c + 2 * KS_C));
__m256i p3 = LDU256((c + 3 * KS_C));
__m256i h0 = LDU256((c + 8));
__m256i h1 = LDU256((c + KS_C + 8));
__m256i h2 = LDU256((c + 2 * KS_C + 8));
__m256i h3 = LDU256((c + 3 * KS_C + 8));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p0), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h0)), kokhi);
a1 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p1), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h1)), kokhi);
a2 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p2), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h2)), kokhi);
a3 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, p3), all8) & (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, h3)), kokhi);
c += 4 * KS_C;
}
for (; j < hi; j++, c += KS_C) {
__m256i pv = LDU256(c);
__m256i pvh = LDU256((c + 8));
a0 += (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8) &
(u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
add = a0 + a1 + a2 + a3;
}
} else {
T16E_QTCALC();
for (u32 j = lo; j < hi; j++) {
const u32 *c = s_pm + (size_t)odd[j] * STRIDE;
__m256i pv = LDA((const __m256i *)c);
u32 ok = (u32)_mm256_testc_si256(_mm256_cmpgt_epi32(qT, pv), all8);
if (k > 8) {
__m256i pvh = LDA((const __m256i *)(c + 8));
ok &= (u32)_mm256_testc_si256(_mm256_andnot_si256(kbadhi, _mm256_cmpgt_epi32(qTh, pvh)), kokhi);
}
add += ok;
}
}
out[i] += add;
}
if constexpr(KK==10)flush_deferred(out,odd);
}
}
static u8 cached_signature[(size_t)MAXN*16] __attribute__((aligned(64)));
template<int K>
__attribute__((target("avx2")))
static void solve_mf(u32 N, const unsigned **x, u32 *out) {
const int k = K;
const u32 W = ((N + 63) / 64 + 7u) & ~7u;
g_W = W;
#ifdef MF_SKIP_AND
g_skip_and = 1;
#endif
#ifdef MF_FILT
g_use_filt = 1;
#endif
#ifdef MF_NOFILT
g_use_filt = 0;
#endif
#ifdef MF_Q
g_Q = MF_Q; g_B = (u32)((N + (MF_Q) - 1) / (MF_Q));
#endif
#ifdef MF_FILT
g_use_filt = 1;
#endif
#ifdef MF_NOFILT
g_use_filt = 0;
#endif
#ifdef MF_SKIP_FRINGE
g_skip_fringe = 1;
#endif
if (!g_Q) {
u64 r = (u64)N, s2 = 0;
while (s2 * s2 < r) s2++;
u64 overhead = (u64)(5 * k + 21) * N * 4;
overhead += (u64)k * k * 4 * N;
overhead += (u64)k * k * ((u64)N + 64);
overhead += (u64)N * ((k <= 8) ? 8u : (u32)k) * 4 * k;
u64 budget = ((u64)MF_BUDGETMB << 20);
if (budget > overhead + ((u64)64 << 20)) budget -= overhead; else budget = (u64)64 << 20;
#if MF_PLEN
static const u32 kfill[7] = {72, 67, 62, 58, 54, 50, 46};
u64 perfill = ((u64)(k - 1) * W * 8) * kfill[k - 4] / 100;
#else
u64 perfill = (u64)(k - 1) * W * 8;
#endif
u64 Qmem = budget / (perfill ? perfill : 1);
if (Qmem < 8) Qmem = 8;
static const u32 kscale[7] = {82, 91, 100, 108, 115, 122, 129};
u32 q = (u32)((s2 * MF_QCOEF + 99) / 100);
q = (u32)(((u64)q * kscale[k - 4] + 99) / 100);
if ((u64)q > Qmem) q = (u32)Qmem;
if (q > N) q = N;
if(q>=MAXQ)q=MAXQ-1;
g_Q = q;
g_B = (N + q - 1) / q;
}
for (u32 t = 0; t < 256u; t++) s_pref[t] = (t >= 64u) ? ~0ull : ((1ull << t) - 1ull);
g_mask_on = MF_PFXMASK;
const u32 Q = g_Q, B = g_B;
const u64 bmag = ((1ull << 40) + B - 1) / B;
#if MF_PLEN
g_plen_on = 1;
#endif
#if MF_WTRIM
u32 Wpool = W;
#else
const u32 Wpool = W;
#endif
#if MF_FILTAUTO
if (!g_use_filt && B >= 400) g_use_filt = 1;
#endif
if (g_use_filt && (u64)k * k * (g_Qc + 1) * W * 8 > ((u64)700 << 20)) g_use_filt = 0;
#if !MF_FILTAUTO
g_use_filt = 0;
#endif
{
int lo8[8], hi8[8], bad8[8];
for (int e = 0; e < 8; e++) lo8[e] = (e < k) ? 0 : 0x7FFFFFFF;
for (int e = 0; e < 8; e++) hi8[e] = (8 + e < k) ? 0 : 0x7FFFFFFF;
for (int e = 0; e < 8; e++) bad8[e] = (8 + e < k) ? 0 : -1;
khi8v = LDU256(lo8);
khi8hv = LDU256(hi8);
kbadhi = LDU256(bad8);
kokhi = _mm256_xor_si256(kbadhi, _mm256_set1_epi32(-1));
}
const int K1 = k - 1;
for (int d = 0; d < k; d++) {
const unsigned *xd = x[d];
u32 *od = s_ord[d];
u8*hc=compact_hist;u32*ct=compact_cursor;
for(u32 i=0;i<=N;i++)hc[i]=0;
u32 lim=N>MF_ORDPF?N-MF_ORDPF:0;
for(u32 i=0;i<lim;i++){
Z16S_PFW(hc+xd[i+MF_ORDPF]);
hc[xd[i]]++;
}
for(u32 i=lim;i<N;i++){u32 v=xd[i];hc[v<N?v:0]++;}
u32 sum=0;
u32 hv=0;
for(;hv+8<=N+1;hv+=8){
__m256i c=_mm256_cvtepu8_epi32(_mm_loadl_epi64((const __m128i*)(hc+hv)));
__m256i p=_mm256_add_epi32(c,_mm256_slli_si256(c,4));
p=_mm256_add_epi32(p,_mm256_slli_si256(p,8));
__m128i lo=_mm256_castsi256_si128(p),hi=_mm256_extracti128_si256(p,1);
hi=_mm_add_epi32(hi,_mm_shuffle_epi32(lo,255));
__m256i inc=_mm256_inserti128_si256(_mm256_castsi128_si256(lo),hi,1);
__m256i ex=_mm256_add_epi32(_mm256_sub_epi32(inc,c),_mm256_set1_epi32(sum));
_mm256_storeu_si256((__m256i*)(ct+hv),ex);
sum+=(u32)_mm_extract_epi32(hi,3);
}
for(;hv<=N;hv++){u32 c=hc[hv];ct[hv]=sum;sum+=c;}
if(sum==N && N<1048576u){
u32*gt=s_gt[d];u32*pp=s_pos[d];
for(u32 i=0;i<N;i++){
if(i+2*MF_SCAPF<N){_mm_prefetch((const char*)(ct+xd[i+2*MF_SCAPF]),_MM_HINT_T0);}
if(i+MF_SCAPF<N){u32 w=ct[xd[i+MF_SCAPF]];Z16S_PFW(od+(w&0xfffffu)+(w>>20));}
u32 v=xd[i];
u32 w=ct[v],st=w&0xfffffu,pos=st+(w>>20);ct[v]=w+(1u<<20);
od[pos]=i;pp[i]=pos;gt[i]=st;
#if MF_FB2
s_posp[(size_t)i*MAXK+d]=pos;
#endif
u32 num=(ct[v+1]&0xfffffu)-1u;
u32 bb=(u32)(((u64)num*bmag)>>40);
s_bdT[(size_t)d*N+i]=(u16)bb;
}
}else{
for (u32 i = 0; i <= N; i++) s_cntv[i] = 0;
#if MF_ORDPF > 0
{ u32 i = 0;
for (; i + MF_ORDPF < N; i++) {
u32 vn = xd[i + MF_ORDPF];
Z16S_PFW(s_cntv + (vn < N ? vn : 0));
u32 v = xd[i]; s_cntv[v < N ? v : 0]++;
}
for (; i < N; i++) { u32 v = xd[i]; s_cntv[v < N ? v : 0]++; }
}
#else
for (u32 i = 0; i < N; i++) { u32 v = xd[i]; s_cntv[v < N ? v : 0]++; }
#endif
{ u32 s = 0; for (u32 i = 0; i <= N; i++) { u32 c = s_cntv[i]; s_cntv[i] = s; s_tmp[i] = s; s += c; } }
#if MF_FB2
for (u32 i = 0; i < N; i++) {
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; od[q] = i;
s_posp[(size_t)i * MAXK + d] = q;
s_pos[d][i] = q;
}
#else
{
u32 *pp = s_pos[d];
for (u32 i = 0; i < N; i++) {
if (i + 2*MF_SCAPF < N) { u32 v2 = xd[i + 2*MF_SCAPF]; if (v2 >= N) v2 = 0;
_mm_prefetch((const char *)(s_tmp + v2), _MM_HINT_T0); }
if (i + MF_SCAPF < N) { u32 vf = xd[i + MF_SCAPF]; if (vf >= N) vf = 0;
Z16S_PFW(&od[s_tmp[vf]]); }
u32 v = xd[i]; if (v >= N) v = 0; u32 q = s_tmp[v]++; od[q] = i; pp[i] = q;
}
}
#endif
{ u32 *gt = s_gt[d];
for (u32 i = 0; i < N; i++) {
{if (i + MF_CNTPF < N) { u32 vp = xd[i + MF_CNTPF]; if (vp >= N) vp = 0;
_mm_prefetch((const char *)(s_cntv + vp), _MM_HINT_T0); }}
u32 v = xd[i]; if (v >= N) v = 0;
gt[i] = s_cntv[v];
u32 num = s_cntv[v + 1] - 1u; if (num > N) num = N;
u32 bb = (u32)(((u64)num * bmag) >> 40);
{ u16 bbx = (bb > Q - 1 ? Q - 1 : (u16)bb);
s_bdT[(size_t)d * N + i] = bbx; }
} }
}
BVAL(d, 0) = 0; FPOS(d, 0) = 0;
for (u32 b = 1; b < Q; b++) {
u32 pos = b * B < N ? b * B : N - 1;
u32 v = xd[od[pos]];
BVAL(d, b) = v;
u32 gs = pos;
while (gs > 0 && xd[od[gs - 1]] == v) gs--;
FPOS(d, b) = gs;
}
BVAL(d, Q) = 0xFFFFFFFFu; FPOS(d, Q) = 0;
}
if(k==10){
u32 i=0;
for(;i+8<=N;i+=8){
__m128i c0=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)0*N+i));
__m128i c1=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)1*N+i));
__m128i c2=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)2*N+i));
__m128i c3=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)3*N+i));
__m128i c4=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)4*N+i));
__m128i c5=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)5*N+i));
__m128i c6=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)6*N+i));
__m128i c7=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)7*N+i));
__m128i c8=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)8*N+i));
__m128i c9=_mm_loadu_si128((const __m128i*)(s_bdT+(size_t)9*N+i));
__m128i t0=_mm_unpacklo_epi16(c0,c1),t1=_mm_unpackhi_epi16(c0,c1);
__m128i t2=_mm_unpacklo_epi16(c2,c3),t3=_mm_unpackhi_epi16(c2,c3);
__m128i t4=_mm_unpacklo_epi16(c4,c5),t5=_mm_unpackhi_epi16(c4,c5);
__m128i t6=_mm_unpacklo_epi16(c6,c7),t7=_mm_unpackhi_epi16(c6,c7);
__m128i u0=_mm_unpacklo_epi32(t0,t2),u1=_mm_unpackhi_epi32(t0,t2);
__m128i u2=_mm_unpacklo_epi32(t1,t3),u3=_mm_unpackhi_epi32(t1,t3);
__m128i u4=_mm_unpacklo_epi32(t4,t6),u5=_mm_unpackhi_epi32(t4,t6);
__m128i u6=_mm_unpacklo_epi32(t5,t7),u7=_mm_unpackhi_epi32(t5,t7);
__m128i w0=_mm_unpacklo_epi64(u0,u4),w1=_mm_unpackhi_epi64(u0,u4);
__m128i w2=_mm_unpacklo_epi64(u1,u5),w3=_mm_unpackhi_epi64(u1,u5);
__m128i w4=_mm_unpacklo_epi64(u2,u6),w5=_mm_unpackhi_epi64(u2,u6);
__m128i w6=_mm_unpacklo_epi64(u3,u7),w7=_mm_unpackhi_epi64(u3,u7);
__m128i p0=_mm_unpacklo_epi16(c8,c9),p1=_mm_unpackhi_epi16(c8,c9);
u8* rb=(u8*)(s_bd+(size_t)i*MAXK);
_mm_storeu_si128((__m128i*)(rb+0),w0);*(u32*)(rb+16)=(u32)_mm_extract_epi32(p0,0);
_mm_storeu_si128((__m128i*)(rb+20),w1);*(u32*)(rb+36)=(u32)_mm_extract_epi32(p0,1);
_mm_storeu_si128((__m128i*)(rb+40),w2);*(u32*)(rb+56)=(u32)_mm_extract_epi32(p0,2);
_mm_storeu_si128((__m128i*)(rb+60),w3);*(u32*)(rb+76)=(u32)_mm_extract_epi32(p0,3);
_mm_storeu_si128((__m128i*)(rb+80),w4);*(u32*)(rb+96)=(u32)_mm_extract_epi32(p1,0);
_mm_storeu_si128((__m128i*)(rb+100),w5);*(u32*)(rb+116)=(u32)_mm_extract_epi32(p1,1);
_mm_storeu_si128((__m128i*)(rb+120),w6);*(u32*)(rb+136)=(u32)_mm_extract_epi32(p1,2);
_mm_storeu_si128((__m128i*)(rb+140),w7);*(u32*)(rb+156)=(u32)_mm_extract_epi32(p1,3);
}
for(;i<N;i++){u16 *row = s_bd + (size_t)i * MAXK; for (int d = 0; d < k; d++) row[d] = s_bdT[(size_t)d * N + i];}
} else {
for (u32 i = 0; i < N; i++) {
u16 *row = s_bd + (size_t)i * MAXK;
for (int d = 0; d < k; d++) row[d] = s_bdT[(size_t)d * N + i];
}
}
{
u32 nn = N - 1; u32 sh = 0;
while (nn > 255u) { nn >>= 1; sh++; }
g_sigsh = sh;
g_sigmul=N>1?(u32)((255ULL<<23)/(N-1)):0;
size_t need = (size_t)k * (k-1) * MF_SPL;
static u8 *sigpool = 0; static size_t sigcap = 0;
if (need > ((size_t)220 << 20) || (size_t)N + 32 > MF_SPL) { sigpool = 0; sigcap = 0; }
else if (need > sigcap) { sigpool = (u8 *)pool_alloc(need); sigcap = sigpool ? need : 0; }
if (sigpool) {
s_sig = sigpool;
g_sig_on = 1;
g_sig_merged = 0;
}
}
#if MF_NOFILTB
g_use_filt = 0;
#endif
{
size_t needav = (size_t)N * STRIDE * 4 + 256;
if (needav > s_avcap) {
s_avpool = (u32 *)pool_alloc(needav);
s_avcap = s_avpool ? needav : 0;
}
}
{
size_t mrn = (size_t)MAXK * MAXK * MAXQ;
for (size_t z = 0; z < mrn; z++) s_maxr[z] = 0;
}
if(k==10){
u32 i=0;
for(;i+8<=N;i+=8){
__m256i v=_mm256_slli_epi32(_mm256_loadu_si256((const __m256i*)(s_gt[0]+i)),4);
for(unsigned d=1;d<10;++d){
__m256i q=_mm256_or_si256(_mm256_slli_epi32(_mm256_loadu_si256((const __m256i*)(s_gt[d]+i)),4),_mm256_set1_epi32(d));
v=_mm256_min_epu32(v,q);
}
_mm256_storeu_si256((__m256i*)(s_tmp+i),v);
}
for(;i<N;++i){u32 v=s_gt[0][i]<<4;for(unsigned d=1;d<10;++d){u32 q=(s_gt[d][i]<<4)|d;if(q<v)v=q;}s_tmp[i]=v;}
}
for (u32 i = 0; i < N; i++) {
u32 best;int ds;
if(k==10){best=s_tmp[i]>>4;ds=s_tmp[i]&15u;}else{
u64 bpk = ((u64)s_gt[0][i] << 4);
for (int d = 1; d < k; d++) {
u64 g = ((u64)s_gt[d][i] << 4) | (u64)d;
bpk = (g < bpk) ? g : bpk;
}
best = (u32)(bpk >> 4);
ds = (int)(bpk & 15u);
}
s_g[i] = (best << 4) | (u32)ds;
const u16 *bdv = s_bd + (size_t)i * MAXK;
u32 *av = s_avpool + (size_t)i * STRIDE;
u32 *mr = s_maxr + ((size_t)ds * MAXK) * MAXQ;



fold_dimension[i]=(u8)ds;
for (int d = 0; d < k; d++) {
if (d == ds) { av[d] = 0x7FFFFFFFu; continue; }
u32 b = bdv[d];
av[d] = d+1<k ? BVAL(d, b) : 0x7FFFFFFFu;
if (g_plen_on && best > mr[(size_t)d * MAXQ + b])
mr[(size_t)d * MAXQ + b] = best;
}
}


if (s_sig) {
const u32 sh = g_sigsh;
if(k==10) prepare_cached_signatures(cached_signature,x,N);
for (u32 i = 0; i < N; i++) {
u32 *row = s_pm + (size_t)i * STRIDE;
for (int d = 0; d < k; d++) row[d] = x[d][i];
const u32 *av = s_avpool + (size_t)i * STRIDE;
u8 *pad = (u8 *)row + 40;
if(k==10){ const u8 *cs=cached_signature+(size_t)i*10; __m128i cv=_mm_sub_epi8(_mm_loadu_si128((const __m128i*)cs),_mm_set1_epi8(1)); _mm_storeu_si128((__m128i*)pad,cv); } else { for (int e = 0; e < k; e++) { u32 v = sigfull(row[e]); pad[e] = (u8)(v ? v-1u : 0u); } }
if(k==10){ __m256i a8=_mm256_loadu_si256((const __m256i*)av);
__m256i s8=_mm256_max_epu32(_mm256_srli_epi32(_mm256_mullo_epi32(a8,_mm256_set1_epi32((int)g_sigmul)),23),_mm256_set1_epi32(1));
__m128i lo=_mm256_castsi256_si128(s8), hi=_mm256_extracti128_si256(s8,1);
__m128i b16=_mm_packus_epi32(lo,hi); __m128i b8=_mm_packus_epi16(b16,b16);
b8=_mm_sub_epi8(b8,_mm_set1_epi8(1)); _mm_storel_epi64((__m128i*)(pad+10),b8);
u32 v8=sigfull(av[8]); pad[18]=(u8)(v8?v8-1u:0u); } else { for (int e = 0; e + 1 < k; e++) { u32 v = sigfull(av[e]); pad[k + e] = (u8)(v ? v-1u : 0u); } }
}
} else {
for (u32 i = 0; i < N; i++) {
u32 *p = s_pm + (size_t)i * STRIDE;
for (int d = 0; d < k; d++) p[d] = x[d][i];
}
}
{
for (u32 v = 0; v <= (u32)k; v++) s_cntv[v] = 0;
for (u32 i = 0; i < N; i++) s_cntv[(s_g[i] & 15u) + 1]++;
{ u32 ac = 0; for (u32 v = 0; v <= (u32)k; v++) { u32 c = s_cntv[v]; s_cntv[v] = ac; ac += c; } }
for (u32 i = 0; i < N; i++) {
{if (i + MF_GQPF < N) _mm_prefetch((const char *)(s_g + i + MF_GQPF), _MM_HINT_T0);}
u32 ds = s_g[i] & 15u; s_qord[s_cntv[ds + 1]++] = i | ((u32)s_bdT[(size_t)(ds ? 0u : 1u) * N + i] << 20); }
}
u32 gstart[MAXK + 2];
{ gstart[0]=0; for(int d=1;d<=k;++d)gstart[d]=s_cntv[d]; gstart[k+1]=N; }
for (int d = 0; d < k; d++) {
u32 pos[MAXK];
for (int ds = 0; ds < k; ds++) pos[ds] = gstart[ds];
const u32 last_bucket=(N-1u)/B;
u32 r=0;
for(u32 b=0;b<=last_bucket;++b){
 const u32 end=b==last_bucket?N:FPOS(d,b+1);
 for(;r<end;++r){
  if(r+MF_FRDPF<N){u32 ip=s_ord[d][r+MF_FRDPF];_mm_prefetch((const char*)(fold_dimension+ip),_MM_HINT_T0);}
  u32 id=s_ord[d][r];u32 dst=pos[fold_dimension[id]]++;
  s_frord_[d][dst]=id|(b<<20);
 }
}
}
#if MF_NOSDMP
g_nosdmp = 1;
#endif
if (!g_nosdmp) {
u32 KS = k;
#if MF_KSPAD
if (k <= 8) KS = 8;
#endif
size_t per = (size_t)N * KS * 4;
size_t lim = (size_t)150 << 20;
if (k >= 9) lim = (size_t)470 << 20;
if (per * k <= lim) {
static u32 *pool = 0; static size_t cap = 0;
if (per * k > cap) { pool = (u32 *)pool_alloc(per * k + 256); cap = per * k; }
if (pool) {
g_KS = KS;
for (int d = 0; d < k; d++) {
s_sdmp[d] = pool + (size_t)d * N * g_KS;
const u32 *od = s_ord[d];
u32 *dst = s_sdmp[d];
const u32 KSx = g_KS;
for (u32 j = 0; j < N; j++) {
#if MF_PFB > 0
if (j + MF_PFB < N) _mm_prefetch((const char *)(s_pm + (size_t)od[j + MF_PFB] * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)od[j] * STRIDE;
u32 *dp = dst + (size_t)j * KSx;
for (u32 e = 0; e < KSx; e++) dp[e] = (e < (u32)k) ? row[e] : 0u;
if (s_sig) {
u8 *sb = s_sig + (size_t)d * (k-1) * MF_SPL;
for (int e = 0; e < k; e++) if(e!=d) sb[(size_t)(e-(e>d)) * MF_SPL + j] = (u8)((sigfull(row[e])) | ((sigfull(row[e])) == 0));
}
}
if (s_sig) g_sig_merged = 1;
}
}
}
}
if (s_sig && !g_sig_merged && k==10) {
for(int d=0;d<k;d++) {
const u32 *od=s_ord[d];
u8 *base=s_sig+(size_t)d*(k-1)*MF_SPL;
u32 j=0;
for(;j+8<=N;j+=8) {
if(j+64<N){const u32*op=od+j+64;
_mm_prefetch((const char *)(cached_signature+(size_t)op[0]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[1]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[2]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[3]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[4]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[5]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[6]*10),_MM_HINT_T0);
_mm_prefetch((const char *)(cached_signature+(size_t)op[7]*10),_MM_HINT_T0);}
__m128i r0=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+0]*10));
__m128i r1=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+1]*10));
__m128i r2=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+2]*10));
__m128i r3=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+3]*10));
__m128i r4=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+4]*10));
__m128i r5=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+5]*10));
__m128i r6=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+6]*10));
__m128i r7=_mm_loadu_si128((const __m128i *)(cached_signature+(size_t)od[j+7]*10));
__m128i t0=_mm_unpacklo_epi8(r0,r1);
__m128i t1=_mm_unpacklo_epi8(r2,r3);
__m128i t2=_mm_unpacklo_epi8(r4,r5);
__m128i t3=_mm_unpacklo_epi8(r6,r7);
__m128i u0=_mm_unpacklo_epi16(t0,t1);
__m128i u1=_mm_unpackhi_epi16(t0,t1);
__m128i u2=_mm_unpacklo_epi16(t2,t3);
__m128i u3=_mm_unpackhi_epi16(t2,t3);
__m128i v0=_mm_unpacklo_epi32(u0,u2);
__m128i v1=_mm_unpackhi_epi32(u0,u2);
__m128i v2=_mm_unpacklo_epi32(u1,u3);
__m128i v3=_mm_unpackhi_epi32(u1,u3);
__m128i h0=_mm_unpackhi_epi8(r0,r1);
__m128i h1=_mm_unpackhi_epi8(r2,r3);
__m128i h2=_mm_unpackhi_epi8(r4,r5);
__m128i h3=_mm_unpackhi_epi8(r6,r7);
__m128i hu0=_mm_unpacklo_epi16(h0,h1),hu1=_mm_unpacklo_epi16(h2,h3);
__m128i v4=_mm_unpacklo_epi32(hu0,hu1);
if(d!=0)_mm_storel_epi64((__m128i *)(base+(size_t)(0-(0>d))*MF_SPL+j),v0);
if(d!=1)_mm_storel_epi64((__m128i *)(base+(size_t)(1-(1>d))*MF_SPL+j),_mm_srli_si128(v0,8));
if(d!=2)_mm_storel_epi64((__m128i *)(base+(size_t)(2-(2>d))*MF_SPL+j),v1);
if(d!=3)_mm_storel_epi64((__m128i *)(base+(size_t)(3-(3>d))*MF_SPL+j),_mm_srli_si128(v1,8));
if(d!=4)_mm_storel_epi64((__m128i *)(base+(size_t)(4-(4>d))*MF_SPL+j),v2);
if(d!=5)_mm_storel_epi64((__m128i *)(base+(size_t)(5-(5>d))*MF_SPL+j),_mm_srli_si128(v2,8));
if(d!=6)_mm_storel_epi64((__m128i *)(base+(size_t)(6-(6>d))*MF_SPL+j),v3);
if(d!=7)_mm_storel_epi64((__m128i *)(base+(size_t)(7-(7>d))*MF_SPL+j),_mm_srli_si128(v3,8));
if(d!=8)_mm_storel_epi64((__m128i *)(base+(size_t)(8-(8>d))*MF_SPL+j),v4);
if(d!=9)_mm_storel_epi64((__m128i *)(base+(size_t)(9-(9>d))*MF_SPL+j),_mm_srli_si128(v4,8));
}
for(;j<N;j++) {
const u8 *row=cached_signature+(size_t)od[j]*10;
for(int e=0;e<k;e++)if(e!=(int)d)base[(size_t)(e-(e>d))*MF_SPL+j]=row[e];
}
}
g_sig_merged=1;
}
if (s_sig && !g_sig_merged) {
for (int d = 0; d < k; d++) {
const u32 *od = s_ord[d];
u8 *base = s_sig + (size_t)d * (k-1) * MF_SPL;
for (u32 j = 0; j < N; j++) {
#if MF_PFB > 0
if (j + MF_PFB < N) _mm_prefetch((const char *)(s_pm + (size_t)od[j + MF_PFB] * STRIDE), _MM_HINT_T0);
#endif
const u32 *row = s_pm + (size_t)od[j] * STRIDE;
for (int e = 0; e < k; e++) if(e!=d) base[(size_t)(e-(e>d)) * MF_SPL + j] = (u8)((sigfull(row[e])) | ((sigfull(row[e])) == 0));
}
}
}
u64 poolwords = (u64)K1 * (Q + 1) * W;
#if MF_PLEN
if (g_plen_on) {
u64 best = 0;
for (int dsx = 0; dsx < k; dsx++) {
u64 tot = 0;
for (int e = 0; e < K1; e++) {
int d = (e < dsx) ? e : e + 1;
const u32 *mr = s_maxr + ((size_t)dsx * MAXK + d) * MAXQ;
for (u32 b = 0; b <= Q; b++) {
u32 RR = mr[b];
u32 len = ((RR >> 6) + 8u) & ~7u;
if (len > W) len = W;
tot += len;
}
}
if (tot > best) best = tot;
}
if (best && best < poolwords) poolwords = best;
}
#endif
size_t need = (size_t)poolwords * sizeof(u64);
static u64 *pool = 0; static size_t cap2 = 0;
if (need > cap2) { pool = (u64 *)pool_alloc(need + 4096); cap2 = need; }
s_bs = pool;
for (int ds = 0; ds < k; ds++) {
u32 q0 = gstart[ds], q1 = gstart[ds + 1];
if (q0 >= q1) continue;
u32 rlim=0;
{const u32*rm=s_maxr+((size_t)ds*MAXK+(ds?0:1))*MAXQ;
for(u32 b=0;b<=Q;++b)if(rm[b]>rlim)rlim=rm[b];}
#if MF_WTRIM
{
u32 mx = rlim>1?rlim:1;
if(!g_plen_on)for (u32 qi = q0; qi < q1; qi++) { u32 rr = s_gt[ds][s_qord[qi] & 0xFFFFFu]; if (rr > mx) mx = rr; }
u32 wp = ((mx >> 6) + 8u) & ~7u;
Wpool = (wp < W) ? wp : W;
}
#endif
#if MF_PLEN
if (g_plen_on) {
u64 tot = 0;
for (int e = 0; e < K1; e++) {
int d = (e < ds) ? e : e + 1;
const u32 *mr = s_maxr + ((size_t)ds * MAXK + d) * MAXQ;
u32 *po = s_pofs + (size_t)e * MAXQ;
u32 *pl = s_plen + (size_t)e * MAXQ;
for (u32 b = 0; b <= Q; b++) {
u32 RR = mr[b];
u32 len = ((RR >> 6) + 8u) & ~7u;
if (len > Wpool) len = Wpool;
po[b] = (u32)tot; pl[b] = len; tot += len;
}
}
if (tot > (u64)K1 * (Q + 1) * W) { g_plen_on = 0; }
}
#endif
g_mask_ok = 0;
if (g_mask_on) {
{ u32 dd0 = (ds == 0) ? 1u : 0u; g_dm = 0; while ((u32)g_dm == (u32)ds || (u32)g_dm == dd0) g_dm++; }
const u32 dmx = (u32)g_dm;
const u32 *const sdsp = s_pos[ds], *const sdmo = s_pos[dmx], *const sdom = s_ord[dmx], *const sdsr = s_ord[ds];
const u32 *const mrx = s_maxr + ((size_t)ds * MAXK + dmx) * MAXQ;
u32 mblk = 1; { u32 acc = 0;
for (u32 b = 0; b <= Q; b++) {
u32 rr = (mrx[b] >> 7) + 1u; if (rr > Wpool) rr = Wpool; if (rr > mblk) mblk = rr;
u32 rl = (rr + 63u) & ~63u; s_tofs[b] = acc; s_rlen[b] = rl; acc += rl; }
if (mblk > Wpool) mblk = Wpool;
{ size_t tnd = acc;
if (tnd > s_tmcap) { s_tm = (u8 *)pool_alloc(tnd + 4096); s_tmcap = s_tm ? tnd : 0; } } }
{ size_t end = ((size_t)mblk + 1) * 128;
if (end > s_edgcap) { s_edg = (u8 *)pool_alloc(end + 4096); s_edgcap = s_edg ? end : 0; } }
if (s_tm && s_edg) {
g_mask_ok = 1; g_tstride = mblk;
{ u8 *const cnt = s_cntx;
for (u32 m = 0; m < mblk; m++) cnt[m] = 0;
u32 j2 = 0;
for (u32 b = 0; b <= Q; b++) {
u32 L = (b == 0u) ? 0u : ((b < Q) ? FPOS(dmx, b) : (u32)N);
while (j2 < L) {
{ u32 pf = j2 + MF_PFXSW; if (pf >= N) pf = j2; u32 pp = sdom[pf];
_mm_prefetch((const char *)(sdsp + pp), _MM_HINT_T0); Z16S_PFW(&s_npos[pp]); }
u32 p = sdom[j2]; j2++;
u32 rk = sdsp[p]; u32 blk = rk >> 7;
if (blk < mblk) { u32 c = cnt[blk]; cnt[blk] = c + 1u; s_npos[p] = (blk << 7) | c; }
else s_npos[p] = rk;
}
{ u8 *row = s_tm + s_tofs[b]; u32 rl = s_rlen[b];
for(u32 z=0;z<rl;z+=64){
_mm256_stream_si256((__m256i*)(row+z),_mm256_loadu_si256((const __m256i*)(cnt+z)));
_mm256_stream_si256((__m256i*)(row+z+32),_mm256_loadu_si256((const __m256i*)(cnt+z+32)));} }
}
_mm_sfence();
}
{ u32 nb = (N + 127u) >> 7; if (mblk > nb) mblk = nb;
for (u32 m = 0; m < mblk; m++) {
u32 b0 = m << 7, nj = N - b0; if (nj > 128u) nj = 128u;
u8 *const edge=s_edg+(size_t)m*128;
if(nj<128u)__builtin_memset(edge,127,128);
for (u32 j = 0; j < nj; j++) {
  u32 look=b0+j+32;
  if(look<N)_mm_prefetch((const char*)(s_npos+sdsr[look]),_MM_HINT_T0);
  u32 sg = s_npos[sdsr[b0 + j]] & 127u;
  edge[sg]=(u8)j;
} } }
} else g_mask_on = 0;
}
const u32 *s_nid = g_mask_ok ? s_npos : s_pos[ds];
const u32 emsk = (g_mask_ok ? ((u32)g_dm < (u32)ds ? (u32)g_dm : (u32)g_dm - 1u) : 0xffffffffu);
const u32 LIM=((((rlim>>7)<<1)+2u)<<6);
for (int e = 0; e < K1; e++) {
if ((u32)e == emsk) continue;
int d = (e < ds) ? e : e + 1;
const unsigned *xd = x[d];
const u32 *od = s_ord[d];
#if MF_ASCR && !MF_BUILD_NOPOOL


{
const u32 d1b = (ds == 0) ? 1u : 0u;
const u32 e1b = (d1b < ds) ? d1b : d1b - 1u;
if ((u32)e == e1b && !g_lexsort) {
u32 dp = 0, ptr2 = 0;
s_doff[0] = 0;
for (u32 b = 1; b <= Q; b++) {
u32 pend = (b < Q) ? FPOS(d, b) : (u32)N;
u32 pp = ptr2;
const u32 nidpf = 40;
for (; pp + 8 <= pend; pp += 8) {
if (pp + nidpf + 8 <= pend) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
_mm_prefetch((const char *)(s_nid + od[pp + nidpf + 4]), _MM_HINT_T0);
}
if (pp + 72 <= pend) _mm_prefetch((const char *)(od + pp + 64), _MM_HINT_NTA);
u32 q0 = s_nid[od[pp + 0]], q1 = s_nid[od[pp + 1]], q2 = s_nid[od[pp + 2]], q3 = s_nid[od[pp + 3]];
u32 q4 = s_nid[od[pp + 4]], q5 = s_nid[od[pp + 5]], q6 = s_nid[od[pp + 6]], q7 = s_nid[od[pp + 7]];
s_delta[dp]=q0;dp+=(q0<LIM);s_delta[dp]=q1;dp+=(q1<LIM);s_delta[dp]=q2;dp+=(q2<LIM);s_delta[dp]=q3;dp+=(q3<LIM);
s_delta[dp]=q4;dp+=(q4<LIM);s_delta[dp]=q5;dp+=(q5<LIM);s_delta[dp]=q6;dp+=(q6<LIM);s_delta[dp]=q7;dp+=(q7<LIM);
}
for (; pp + nidpf < pend; pp++) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
u32 qq2 = s_nid[od[pp]]; s_delta[dp] = qq2; dp += (qq2 < LIM);
}
for (; pp < pend; pp++) { u32 qq3 = s_nid[od[pp]]; s_delta[dp] = qq3; dp += (qq3 < LIM); }
s_doff[b] = dp;
ptr2 = pend;
}
continue;
}
}
#endif
u64 *base = g_plen_on ? s_bs : (s_bs + (size_t)e * (Q + 1) * Wpool);
u64 *cur = s_acc;
for (u32 w = 0; w < Wpool; w++) cur[w] = 0;
if (g_plen_on) {
u64 *d0 = s_bs + s_pofs[(size_t)e * MAXQ];
u32 l0 = s_plen[(size_t)e * MAXQ];
for (u32 w = 0; w < l0; w++) d0[w] = 0;
}
u32 ptr = 0;
#if MF_BUILD_NOPOOL
while (ptr < N) ptr++;
#else
for (u32 b = 1; b <= Q; b++) {
u32 pend = (b < Q) ? FPOS(d, b) : (u32)N;
#if MF_NIDPF > 0
{ u32 pp = ptr;
const u32 nidpf = 40;
for (; pp + 8 <= pend; pp += 8) {
if (pp + nidpf + 8 <= pend) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
_mm_prefetch((const char *)(s_nid + od[pp + nidpf + 4]), _MM_HINT_T0);
}
u32 q0 = s_nid[od[pp + 0]], q1 = s_nid[od[pp + 1]], q2 = s_nid[od[pp + 2]], q3 = s_nid[od[pp + 3]];
u32 q4 = s_nid[od[pp + 4]], q5 = s_nid[od[pp + 5]], q6 = s_nid[od[pp + 6]], q7 = s_nid[od[pp + 7]];
cur[q0 >> 6] |= 1ull << (q0 & 63); cur[q1 >> 6] |= 1ull << (q1 & 63);
cur[q2 >> 6] |= 1ull << (q2 & 63); cur[q3 >> 6] |= 1ull << (q3 & 63);
cur[q4 >> 6] |= 1ull << (q4 & 63); cur[q5 >> 6] |= 1ull << (q5 & 63);
cur[q6 >> 6] |= 1ull << (q6 & 63); cur[q7 >> 6] |= 1ull << (q7 & 63);
}
for (; pp + nidpf < pend; pp++) {
_mm_prefetch((const char *)(s_nid + od[pp + nidpf]), _MM_HINT_T0);
u32 q = s_nid[od[pp]]; cur[q >> 6] |= 1ull << (q & 63);
}
for (; pp < pend; pp++) { u32 q = s_nid[od[pp]]; cur[q >> 6] |= 1ull << (q & 63); }
}
ptr = pend;
#else
while (ptr < pend) { u32 q = s_nid[od[ptr]]; cur[q >> 6] |= 1ull << (q & 63); ptr++; }
#endif
u64 *dst = g_plen_on ? (base + s_pofs[(size_t)e * MAXQ + b])
: (base + (size_t)b * Wpool);
u32 wlen = g_plen_on ? s_plen[(size_t)e * MAXQ + b] : Wpool;
#if MF_NT
{
u32 w = 0;
for (; w + 4 <= wlen; w += 4)
_mm256_stream_si256((__m256i *)(dst + w), LDA((const __m256i *)(cur + w)));
for (; w < wlen; w++) dst[w] = cur[w];
}
#else
for (u32 w = 0; w < wlen; w++) dst[w] = cur[w];
#endif
}
_mm_sfence();
#endif
}
switch (k) {
case 4: query_group<4>(N, out, ds, q0, q1, Q, Wpool); break;
case 5: query_group<5>(N, out, ds, q0, q1, Q, Wpool); break;
case 6: query_group<6>(N, out, ds, q0, q1, Q, Wpool); break;
case 7: query_group<7>(N, out, ds, q0, q1, Q, Wpool); break;
case 8: query_group<8>(N, out, ds, q0, q1, Q, Wpool); break;
case 9: query_group<9>(N, out, ds, q0, q1, Q, Wpool); break;
default: defer_count=0;
query_group<10>(N, out, ds, q0, q1, Q, Wpool);
break;
}
}
}
void count_10d(int n, const unsigned *x[10], unsigned *out) { solve_mf<10>((u32)n, (const unsigned **)x, out); }

评测结果