代码

/*
References:
- duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/109151:
  Directly reused its accepted guarded fixed-stride x-bucket engine and its
  K7/K8 scalar savings; all prior citations remain below. The public source
  has no separate license notice; this adaptation is submitted only within
  the same contest site, with author and URL attribution.
- Our account saffah_codex_6s_agg2, https://duck.ac/submission/109120:
  Our original fixed-stride x-bucket layout is inherited through #109151.
Approach:
- Use 12288 records per x bucket rather than 20480. The test's approximately
  uniform x distribution needs substantially fewer than 20480 entries in
  each of its 1024 buckets. The inherited overflow check and full-layout
  fallback still handle larger buckets. Each bucket starts one cache set
  later than the preceding bucket, while the address span shrinks.
Purpose:
- Measure whether reducing sparse bucket address span and page/TLB traffic
  clears the live official 1008 threshold; this is an experimental capacity
  sweep with correctness kept by the inherited fallback.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 **#109120** <https://duck.ac/submission/109120>
//     （判题机 197335.413 µs）—— **本件 `[w8s-XF]` 的**思想出处**：把 x 的 MSD 桶从"变长前缀和布局"改成
//     **定长步距布局**（`bucket d` 落在 `d*XBSTEP`），并因此**整趟删掉 x 直方图 + 前缀和**。
//     **本件未逐字节复制该件**：本席按"定长 + 越界守卫 + 旧布局回退"重写（见思路），因为原件的定长布局在
//     **任一桶超过其容量时越界写**（本席用 `w8s_gate.py` 的 shape 5 复现了它：n=1e7 时 x<625001 ⇒ 单桶 25.6 万）
//     —— 那对本文件是**不可接受**的：题面契约允许任意 `[0,n)` 分布，而本件必须对所有合法输入正确。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号）：**#109094** <https://duck.ac/submission/109094>
//     （201164.799 µs = 本件基座：K1+K3+K5+两常量）· **#109067** · **#108945** · **#108903**（祖先链）。
// [3] duck.ac 用户 saffah_codex_6s_agg2，提交 #108843 <https://duck.ac/submission/108843>
//     （205193.608 µs）—— 上述全部我方件的引擎基座（其自带引用链见 #108843 原件）。
// 许可证合规：本题提交代码按 duck.ac 站规公开可读；[1][3] 的公开源**未附独立许可证声明**
//   （其注释自述 "no separate license notice"），各件仅在同一竞赛站内复刻与再创作，不作他用。
// ======================
// ===== 思路 =====
// 本发 = 三把刀（`[w8s-K7]` / `[w8s-K8]` / `[w8s-XF]`）叠在 #109094 上。
//
// 【[w8s-XF] 定长步距 x 桶 + 越界守卫 + 回退】`bnd[d] = d*XBSTEP`（`XBSTEP = XBCAP + 8`，`XBSTEP/8 ≡ 1 (mod 64) 行`）
//   ⇒ ① **整趟 x 直方图 + 前缀和消失**（原件 #109120 的主要收益）；② 1024 条 stage A 散射流**每个占一个 L1 组**
//   （变长布局下行距 ≈ 1220 行 ≡ 4 (mod 64) ⇒ 全部挤进 16 个组）。
//   ★ **正确性守卫（本席新增，原件没有）**：散射结束后逐桶检查 `xend[d] - bnd[d] > XBCAP`（O(MSN) 检查，成本可忽略）；
//   一旦越界 ⇒ **按旧布局重做 stage A**（重算直方图 / 前缀和 / 重散射 / 重建 `gHis16`）⇒ **对所有合法输入都正确**。
//   本席的闸门**专门覆盖了回退路径**：`shape 5`（x<n/16）在 n=1e7 时单桶 25.6 万 ≫ XBCAP=20480 ⇒ 一定走回退，
//   而输出与旧引擎**逐位相同** ✓。`PKB` 尺寸 = `MSN*XBSTEP + NMAX + 64`（越界写的吸收区 + 回退布局所需区间）。
//
// 【[w8s-K7]】`rank_l3_run` 的 staging 打包去掉 `& 0xFFFFFF`（和 < 2^25 ⇒ bit24 落在 8 字节重叠存的 bit48，
//   那是邻居/垫子的字段，且 flush 读回时本来就掩码）✓
// 【[w8s-K8]】stage B 第 3 趟 `cnb2` 游标绝对化 ⇒ 去掉逐元素 `s +`（与 `[w8s-K5]` 同型）✓
//
// 【剂量】（判题机"立即体验"，`work/w8s_ab.sh` + `w8r_head_o2.h`，n=1e7 生产几何，同进程）
//   | 臂 | ticks | Δ |
//   | 基座 #109094 正文 = `work/w8s_k5.cpp`（K1+K3+K5） | 717,104,908 / 717,149,070 | — |
//   | + K7+K8 = `work/w8s_k8.cpp` | 715,032,328 | −0.29% |
//   | 对手 #109120 正文（他那一刀，**无守卫**）| 692,547,228 | −3.15%（probe）↔ **判题机 −1.90%** |
//   | **本件 `work/w8s_xf.cpp`（XF+K7+K8，带守卫）** | **687,682,344** | **−3.83%**（比原件还快：XBSTEP 更紧）|
//   * `h=25293157591` 全臂逐位相同 ✓。
//   ★ **诚实记录**：本族（数据布局）的 probe↔判题机**换算率不守恒**（对手那一刀 probe −3.15% ↔ 判题机 −1.90%），
//     因为 probe 台架的数组是 `malloc` 的、与判题机的静态布局不同 ⇒ **本件的判题机幅度以正式提交为准**。
//
// 【口径与目的】入场 `mine=201164.799`（#109094）· `T=197335.413`（#109120，晚于我方 ⇒ **宽支** `1.005*T`）
//   ⇒ 宽支缺口 2.841709 ms；但**我方任何新最好件都会把口径翻严支** ⇒ 真靶 `0.99*T+1µs = 195.363059`。
//   本发把 lane 从 201.165 推到预期 194~197 ⇒ ①若 ≤195.363 则**当场转绿**；②若落在 (195.363, 196.7]，则变成
//   "对手下一发小幅改进（<0.8%）即自动转绿"的位置（宽支判据 `mine ≤ 1.005*T'`）。
// 【目的（实验性提交声明）】三把刀打包 + **首次在本题引入"带守卫的数据布局改动"**（本席不接受无守卫版本）。
//
// ---- 闸门（正确性）----
//   * `work/w8s_gate.py w8s_k8.cpp w8s_xf.cpp xf --fast`：**15/15 分组 0 失败**（小 n 六形态与 O(n²) 暴力对拍
//     BRUTE-OK；n=1e5、**n=1e7 生产 n** 的 uniform / clustered / reversed 三形态 FNV **逐位相同**）——
//     其中 **n=1e7 shape=5 强制走回退路径** ✓（即"定长越界 ⇒ 旧布局"这条路被实测覆盖）。
//   * 判题机 gcc 9.3（`tools/gcc93check.py`）：**exit=0，无 severity≥3 诊断** ✓。
//   * 提交前机械自检：`md5sum` 与 work/ 下所有 .cpp 均不同；按 `w8s_ab.sh` 剥头规则处理后与
//     **被 probe 的那个文件**（`w8s_xf.cpp`）逐字节相同（"交的就是量的那个"）✓。
// ================
/*
References:
- Our account saffah_codex_6s_agg2, https://duck.ac/submission/107846:
  Reused the accepted 1008 engine and its inherited citations below.
- duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/107504:
  Its ranking engine is inherited through #107846; its public source had no
  separate license notice.
Approach:
- Keep byte cursors for the random six-byte staging scatter, eliminating
  its per-result multiply-by-six. Convert each row end to a record index once
  for the sequential flush, restoring its original induction-variable form.
  All staged bytes and output values are identical to the accepted engine.
Purpose:
- Experimental official timing of stage addressing with a fast flush loop.
*/
/*
References:
- Our account saffah_codex_6s_agg2, https://duck.ac/submission/107846:
  Reused our accepted 1008 engine and all its inherited citations.
- duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/107504:
  Its ranking engine is inherited through #107846; the public source had no
  separate license notice.
Approach:
- Store gBOff as a byte cursor into the six-byte staging rows rather than
  as a record index. Advance it by six per staged result, and walk the flush
  in six-byte increments. This removes a multiply-by-six from each random
  staging scatter while preserving exactly the same bytes and output values.
Purpose:
- Experimental official timing of stage addressing at ten million points.
*/
/*
References:
- duck.ac user saffah_cc_v41_agg1, https://duck.ac/submission/107504: directly reused its accepted 6-byte staging and AVX2 rank engine; inherited attribution remains in the copied source. The public submission contains no separate license notice.
- duck.ac problem statement, https://duck.ac/problem/1008: the 10,000,000-point limit and count_2d interface.
Approach:
- Replace the two 32-bit vector prefix counters for the 64-value middle y digit by two 16-bit counters whenever a top y bucket has at most 65535 points. This halves the counter width, allowing each update to use 128-bit vectors; larger buckets continue through the original 32-bit code.
Purpose:
- Measure whether reducing vector width and counter traffic in the middle y-rank pass clears the live official 1008 target while preserving the accepted fallback.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#107073** <https://duck.ac/submission/107073>
//     （207.759776 ms = 本題当代原最好件）—— **本文件正文的逐字节基座**（工作副本 `problems/1008/work/q8z_mine_107073.cpp`），
//     除本发唯一改动（staging 记录 8 B → 6 B，见思路段）外一字未改。其自述的上游引用（#107041/#107037/#106897 等）
//     在下方原样保留，出处链完整。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 **#106959** <https://duck.ac/submission/106959>（208.158054 ms = 本題实时 T）。
//     用途：**只作门槛计算**（严支 `0.99*T + 1µs = 206.077473`）。**本发未取用它的任何一行代码。**
// [3] 本工作区 `problems/1008/notes.md`（`w8c_` 第六轮列出的"`g_STG` 6 B 压缩"条目、`w8d_` 的复评与 `abl5` 的 flush 定价）
//     与 `BRIEF.md` **§2.19.562**（"先算发出字节/有用字节，再套墙"）。**只引用结论与方法，未复制代码。**
// ======================
// ===== 思路 =====
// 【目的】`g_STG`（out[] 的落盘暂存区，np × 8 B = 80 MB）**记录 8 B → 6 B**。
//   它是本文件里**唯一一个"只用了 48 位却占 64 位"的大数组**：记录 = `cnt`(24 位) + `idx`(24 位)。
//   ★ 本发与 `w8d_` 那次"评估后不做"的区别只有一处，但那一处就是成败：**用一次 8 B 重叠写，而不是两次写。**
//
// 【实现（唯一改动）】
//   · 声明：`alignas(4096) static unsigned char g_STG[6*(size_t)NMAX + …]`，取址宏 `STG6E(k) = g_STG + 6k`。
//   · 三处写点（`rank_l3_run` 主环 + 两个单元素快路）一律改成
//       `*(u64*)STG6E(pos) = (((u64)cnt) << 24) | idx;`
//     —— **一次未对齐 8 B 存**：它比记录多写 2 B，多写的正是**同一条 row 里下一条记录的头 2 字节**，
//     而下一条记录在 row 内**总是后写**（游标 `gBOff[b]++` 单调）⇒ 那 2 B 会被后一条存覆盖 ⇒ **语义无损**。
//     最后一条记录的溢出 2 B 落在 row 之间的 `STGPADE` 填充里 ✓；数组尾部另有 64 B 余量 ⇒ 越界读也不会碰坏东西。
//   · 读点（flush 两个环 + 它的 `prefetchw` 地址）：`u64 r; memcpy(&r, STG6E(t), 8);`
//     ⇒ `idx = r & 0xFFFFFF`、`cnt = (r >> 24) & 0xFFFFFF`（**多算一位掩码**，因为头部 2 B 是邻居的垃圾）✓
//   · `STGPADE 16 → 21`：row 垫子按**记录数**计，21×6 = 126 B ≈ 原来的 16×8 = 128 B（保持 row 步长与 L1 组散布同量级）。
//
// 【为什么"两次写"版本是错的答案、而"重叠写"才对】（本席实测，同一基座、同一探针）
//   | 形态 | ticks | Δ |
//   |---|---|---|
//   | 基座 8 B | 742,363,144 / 742,369,858 | — |
//   | 6 B + **两次写**（u32 + u16） | 749,517,344 | **+0.964% ✗** |
//   | **6 B + 一次重叠 8 B 写** | **738,110,510 / 738,266,008 / 738,211,558** | **−0.573% / −0.559% ✓✓** |
//   | 5 B（idx 只存低 15 位，高 9 位由 row 隐含）+ 重叠写 | 739,539,404 | −0.365% ✗ |
//   | 6 B + `STGPADE 8` / `32` | 739,799,606 / 738,208,574 | +0.400% ✗ / −0.560% ≈ |
//   ⇒ **记录条数才是这里的绑定资源，不是字节数**：两次写把每记录的 store 数翻倍 ⇒ 直接吃掉全部字节收益；
//     而重叠写**保持每记录 1 条 store** ⇒ 省下的是"触摸的 cache line 数"（80 MB/64 B → 60 MB/64 B，−25%）
//     与"写回字节"（−20 MB）+ flush 读（−20 MB）+ **命中页数 −5,000（≈1.9 ms，本題 360 MB 首触，页错是实价）**。
//     ★ 5 B 那一格更小却更慢 ⇒ 与"5 字节步长让 8 B 存跨线率升高"一致（6 B 步长 ≈9% 跨线，5 B ≈12.5%）。
//
// 【闸门】探针本身就是**生产 n = 10,000,000** 的整程跑，且它打印输出哈希 ⇒
//   本发 `h = 25293157591` **与基座逐位相同**（四次独立运行都是这个值）✓ ⇒ 强闸门 = "生产 n 输出逐位相同" ✓
//   （探针 head 的 `#pragma`/driver 只影响计时口径，不影响引擎正文；本発正文与上面四行读数用的是同一份文件。）
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#107041**
//     <https://duck.ac/submission/107041>（208.130655 ms = 我方当值最好件）
//     —— **本文件正文的逐字节基座**（工作副本 `problems/1008/work/y8f_base3.cpp`）。
//     它是本账号另一席 `w8q_` 的件（flush 环预取守卫剥离），**本发只在其之上加 2 行**。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#107037**
//     <https://duck.ac/submission/107037>（208.278708 ms）—— [1] 的前一代（`w8q_` 的 stage A 守卫剥离）。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#106897**
//     <https://duck.ac/submission/106897>（210.542116 ms）—— 血统链更早一代。
// [4] duck.ac 用户 saffah_codex_6s_agg2，提交 **#106959**
//     <https://duck.ac/submission/106959>（208.158054 ms = 本题实时 T / 榜首）。
//     用途：**只作门槛计算**（`0.99*T + 1µs = 206.077473`）。**本发未取用它的任何一行代码。**
// [5] 本工作区 `BRIEF.md` **§2.19.498**（本席入库：`__builtin_prefetch(p,1,·)` 与内联 `prefetchw` **不是同一把刀**）
//     · **§2.18.357**（已按本条更正）· **§2.19.405**（locality 轴）· **§2.19.340**（预取判据）
//     · **§2.19.416**（提示通道改动必须看反汇编）· **§2.19.444**（构建完整性三查）· **§2.19.489**（组合件必须声明）。
//     只用于机理判断，未复制任何代码。
// ======================
// ===== 思路 =====
// 【★ 本发是组合件，按 `§2.19.489` 声明实际内容】
//   本发 = **① `w8q_` 的 stage A 预取守卫剥离（`#107037`）+ ② `w8q_` 的 flush 环预取守卫剥离（`#107041`）
//   + ③ 本席的 2 行 `prefetchw`**。
//   **本席本发只贡献 ③**；①② 是基座自带，列出只为口径完整。
// 【两个分件在当前基座上的靶是否都还在（`§2.19.489` 要求）——实核证据】
//   * **① 的靶**：`y8f_base3.cpp` 第 432 行 `for (; i + 64u < np; i++) {` + 尾环 `for (; i < np; i++) {`，
//     且其 stage A 预取**已无 per-element `if`** ⇒ **① 在位** ✓
//   * **② 的靶**：同文件第 598 行 `for (; t + 64u < e; t++) {`，其预取**已无 per-element `if`** ⇒ **② 在位** ✓
//   * `grep -n '__builtin_prefetch' y8f_base3.cpp` ⇒ 代码里**恰好 2 处**（433 / 599）⇒ **③ 的两个靶都在** ✓
//   * **打完后复核**：`y8f_pfwAB_b3.cpp` 里 `__asm__ __volatile__("prefetchw` 计数 = **2**、
//     代码里残留 `__builtin_prefetch` = **0**、两条 `for (; … < …; …++)` 剥离环**原样在位**
//     ⇒ **三件并存、互不覆盖** ✓
// 【口径（`§2.19.410/443`：先判支）】`tools/exact.py 1008`：
//   `mine = 208.130655 (#107041)` · `T = 208.158054 (#106959)` · 严支真靶 `0.99*T + 1µs = 206.077473`
//   ⇒ 还需 **2.053182 ms（0.986%）**。**本发按真靶评估。**
//   ★ 现在走**严支**（`#107041` 的提交号 107041 **大于** T 的 106959 ⇒ T 早于我方最好件 ⇒ 口径=严）✓
//   ★ **被动窗口是开着的**：对手任何"新最好件" `T''`（必然晚于我方最好件 ⇒ 口径翻**宽**）
//     只要落在 `T'' ≥ mine/1.005 = 207.0952` 且 `T'' < 208.158054`（= 必须比现 T 更快）
//     ⇒ 我方**自动转绿**。窗口带宽 **1.063 ms（0.51%）** ✓ ⇒ 本发不是唯一出路，但是**主动**的那条。
//     （注：若 `T''` 落在 207.0952 以下，则口径虽翻宽、我方仍红 ⇒ 对手越强我们越远 ⇒ 仍需自己压。）
// 【本席本发唯一改动（③）】两处 `__builtin_prefetch(..., 1, 3)` → `__asm__ __volatile__("prefetchw %0" :: "m"(...))`
//   * **机理**：`__builtin_prefetch(p, 1, 3)` 的 **rw=1 写意图位被 gcc 丢弃** —— 判题机同款 gcc 9.3 实编
//     **10 条 `prefetcht0`、0 条 `prefetchw`**（`tools/gcc93check.py --show prefetch` 实核）⇒ 行以 **S 态**到达
//     ⇒ 被覆盖的散写 store **仍要付一次 RFO 升级**（一次完整内存往返 = 预取本该隐藏的延迟）。
//     真 `prefetchw` ⇒ 行以 **E/M 态**到达 ⇒ **升级消失** ✓（`§2.19.498`）
//   * **判题机已确认该机理**：本席上一发 `#107038 = 209.983217 ms` vs 当时代基座 `#106897 = 210.542116`
//     ⇒ **−0.2655% ✓**。本发是把它**重铺到两席合并后的更好基座**上（正交叠加，**不是重复试验**）。
//   * **判题机 gcc 9.3 实核**：`10 × prefetcht0` → `10 × prefetchw`，**地址与条数一一对应** ✓；
//     `.text` 尺寸与基座**完全相同（557181 B）** ✓；`objdump -d` 与本席已闸门的件**逐行相同** ✓
//   * **构建完整性三查（`§2.19.444`）**：① `.text` 量级相同 ✓ ② `#pragma GCC optimize/target` 与
//     `#define MSH/MSN/XSH/NBKT/BSH/STGPADE` **全部原样在位** ✓ ③ 纯前置注释头，正文与已闸门件逐字节相同 ✓
//   * **纯提示、零语义**（prefetch 不产生架构状态）⇒ 闸门 **14 组逐位相同**：小 n（3000/20000，6 种数据形态）
//     与**暴力对照 BRUTE-OK**；大 n（1e6、**生产 1e7**）FNV **逐位相同** ✓
// 【与已关闭读数的区别（三者都没测过本发这一维）】
//   * `§2.18.357` 的 "+3.6% / +5.0%" 其臂**实编 `prefetcht0`** ⇒ **不是 prefetchw 的读数**（`§2.19.498` 已更正）；
//   * 本 lane 的 locality 三档（T0/NTA/T1/T2）测的是**缓存层级**，不是**一致性状态**；
//   * "盲扫预取 +1.98%" 与 "`pk[]` +5.31%" 是**新增请求**（撞在飞容量，`§2.19.340`）⇒ 本发**不增加任何请求** ✓
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#107037**
//     <https://duck.ac/submission/107037>（208.278708 ms = 我方当值最好件）
//     —— **本件正文的逐字节基座**，除本发唯一改动外一字未改。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 **#106959** <https://duck.ac/submission/106959>
//     （208.158054 ms = 本题实时 T）—— 它的**唯一改动** = stage A 预取守卫剥离；我方已在 **#107037** 收回
//     （210.542116 → 208.278708 = **−2.263 ms / −1.075%**，与他 208.158054 只差 0.121 ms = **0.058%**，
//     落在同族"同源码两发残差 0.028~0.06%"的散布内 ✓）。**本发不取它的任何一行。**
// [3] duck.ac 题目页 <https://duck.ac/problem/1008>（n=1e7，二维数点，接口 `count_2d`）。
//     口径（本席自核 `tools/exact.py 1008`）：mine=208.278708 · T=208.158054 ·
//     **严支真靶 = 0.99*T + 1µs = 206.077473 ms ⇒ 本发前还差 2.201235 ms（1.057%）** ✓
// [4] /home/yjp/duck.ac/BRIEF.md **`§2.19.425`**（覆盖度表要按站点分类读：**同型站点是否全部覆盖**）+
//     `§2.19.455`/`§2.19.471`（守卫频率必须 = 64 B line 的消费频率；轮次 = 1 是最优下界）
//     + `§2.19.416`/`§2.19.422`（守卫进体/出体；本题由判题机实测"剥出去"为正 —— 见 [2]/#107037 的读数）✓
// 许可证：以上均为 duck.ac 公开提交，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// 【本发只有一个变量：flush 环的预取守卫剥离 —— `§2.19.425` 的"覆盖度表"第二行】
//   ① 站点分类（同型/弱型）：`#107037` 收回的那一手打在 **stage A**；
//      本发打 **flush 环**（`// ---- flush: walk the staging array one idx-bucket at a time …`），
//      它与 stage A **逐字同型**：`for (t…) { if (t + 64u < e) __builtin_prefetch(&out[…]); <store> }`
//      —— **同一刀型的第二个站点，且对手 #106959 没有剥它** ✓（`§2.19.425` 第①问：同型站点是否**全部**覆盖）
//   ② 改动：`u32 t = e - 6u * gBkt[b]; for (; t + 64u < e; t++) { <预取无条件> <store> } for (; t < e; t++) { <store> }`
//   ③ **语义逐位不变（可证）**：被剥出去的是**每个桶的最后 64 条记录**，在原形守卫 `t + 64u < e` 下
//      **恒假** ⇒ 它们本来就不发预取 ⇒ 尾环不发预取与原形一致；**每条 store 的地址与值都不变** ✓
//      （flush 是**逐桶就地写 `out[g_STG[t] & 0xFFFFFF]`** 的散写：前瞻 64 条 = 把该桶内未来 64 条的
//        out 行提前拉进缓存 ⇒ 前 64 条之外的记录各有一次被覆盖的散写；剥离后主环少一次**可预测分支** ✓）
//   ④ 期望：stage A 的同型剥离判题机 −1.075%（我方 #107037）⇒ 本发若同量级（flush 处理的是**同样 1e7 条**记录）
//      则 **−2.2 ms 上下，恰好在真靶附近** ⇒ 单发可能直接越线；若只拿一半，则差 ~1 ms（继续下一手）✓
//
// 【闸门（`work/y8e_mk.sh`，n=1e7，判题同款 flags）】输出哈希：基座/`#107037`/本件 **h=25293157591** 三者逐位相同 ✓
//   （本机 ticks 只作符号：该台架剥掉 `#pragma GCC target` 块 ⇒ codegen 类幅度不可信，见 `y08a_` 七）
// ======================
// ===== REFERENCES (本发新增，以下为原基座的引用链) =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#106763**
//     <https://duck.ac/submission/106763>（212.866283 ms = 我方当值最好件）
//     —— **本文件正文的逐字节基座**（工作副本 `problems/1008/work/y8e_base.cpp`），除本发唯一改动外一字未改。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 **#106724**
//     <https://duck.ac/submission/106724>（212.837532 ms = 本题实时 T / 榜首）。
//     用途：**只作门槛计算**（严支 `0.99*T + 1µs = 210.710157`）。**本发未取用它的任何一行。**
// [3] 本工作区 `BRIEF.md` **§2.19.404**（"已存在的预取族"是盲区：要逐数组、逐**目标**问
//     "这一趟还要读哪几个数组 / 哪些目标被覆盖到了"）、**§2.19.405**（locality 轴；本席本轮的 3 发
//     判题机读数已把它在**写预取**上关闭：T0 最优，NTA/T1/T2 全负）、**§2.19.340**（预取判据；
//     本 lane 的"盲扫预取 +1.98%"是**新增**请求撞饱和度）。**只用于机理判断，未复制任何代码。**
// ======================
// ===== 本发思路（`y8e_`，2026-09-28 19:0x）=====
// 【目的】单变量试验：**把两条既有写预取从"隔一个取一个"改成"每个都取"**（覆盖度，不是 locality）。
// 【现状】`mine = 212.866283 (#106763)` · `T = 212.837532 (#106724)` ·
//   严支线 `0.99*T + 1µs = 210.710157` ⇒ 还需 **−2.156126 ms（1.013%）**。
// 【普查发现（`§2.19.404` 的"覆盖度"形式）】本文件的两条写预取**各自只覆盖一半的散写 store**：
//   * L370（stage A）：`if ((i & 1u) == 0u && i + 64u < np) __builtin_prefetch(PKB + cntb[future_dg], 1, 3);`
//   * L529（flush） ：`if ((t & 1u) == 0u && t + 64u < e)  __builtin_prefetch(&out[g_STG[t+64] & 0xFFFFFF], 1, 3);`
//   ★ **奇偶条件 `(i & 1u) == 0u` 与前瞻距离 `64` 的奇偶性相同** ⇒ "偶数 `i` 的预取命中的是**偶数** `i+64`"
//     ⇒ **奇数下标的散写 store 从来没有任何预取覆盖它们** ⇒ 这两条冷散写流各有 **50% 的 store 是裸的**。
// 【本发唯一改动】把两处的 `(x & 1u) == 0u &&` 条件删掉（前瞻距离 64 不变）⇒ **覆盖度 50% → 100%**。
//   **纯提示、零语义**。代价 = 每元素多一条预取 uop（~5e6 条/趟）。
//   ★ 与 `§2.19.340` 的"盲扫预取 +1.98% ✗"**不同**：那条是**新增一整族预取**（在飞请求翻倍）；
//     本发只是把**已有的那一族**补满覆盖度 —— 若该相位真已 LFB 饱和，本发应当同样判负，
//     那将是"该相位在飞已满"的**第四次**独立确认；若为正，说明之前是"覆盖度不足"而不是"饱和" ✓。
// 【闸门】本机 probe 台架（`y8e_mk.sh`，n=1e7）：`h=25293157591` **与基座逐位相同** ✓；
//   本机交错 A/B（3 轮）：base min 1070.97 M ticks vs 本件 1082.63 M ticks ⇒ **本机 ≈ 平/略负**
//   （本机对本题"既噪声大又错配" ⇒ 只作"是否显然错误"的筛子，符号以判题机为准）✓。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 #106724 <https://duck.ac/submission/106724>
//     （判题机 212837.532 µs = 本题当代 T）—— **本文件正文 = 该提交正文逐字节复制**（`§2.16` 第一步"纯复刻"），
//     其自带的两段 References/Approach（含 [1]#106717、[2] 本账号 #105198）原样保留在下方。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 #106717 <https://duck.ac/submission/106717>
//     （= [1] 的父本）—— 经本席**剥注释 diff** 核对：它相对 [2] 引用的本账号 #105198 只有**两处**代码差异
//     （① 把 `_mm256_set1_epi32(ya0)` 提到 `a<8` 分支外共享给两条路径；② `popcount(mm & gDupMsk[a])`
//     → `popcount(_bzhi_u32(mm,a))`，并删掉 gDupMsk 表；③ 另加 `bmi2` 到 `#pragma GCC target`），再叠 [1] 的
//     "把 a≥8 的冷回退移进 noinline"。三处**都不改算术**（判题机 Accepted ⇒ 逐位等价 ✓）。
// [3] 本账号 saffah_cc_v41_agg1，提交 #105198 <https://duck.ac/submission/105198>
//     —— 本 lane 的达标题（`work/w8b_sub1.cpp`，215.084600 ms）；[1] 自述其继承自此件。
// ======================
// ===== 思路 =====
// 本发 = **取证复刻（replication）**，不是新实验：把对手当代件 #106724 的正文取回，作为本 lane 的新基座。
// 依据（§2.18.349）：对手的文件**逐行包含我方 #105198 的引擎**，其增量已被判题机定价 ⇒ 抄它是**已定价**的一步；
// 本席另做了**剥注释 diff**（判据：只数结构性 hunk）确认"我方件 → 对手件"的全部差异就是上述三处（外加 noinline），
// 且**没有任何算术改动**（因此本次不另立新变量）。
// ★ 与协调者口径的关系：我方最好件 #105198 **早于** #106724 ⇒ 当前走**宽支**（thr 213.902720，还需 1.181880 ms）；
//   但**本发一旦成为我方新最好件，口径立刻翻严支**（thr = 210.710157）⇒ **本发只取回已定价的那 1.045%**，
//   离严支线仍差 ~2.13 ms ⇒ **预计发完仍是红**（不指望一发翻绿，只为把基座抬到对手当代件上）。
// 正确性：对手件判题机 **Accepted** ✓；三处差异均不改算术（共享广播 / 等价掩码 / noinline）✓。
// ================
// References:
// [1] Our account saffah_codex_6s_agg2, submission #106717:
//     https://duck.ac/submission/106717
//     Direct copy of our accepted BMI2 mask and shared y-broadcast variant;
//     its inherited credits remain below.
// [2] duck.ac user saffah_cc_v41_agg1, submission #105198:
//     https://duck.ac/submission/105198
//     Inherited ranking engine and AVX2 eight-lane y history. No separate
//     license notice appears in the public source.
// Approach:
// Move the rare equal-x group fallback for a>=8 into a cold noinline
// helper. This preserves its exact scalar scan but keeps its loop and setup
// out of the ten-million-element fast loop's instruction footprint.
// Purpose:
// Measure official front-end savings while verifying all fallback cases.
// References:
// [1] Our account saffah_codex_6s_agg2, submission #106715:
//     https://duck.ac/submission/106715
//     Direct copy of our accepted BMI2 recent-y mask variant and inherited
//     credits below.
// [2] duck.ac user saffah_cc_v41_agg1, submission #105198:
//     https://duck.ac/submission/105198
//     Inherited 1008 ranking engine and AVX2 recent-y history. No separate
//     license notice appears in the public source.
// Approach:
// Broadcast the current y value once and share that vector between the
// recent-y comparison and the history insertion. This removes a possible
// duplicate broadcast in the L1 hot loop without changing its arithmetic.
// Purpose:
// Measure the official instruction-scheduling effect and verify all cases.
// References:
// [1] duck.ac user saffah_cc_v41_agg1, submission #105198:
//     https://duck.ac/submission/105198
//     Direct copy of its accepted 1008 ranking engine and AVX2 recent-y
//     history. Its detailed inherited citations remain below. No separate
//     license notice appears in this public source.
// [2] Inherited through [1]: our account saffah_codex_6s_agg2,
//     https://duck.ac/submission/104516
//     L3 segmented counter design.
// Approach:
// Use BMI2 BZHI to keep the low a bits of the eight-lane comparison mask
// instead of loading a small lookup table and applying an AND. For a<8,
// both operations produce exactly (mask & ((1<<a)-1)); the a>=8 fallback
// remains unchanged. Remove the now-unused mask table initialization.
// Purpose:
// Measure whether one register-only mask instruction reduces L1 hot-loop
// load pressure and total official time.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6s_agg2，提交 **#104516**
//     <https://duck.ac/submission/104516>（227.793436 ms，本题当时榜首）。
//     用途：**直接复制**其 L3 段计数结构 —— `rank16_*` / `rank8_*` / `rank8_upgrade` /
//     `rank_l3_run<>` 一族函数、`gR16H/gR16L/gR16MaskH/gR16MaskL` 与 `gR8L/gR8MaskL`
//     两张**预算好的掩码行**表（`mask[a][i] = (i > a)`）、以及 L2+L3 融合段里的三分支 dispatch。
//     本文件里该块与他**逐字相同**（未改动）。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#104739**
//     <https://duck.ac/submission/104739>（227.993923 ms）—— 本文件正文的基底，以及
//     `MSH/BSH/STGPADE/桶内 LSD 数位` 四个常量的取值出处。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#103946**
//     <https://duck.ac/submission/103946>（230.793356 ms）—— 引擎内 `optimize` 指示、
//     staging 行垫子、stage A 散射目标预取、`g_STG` 的 `alignas(4096)`、flush 段 `out[]`
//     写目标预取、y 的 9/6/9 数位分割。
// [4] duck.ac 用户 saffah_codex_6s_agg2，提交 **#103614**
//     <https://duck.ac/submission/103614>（233.286522 ms）—— `MSH 10` + 桶内 LSD `7+7`
//     的组合、以及 stage A 散射目标预取（`pfXs`）的实现。
// [5] /home/yjp/duck.ac/BRIEF.md
//     **§2.18.825**（`cyc/元素 ≈ max(loads/2, stores/1, uops/4)`：先算哪一项是 max，只动那一项）·
//     **§2.18.850②**（指令条数 → 墙钟兑现率 ≈ 90%；本族可直接读判题机 gcc 9.3 的循环体条数排产）·
//     **§2.18.845**（"减 uop 无效" ≠ "调度无效"：发射序是活的）·
//     **§2.18.827**（热环里很少执行的内层分支会挤占 µop cache，解法是把它移出热环）·
//     **§2.18.716**（"故意算错"的定价臂）· **§2.18.539**（数据契约审计）·
//     **§2.18.530②**（生成器锚点必须断言命中数）。以上均为**方法论**引用，未复制任何其它代码。
// ======================
// ===== 思路 =====
// 相对我方最好件 **#104841**（222.303664 ms）**只改一处：L1 段 `dup` 的算法**（单变量），
// 语义逐位不变、输出逐位不变。动手顺序按"先给循环定价、再动刀"（§2.18.825 + §2.18.850②）：
//
// (1) **判题机 probe 相位图**（`work/w8r_prof.py`，`w8r_head_o2.h` = 判题机的 `-O2` 口径，
//      n=1e7 冷跑，合计 799.4 M ticks）：
//     stage A 145.7 M (18.2%) | stage B 119.9 M (15.0%) | **L1 248.7 M (31.1%)** |
//     **融合 L2+L3 222.9 M (27.9%)** | flush 62.2 M (7.8%)。
// (2) **判题端 gcc 9.3 汇编**（`tools/gcc93check.py`）逐环核对：L1 内层循环体 **72 条/元素**，
//     其中 `dup` 的标量链（2 深 y 历史 + `seta/setne/and/lea`）占 **13 条**；且 `a>=3` 的
//     重扫分支**内联在热环里**（带 `and ebx,3 / cmp / je` 的模 4 分发前导 + 一个被向量化的
//     重扫循环）—— 正是 §2.18.827 的"很少执行的内层分支挤占 µop cache"形态。
// (3) **端口账**（§2.18.825 的 max 形式）：loads 10/2 = 5 · stores 5/1 = 5 · **uops 72/4 = 18**
//     ⇒ max = **uops/4**，即该环**前端受限** ⇒ **只有"减 uop"付钱**：减 8 条 ≈ −11% 环时 ≈ −3.4% 全时。
//     本轮实测 −3.30%，与"1:1 兑现"吻合（与 abl8 的历史读数同族）。
//
// **做法**：`dup` 的语义是"本组内序号 < a 的元素里 y < ya0 的个数"。把它从"2 深标量历史 +
// a>=3 重扫"换成 **8 lane 的 ymm y-历史 + 一张掩码表**：
//   * `yhist` 的第 j 条 lane = 本 x 组**第 j 个最近**元素的 y：每元素 `vpermd`（常量索引轮转）
//     + `vpblendd`（把 `ya0` 插进 lane 0），循环携带依赖只有 2 拍；
//   * `dup = popcount( movemask( vpcmpgtd(broadcast(ya0), yhist) ) & gDupMsk[a] )`，
//     其中 `gDupMsk[a] = (1<<a)-1`，恰好只保留"本组内合法的 a 条 lane"（a 是新组内的序号，
//     换组时 a 归 0 ⇒ 掩码为 0 ⇒ 无需任何复位）。
//   * 于是**快路径的适用上界从 a<3 抬到 a<8**：随机数据下 x 的组大小 ≈ 零截断 Poisson(1)，
//     P(a>=8) ≈ 4e-6 ⇒ `a>=8` 的**重扫分支（含那条模 4 分发前导）在判题数据上基本不执行**；
//     但它仍在，**最坏复杂度与 #104841 的 a>=3 重扫完全相同**，故对任何合法输入都不劣化。
//   * 逐条代价：`vpcmpgtd + vmovmskps + and(带 load) + popcnt` = 4 条，历史维护 `vpermd + vpblendd`
//     = 2 条，合计 **6 条**，替掉 **13 条**标量链与 2 条 `y2=y1;y1=ya0` 的 mov；并且新形状下
//     gcc 把 `movabs 0x7FFFFFFFFF` **提到了循环外**（旧形状里它每元素重发一次）。
//   * `#pragma GCC target("avx2,popcnt,bmi2")`：判题机 CPUID 已实测 `avx2=1`，而 AVX2 机器必带
//     POPCNT（本工作区此前已在判题机跑过带 `popcnt` 的 target 扩项，编译与运行均正常）。
//
// ---- 闸门（正确性）----
//   * **判题机同规模逐位对拍**（`work/w8d2_cmp.cpp`，`NMAX=10000002`，n=1e7 = 判题机的 n，
//     坐标构造性落在 [0,n)）：本件 vs `#104841` 在 **n=1e5 / n=1e6 各 9 种分布** +
//     **n=1e7 的 8 种分布**（mode 1 / mode 8 在 n=1e7 上是 O(n²)，按前几轮惯例除外）
//     ⇒ **全部逐位相同**。其中 mode 3/4/5/7 是**强并列 / 多桶并列**形态，会真正走进 `a>=8`
//     的重扫路径 ⇒ 新增分支的**两侧都被覆盖**。
//   * n=1e7 判题机 probe 的 `h=25293157591` 与 #104841 **逐位相同**。
//   * `gcc93check.py`（判题机 gcc 9.3）：**exit=0**；全文无 `div/idiv`、无栈上 YMM 溢出。
//   * 已知风险（照实记录，§2.18.539）：本件**未**调用对手留下的 `rank8_fits()`（与 #104841 一致，
//     本次未改动该处）。
//
// ---- 定价（判题机"立即体验"，`work/w8r_ab.sh` + `w8r_head_o2.h`，n=1e7，交替轮转）----
//   | 臂 | ticks |
//   | `#104841`（本件基座） | 795,116,128 / 794,900,422（两轮，互差 0.03%）|
//   | **本件** | **768,847,402 ⇒ −3.30%**（`h=` 逐位相同）|
// ================
#include <cstdint>
#include <cstring>
#include <cstdlib>
#include <immintrin.h>

#pragma GCC push_options
#pragma GCC optimize("O3,unroll-loops,rename-registers")
#pragma GCC target("avx2,popcnt,bmi2")

typedef uint64_t u64;
typedef uint32_t u32;

#define MSH 10
#define MSN (1 << MSH)
#define XSH (24 - MSH)
static const int NMAX = 10000002;

alignas(64) static u32 XA[NMAX], XB[NMAX];
/* [w8s-XF] fixed-stride x buckets: bucket d lives at d*XBSTEP records, i.e.
   XBSTEP/8 == 1 (mod 64) cache lines apart, so the 1024 concurrent stage-A
   scatter streams occupy distinct L1 sets instead of clumping into 16.
   A bucket that would not fit triggers the legacy re-scatter below. */
#define XBCAP 12288u
#define XBSTEP (XBCAP + 8u)
alignas(64) static u64 PKA[NMAX], PKB[(size_t)MSN * XBSTEP + (size_t)NMAX + 64];
alignas(64) static u32 DUPA[NMAX];
static u32 cntb[MSN], xend[MSN];
static u32 cnb2[128];
static u32 gH512[512];
#define NBKT 512
#define BSH 15
#define STGPADE 32   /* [q8z-STG6] staging-row pad in RECORDS: 21*6 = 126 B ~= the old 16*8 = 128 B */
alignas(4096) static unsigned char g_STG[6 * (size_t)NMAX + 16 * NBKT * 8 + 64];   /* [q8z-STG6] 6 B/record: b0..2 = idx, b3..5 = cnt */
#define STG6E(k) ((unsigned char *)g_STG + (size_t)(k))
static u32 gBkt[NBKT + 1];
static u32 gBOff[NBKT + 1];

alignas(32) static u32 gP1[8];
alignas(32) static u32 gP2[8][8];
alignas(32) static u32 gP3[8][8][8];
alignas(16) static uint16_t gR64H[8], gR64L[8][8], gR64Mask[8][8];
static bool gR64MasksReady = false;
static inline void r64_init() {
  if (!gR64MasksReady) {
    for (int d=0; d<8; d++) for (int j=0; j<8; j++)
      gR64Mask[d][j] = (uint16_t)(j>d);
    gR64MasksReady = true;
  }
  memset(gR64H, 0, sizeof(gR64H));
  memset(gR64L, 0, sizeof(gR64L));
}
static inline u32 r64_q(u32 d) {
  return (u32)gR64H[d>>3] + gR64L[d>>3][d&7];
}
static inline void r64_ins(u32 d) {
  u32 hi=d>>3, lo=d&7;
  __m128i h=_mm_load_si128((const __m128i*)gR64H);
  __m128i hm=_mm_load_si128((const __m128i*)gR64Mask[hi]);
  _mm_store_si128((__m128i*)gR64H, _mm_add_epi16(h,hm));
  __m128i *row=(__m128i*)gR64L[hi];
  __m128i l=_mm_load_si128(row);
  __m128i lm=_mm_load_si128((const __m128i*)gR64Mask[lo]);
  _mm_store_si128(row, _mm_add_epi16(l,lm));
}

alignas(32) static u32 gMsk[8][8];
alignas(32) static u32 gInc[8][8];
static u32 gCur[512];
/* gDupMsk[a] = (1<<a)-1: keeps the low a lanes of the ymm y-history,
   i.e. the a most recent elements of the current equal-x group. */

static u32 gBnd[514];
static u32 gHis[513];
/* Joint (d1,d2) histogram, filled for free in stage A.  gHis16 is 512*64 unsigned short = 64 KB;
   it only wraps if some (d1,d2) cell holds more than 65535 elements, which the
   after-the-fact total detects exactly, and only then is the u32 twin rebuilt from
   the caller's y[].  In the normal case this replaces the standalone L2 histogram
   sweep over every bucket. */
alignas(64) static uint16_t gHis16[512][64];
static u32 gHis32[512][64];

static inline void cnt_init(void) {
  memset(gP1, 0, sizeof(gP1));
  memset(gP2, 0, sizeof(gP2));
  memset(gP3, 0, sizeof(gP3));
}
static inline u32 cnt_q(u32 d) {
  return gP1[d >> 6] + gP2[d >> 6][(d >> 3) & 7] + gP3[d >> 6][(d >> 3) & 7][d & 7];
}
static inline void cnt_ins(u32 d) {
  u32 a = d >> 6, b = (d >> 3) & 7, c = d & 7;
  __m256i i3 = _mm256_load_si256((const __m256i *)gInc[c]);
  __m256i v3 = _mm256_load_si256((const __m256i *)&gP3[a][b][0]);
  _mm256_store_si256((__m256i *)&gP3[a][b][0], _mm256_add_epi32(v3, i3));
  __m256i i2 = _mm256_load_si256((const __m256i *)gInc[b]);
  __m256i v2 = _mm256_load_si256((const __m256i *)&gP2[a][0]);
  _mm256_store_si256((__m256i *)&gP2[a][0], _mm256_add_epi32(v2, i2));
  __m256i i1 = _mm256_load_si256((const __m256i *)gInc[a]);
  __m256i v1 = _mm256_load_si256((const __m256i *)&gP1[0]);
  _mm256_store_si256((__m256i *)&gP1[0], _mm256_add_epi32(v1, i1));
}

/* 2-level counter for the 6-bit L3 digit: the third level and the top level of the
   3-level structure are dead weight here (the top 3 bits of the digit are always 0),
   so cnt_q/cnt_ins drop one 32 B load + one 32 B RMW each, and the per-run state that
   has to be cleared shrinks from 2.3 KB to 352 B. */
static inline u32 cnt_q2(u32 d) {
  return gP2[0][(d >> 3) & 7] + gP3[0][(d >> 3) & 7][d & 7];
}
static inline void cnt_ins2(u32 d) {
  u32 b = (d >> 3) & 7, c = d & 7;
  __m256i i3 = _mm256_load_si256((const __m256i *)gInc[c]);
  __m256i v3 = _mm256_load_si256((const __m256i *)&gP3[0][b][0]);
  _mm256_store_si256((__m256i *)&gP3[0][b][0], _mm256_add_epi32(v3, i3));
  __m256i i2 = _mm256_load_si256((const __m256i *)gInc[b]);
  __m256i v2 = _mm256_load_si256((const __m256i *)&gP2[0][0]);
  _mm256_store_si256((__m256i *)&gP2[0][0], _mm256_add_epi32(v2, i2));
}
static inline void cnt_init2(void) { memset(gP2[0], 0, sizeof(gP2[0])); memset(gP3[0], 0, sizeof(gP3[0])); }


alignas(32) static uint16_t gR16H[16], gR16L[16][32];
alignas(32) static uint16_t gR16MaskH[16][16], gR16MaskL[32][32];
static int gR16MasksReady = 0;

static inline void rank16_init() {
  if (!gR16MasksReady) {
    for (int a=0;a<16;a++) for (int i=0;i<16;i++) gR16MaskH[a][i]=(uint16_t)(i>a);
    for (int a=0;a<32;a++) for (int i=0;i<32;i++) gR16MaskL[a][i]=(uint16_t)(i>a);
    gR16MasksReady=1;
  }
  memset(gR16H,0,sizeof(gR16H));
  memset(gR16L,0,sizeof(gR16L));
}
static inline u32 rank16_q(u32 d) {
  return (u32)gR16H[d>>5] + gR16L[d>>5][d&31];
}
static inline void rank16_ins(u32 d) {
  u32 hi=d>>5,lo=d&31;
  __m256i h=_mm256_load_si256((const __m256i*)gR16H);
  __m256i hm=_mm256_load_si256((const __m256i*)gR16MaskH[hi]);
  _mm256_store_si256((__m256i*)gR16H,_mm256_add_epi16(h,hm));
  __m256i *row=(__m256i*)gR16L[hi];
  const __m256i *mask=(const __m256i*)gR16MaskL[lo];
  __m256i a=_mm256_load_si256(row), b=_mm256_load_si256(row+1);
  _mm256_store_si256(row,_mm256_add_epi16(a,_mm256_load_si256(mask)));
  _mm256_store_si256(row+1,_mm256_add_epi16(b,_mm256_load_si256(mask+1)));
}

alignas(32) static uint8_t gR8L[16][32], gR8MaskL[32][32];
static int gR8MaskReady=0;
static inline void rank8_init() {
  if (!gR16MasksReady) {
    for (int a=0;a<16;a++) for (int i=0;i<16;i++) gR16MaskH[a][i]=(uint16_t)(i>a);
    for (int a=0;a<32;a++) for (int i=0;i<32;i++) gR16MaskL[a][i]=(uint16_t)(i>a);
    gR16MasksReady=1;
  }
  if (!gR8MaskReady) {
    for (int a=0;a<32;a++) for (int i=0;i<32;i++) gR8MaskL[a][i]=(uint8_t)(i>a);
    gR8MaskReady=1;
  }
  memset(gR16H,0,sizeof(gR16H));
  memset(gR8L,0,sizeof(gR8L));
}
static inline u32 rank8_q(u32 d) {
  return (u32)gR16H[d>>5] + gR8L[d>>5][d&31];
}
static inline void rank8_ins(u32 d) {
  u32 hi=d>>5,lo=d&31;
  __m256i h=_mm256_load_si256((const __m256i*)gR16H);
  __m256i hm=_mm256_load_si256((const __m256i*)gR16MaskH[hi]);
  _mm256_store_si256((__m256i*)gR16H,_mm256_add_epi16(h,hm));
  __m256i *row=(__m256i*)gR8L[hi];
  const __m256i *mask=(const __m256i*)gR8MaskL[lo];
  __m256i v=_mm256_load_si256(row);
  _mm256_store_si256(row,_mm256_add_epi8(v,_mm256_load_si256(mask)));
}
static inline void rank8_upgrade() {
  for (int a=0;a<16;a++)
    for (int b=0;b<32;b++) gR16L[a][b]=(uint16_t)gR8L[a][b];
}
static inline bool rank8_fits(const u64 *pk,u32 p,u32 qq) {
  uint16_t groups[16]={};
  for (u32 a=p;a<qq;a++) groups[(u32)(pk[a]>>29)&15]++;
  for (int h=0;h<16;h++) if (groups[h]>255) return false;
  return true;
}
template<int MODE>
static inline void rank_l3_run(u64 *pk,u32 p,u32 qq) {
  if constexpr (MODE==2) rank8_init();
  else if constexpr (MODE==1) rank16_init();
  else cnt_init();
  for (u32 a=p;a<qq;a++) {
    u64 rec=pk[a];
    u32 da=(u32)(rec>>24)&511;
    u32 inc;
    if constexpr (MODE==2) { inc=rank8_q(da); rank8_ins(da); }
    else if constexpr (MODE==1) { inc=rank16_q(da); rank16_ins(da); }
    else { inc=cnt_q(da); cnt_ins(da); }
    u32 ix=(u32)(rec&0xFFFFFFu);
    /* [w8s-K7] mask dropped: bit 24 lands at bit 48 (neighbour/pad), flush masks on read */
    { u32 _c=(u32)(rec>>40)+inc; unsigned char *_p=STG6E(((gBOff[ix>>BSH] += 6u) - 6u));
      *(u64*)_p=(((u64)_c)<<24)|ix; }
  }
}

__attribute__((aligned(64)))
__attribute__((noinline,cold)) static u32 dup_long(const u64 *pk, u32 t, u32 a, u32 ya0) {
  u32 dup = 0;
  for (u32 b = t - a; b < t; b++) {
    u64 r = pk[b];
    __asm__("" : "+r"(r));
    dup += (u32)(((u32)(r >> 24) & 0xFFFFFFu) < ya0);
  }
  return dup;
}
void count_2d(int n, const unsigned *x, const unsigned *y, unsigned *out) {
  if (n <= 0) return;
  if (n == 1) { out[0] = 0; return; }
  if (n <= 2000) {
    memset(out, 0, (size_t)n * 4);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (x[j] < x[i] && y[j] < y[i]) out[i]++;
    return;
  }
  if (n > 16000000) {           // record fields: idx < 2^24, y < 2^24
    memset(out, 0, (size_t)n * 4);
    return;
  }
  static int inited = 0;
  if (!inited) {
    for (int m = 0; m < 8; m++)
      for (int i2 = 0; i2 < 8; i2++) { gMsk[m][i2] = (i2 > m) ? 0xFFFFFFFFu : 0u;
                                       gInc[m][i2] = (i2 > m) ? 1u : 0u; }

    inited = 1;
  }
  u32 np = (u32)n;

  // ------------- sort by x: MSD 8 bits (x>>16) then two BUCKET-LOCAL LSD ----
  // The old form was 3 whole-array LSD passes = 680 MB of DRAM traffic.  Here the
  // two low passes run inside one 256-bucket window (~470 KB), so the second pass
  // reads the bucket from L3 and the write-back hits the line already resident:
  // DRAM drops to stage A (200 MB) + one read + one write-back per bucket (240 MB).
  // Stage A scatters straight from the caller's x/y, so no staging copy is needed.
  // XA / PKA are FREE during stage B and are used as the per-bucket temp (len <= np).
  static u32 bnd[MSN + 1];
  memset(cntb, 0, sizeof(cntb));
  memset(gHis16, 0, sizeof(gHis16));
  /* gBkt is a function of np alone -- no need to count it per element. */
  { u32 _full = np >> BSH, _rem = np & ((1u << BSH) - 1u);
    for (u32 _b = 0; _b < NBKT; _b++)
      gBkt[_b] = (_b < _full) ? (1u << BSH) : (_b == _full ? _rem : 0u); }
  for (int d = 0; d < MSN; d++) { bnd[d] = (u32)d * XBSTEP; cntb[d] = bnd[d]; }
  bnd[MSN] = (u32)MSN * XBSTEP;
  u32 i = 0;
  for (; i + 32u < np; i++) {
    u32 future_dg = x[i + 32u] >> XSH;
    __asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(PKB + cntb[future_dg])));
    u32 dg = (x[i] >> XSH);
    u32 qq = cntb[dg]++;
    PKB[qq] = ((u64)(x[i] & 0xFFFFu) << 48) | ((u64)y[i] << 24) | i;
    { u32 d1 = (y[i] >> 15) & 511, d2 = (y[i] >> 9) & 63;
      ++gHis16[d1][d2]; }
  }
  for (; i < np; i++) {
    u32 dg = (x[i] >> XSH);
    u32 qq = cntb[dg]++;
    PKB[qq] = ((u64)(x[i] & 0xFFFFu) << 48) | ((u64)y[i] << 24) | i;
    { u32 d1 = (y[i] >> 15) & 511, d2 = (y[i] >> 9) & 63;
      ++gHis16[d1][d2]; }
  }
  for (int d = 0; d < MSN; d++) xend[d] = cntb[d];
  /* [w8s-XF] if any x bucket overflowed its fixed slot, redo stage A on the
     legacy variable-length layout (correct for every input; costs one extra pass
     only on skewed data). */
  { u32 _bad = 0;
    for (int d = 0; d < MSN; d++) if (xend[d] - bnd[d] > XBCAP) _bad = 1;
    if (_bad) {
      memset(cntb, 0, sizeof(u32) * MSN);
      for (u32 i = 0; i < np; i++) cntb[(x[i] >> XSH)]++;
      { u32 acc = 0;
        for (int d = 0; d < MSN; d++) { u32 c = cntb[d]; bnd[d] = acc; cntb[d] = acc; xend[d] = acc + c; acc += c; } }
      bnd[MSN] = np;
      memset(gHis16, 0, sizeof(gHis16));
      for (u32 i = 0; i < np; i++) {
        u32 dg = (x[i] >> XSH); u32 qq = cntb[dg]++;
        PKB[qq] = ((u64)(x[i] & 0xFFFFu) << 48) | ((u64)y[i] << 24) | i;
        { u32 d1 = (y[i] >> 15) & 511, d2 = (y[i] >> 9) & 63; ++gHis16[d1][d2]; }
      }
    } }
  /* recover gH512 (the d1 histogram) by summing each row, and detect unsigned short overflow */
  u32 histogram_total = 0;
  for (u32 d1 = 0; d1 < 512; d1++) {
    u32 total = 0;
    for (u32 d2 = 0; d2 < 64; d2++) total += gHis16[d1][d2];
    gH512[d1] = total;
    histogram_total += total;
  }
  const bool need32 = (histogram_total != np);
  if (need32) {
    memset(gHis32, 0, sizeof(gHis32));
    for (u32 i = 0; i < np; i++) ++gHis32[(y[i] >> 15) & 511][(y[i] >> 9) & 63];
    for (u32 d1 = 0; d1 < 512; d1++) {
      u32 total = 0;
      for (u32 d2 = 0; d2 < 64; d2++) total += gHis32[d1][d2];
      gH512[d1] = total;
    }
  }
  for (u32 b = 0; b < MSN; b++) {
    u32 s = bnd[b], e = xend[b], len = e - s;
    if (len <= 1) continue;
    memset(cntb, 0, 256 * sizeof(u32));
    memset(cnb2, 0, sizeof(cnb2));
    for (u32 t = s; t < e; t++) cntb[(u32)(PKB[t] >> 48) & 127]++;
    { u32 a2 = 0;
      for (int d = 0; d < 128; d++) { u32 c = cntb[d]; cntb[d] = a2; a2 += c; } }
    for (u32 t = s; t < e; t++) {
      u64 r = PKB[t];
      u32 dg = (u32)(r >> 48) & 127;
      u32 qq = cntb[dg]++;
      PKA[qq] = r;
      cnb2[(u32)(r >> 55) & 127]++;     /* == the histogram pass 3 used to rebuild */
    }
    /* [w8s-K8] absolute cursors: drop the per-element `s +` */
    { u32 a2 = s;
      for (int d = 0; d < 128; d++) { u32 c = cnb2[d]; cnb2[d] = a2; a2 += c; } }
    for (u32 t = 0; t < len; t++) {
      u32 dg = (u32)(PKA[t] >> 55) & 127;
      PKB[cnb2[dg]++] = PKA[t];
    }
  }
  u64 *pk = PKB;
  u64 *alt = PKA;
  /* ---- LAYOUT: staging-row stride must not be a multiple of the L1 set span.
     Without the pad every row starts at b*2^16 elements = b*2^19 bytes, which IS a
     multiple of 4096, so all NBKT=256 concurrent staging write streams (one per idx
     bucket; idx is uniformly random, so they advance in lockstep and therefore keep
     the same offset within the row) map to the SAME L1 set.  With 8-way
     associativity that is ~31/32 conflict misses on every staging store.
     A pad of STGPADE elements moves row b by b*STGPADE*8 bytes; STGPADE=8 gives a
     row stride of 524288+64 bytes = exactly one set apart, spreading the 256 rows
     over all 64 sets (4 per set).  O(NBKT) work, zero per-element cost -- gBOff is
     already the single source of truth for both the L3 store and the flush. */
  { u32 acc = 0; for (int b = 0; b < NBKT; b++) { gBOff[b] = acc; acc += 6u * (gBkt[b] + STGPADE); } gBOff[NBKT] = acc; }

  // ---------------- L1 bucket offsets (histogram filled in stage A) -------
  { u32 acc = 0;
    for (int d = 0; d < 512; d++) { u32 c = gH512[d]; gBnd[d] = acc; gCur[d] = acc; acc += c; } }
  gBnd[512] = np;

  // ---------------- L1: MSD 8 bits (y bits 23..16) -> alt ----------------
  cnt_init();
  {
    for (u32 bb = 0; bb < MSN; bb++) {
    u32 t = bnd[bb], bnde = xend[bb];
    u32 prevx = 0xFFFFFFFFu, a = 0;
    /* lane j of yhist = y of the j-th most recent element of this group */
    __m256i yhist = _mm256_setzero_si256();
    for (; t < bnde; t++) {
      u64 rec0 = pk[t];
      u32 xv = (u32)(rec0 >> 48);
      u32 eq = (u32)(xv == prevx);
      prevx = xv;
      a = (a + 1) & (0u - eq);
      u32 ya0 = (u32)(rec0 >> 24) & 0xFFFFFFu;
      __m256i yb = _mm256_set1_epi32((int)ya0);
      u32 dup0;
      if (a < 8) {
        /* Compare only valid recent y values in the current x group. */
        u32 mm = (u32)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(yb, yhist)));
        dup0 = (u32)__builtin_popcount(_bzhi_u32(mm, a));
      } else dup0 = dup_long(pk, t, a, ya0);
      yhist = _mm256_blend_epi32(
          _mm256_permutevar8x32_epi32(yhist, _mm256_setr_epi32(7,0,1,2,3,4,5,6)),
          yb, 1);
      {
        u64 rec = rec0;
        u32 dup = dup0;
        u32 d = (u32)(rec >> 39) & 511;
        u32 inc = cnt_q(d);
        cnt_ins(d);
        u32 q = gCur[d]++;
        u32 cnt = (0x1000000u - dup) & 0xFFFFFFu;
        cnt = (cnt + inc) & 0xFFFFFFu;
        alt[q] = ((u64)cnt << 40) | (rec & 0x0000007FFFFFFFFFull);
      }
    }
    }
  }

  // -------- fused L2 (y bits 15..8) + L3 (y bits 7..0) + store -----------
  for (u32 b0 = 0; b0 < 512; b0++) {
    u32 s = gBnd[b0], e = gBnd[b0 + 1];
    u32 m = e - s;
    if (m == 0) continue;
    /* [w8s-K1] Rebase the L2/L3 working window to PKB[0..m): every d1 group
       reuses the same resident window instead of walking 80 MB of cold lines. */
    u64 *pk = PKB - s;
    if (m == 1) {
      { u32 _ix = (u32)(alt[s] & 0xFFFFFFu); u32 _c=(u32)((alt[s]>>40)&0xFFFFFFu); unsigned char *_p=STG6E(((gBOff[_ix >> BSH] += 6u) - 6u));
        *(u64*)_p=(((u64)_c)<<24)|_ix; }
      continue;
    }
    // histogram + out prefetch while the bucket is read the first time
    { u32 acc = 0;
      for (int d = 0; d < 64; d++) {
        u32 c = need32 ? gHis32[b0][d] : (u32)gHis16[b0][d];
        gHis[d] = acc; gCur[d] = s + acc; acc += c;   /* [w8s-K5] absolute cursors */
      }
      gHis[64] = acc; }
    if (m <= 65535u) {
      r64_init();
      for (u32 t = s; t < e; t++) {
        u64 rec = alt[t];
        u32 d = (u32)(rec >> 33) & 63;
        u32 inc = r64_q(d);
        r64_ins(d);
        u32 q = gCur[d]++;
        /* [w8s-K3] same value, two fewer ops: the carry out of bit 63 is
           dropped and bits 0..39 are untouched. */
        pk[q] = rec + ((u64)inc << 40);
      }
    } else {
      cnt_init2();
      for (u32 t = s; t < e; t++) {
        u64 rec = alt[t];
        u32 d = (u32)(rec >> 33) & 63;
        u32 inc = cnt_q2(d);
        cnt_ins2(d);
        u32 q = gCur[d]++;
        /* [w8s-K3] same value, two fewer ops: the carry out of bit 63 is
           dropped and bits 0..39 are untouched. */
        pk[q] = rec + ((u64)inc << 40);
      }
    }
    /* L3 inside pk[s..e): the runs are exactly the d1 groups laid down by the scatter
       above, so their boundaries are already known from the prefix sums that were just
       computed -- no need to re-scan pk to discover them.  (Same order, same runs.) */
    for (u32 d1 = 0; d1 < 64; d1++) {
      const u32 p = s + gHis[d1], qq = s + gHis[d1 + 1];
      if (p == qq) continue;
      if (qq - p == 1) {
        { u32 _ix = (u32)(pk[p] & 0xFFFFFFu); u32 _c=(u32)((pk[p]>>40)&0xFFFFFFu); unsigned char *_p=STG6E(((gBOff[_ix >> BSH] += 6u) - 6u));
          *(u64*)_p=(((u64)_c)<<24)|_ix; }
      } else {
        /* within a run of equal (d1,d2) the remaining digit is d3 = y&255 */
        if (qq-p > 65535u) rank_l3_run<0>(pk,p,qq);
        else if (qq-p <= 512u) rank_l3_run<2>(pk,p,qq);
        else rank_l3_run<1>(pk,p,qq);
      }
    }
  }
  // ---- flush: walk the staging array one idx-bucket at a time so every
  //      out[] store lands inside a 64 KB (BSH=14) L2-resident window ----
  {
    for (u32 b = 0; b < NBKT; b++) {
      /* After the scatter gBOff[b] is the running END of row b (the scatter uses it
         as a cursor), so the row is [gBOff[b]-gBkt[b], gBOff[b]) -- "next row's
         base" is no longer the same thing once the rows are padded. */
      u32 e = gBOff[b] / 6u;
      u32 t = e - gBkt[b];
      for (; t + 64u < e; t++) {
        u64 _pf; __builtin_memcpy(&_pf, STG6E(6u * (t + 64u)), 8);
        __asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(&out[(u32)(_pf & 0xFFFFFFu)])));
        u64 r; __builtin_memcpy(&r, STG6E(6u * t), 8); out[(u32)(r & 0xFFFFFFu)] = (u32)((r >> 24) & 0xFFFFFFu); }
      for (; t < e; t++) {
        u64 r; __builtin_memcpy(&r, STG6E(6u * t), 8); out[(u32)(r & 0xFFFFFFu)] = (u32)((r >> 24) & 0xFFFFFFu); }
    }
  }
}

#pragma GCC pop_options

评测结果