// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#107073**
// <https://duck.ac/submission/107073>（207.759776 ms = 我方当值最好件）—— **本文件正文的逐字节基座**
// （工作副本 `problems/1008/work/y8f_pfwAB_b3.cpp`）。**本发只在其之上加 1 条 `prefetchw`。**
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#107041**（208.130655）与 **#107037**（208.278708）
// —— 同账号另一席 `w8q_` 的两条"预取守卫剥离"，已含在 [1] 内，血统注释在 [1] 头部保留。
// [3] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 **#106823**
// <https://duck.ac/submission/106823>（224.161589 ms）—— **本发要复价的那条负读数**：
// 同站点加 `__builtin_prefetch(...,1,...)` 读到 **+5.31% ✗**。**本发未取用它的任何一行代码**；
// 引用它正是因为**那一臂的机制是错的**（见思路段）。**本发是第一席 `y8c_` 的同一意图、正确机制重做。**
// [4] duck.ac 用户 saffah_codex_6s_agg2，提交 **#106959**
// <https://duck.ac/submission/106959>（208.158054 ms = 本题实时 T / 榜首）。只作门槛计算，未取用任何代码。
// [5] 本工作区 `BRIEF.md` **§2.19.498**（本席入库：`__builtin_prefetch(p,1,·)` 与内联 `prefetchw` 不是同一把刀；
// 凡用前者得到的"prefetchw 负例"一律**降级为未定价**、须用内联 asm 复价）· **§2.19.416**（提示通道改动必须看反汇编；
// 带 `unroll` 的环里禁止 per-element 守卫）· **§2.19.340**（预取判据：新增请求负 / 把已有预取修对正 /
// `§2.19.383` 的在飞饱和）· **§2.19.444**（构建完整性三查）· **§2.19.489**（组合件声明）。只用于机理判断。
// ======================
// ===== 思路 =====
// 【本发 = 单变量：新增**一条** `prefetchw`】站点 = 融合 L2+L3 段的 `pk[q]` 散写（80 MB 冷散写，`y8f_base3` L569）。
// 【为什么这条负读数必须复价（`§2.19.498` 的强制后续）】
// `#106823` 在**同站点**读到 **+5.31% ✗**，但那一臂写的是 `__builtin_prefetch(..., 1, ...)` ——
// **该 intrinsic 的 rw=1 写意图位被 gcc 丢弃**：判题机同款 **gcc 9.3 实编 `prefetcht0`、0 条 `prefetchw`**
// （`tools/gcc93check.py --show prefetch` 实核，本席已在 `#107038` 上验证该静默失效）⇒
// **行以 S 态到达，被覆盖的散写 store 仍要付一次 RFO 升级** ⇒ 那一发测的是 `prefetcht0`，**不是 `prefetchw`** ✓
// 【机理：为什么本发预期 ≥ 0（与"加一族预取"不同）】
// * **无预取**时：store → RFO（取行到 E/M）⇒ **1 次事务，但延迟裸露在 store 上**；
// * **`prefetcht0`**时：prefetch（取到 S）→ store → **升级 RFO** ⇒ **2 次事务** ⇒ 这正是 `#106823` 为负的原因；
// * **`prefetchw`**时：prefetch（取到 E/M）→ store 命中 ⇒ **1 次事务，且延迟被隐藏** ⇒
// **事务数不比无预取多，但把延迟藏起来了** ⇒ 与"新增一整族预取"（`§2.19.340` 的 +1.98% ✗ / 在飞饱和）**不同** ✓
// * 残留风险（诚实写明）：它仍**多占一个在飞名额**，而 `y8c_` 归因过"该相位在飞容量已饱和" ⇒
// **本发正是对"饱和"这一归因的判决性复价**：若仍为负 ⇒ `pk[]` 这条**用正确机制也关闭**；
// 若为正 ⇒ 说明之前是**机制错**而不是饱和 ✓
// 【形态（`§2.19.416`）】**前瞻环 + 尾环**，**无 per-element 守卫**（守卫进体会让 gcc 静默放弃
// `unroll-loops`，而本文件全局开了 `#pragma GCC optimize("O3,unroll-loops,rename-registers")`）✓
// 前瞻 32 取自 `#106823` 的同值（保持与那一臂可比、且不改第二个变量）。目标地址 = `pk + s + gCur[df]`
// （`df` 取自 `alt[t+32]` 的同一位段）—— 因 `gCur` 是活游标，**地址只是近似**；这与 `#106823` 用的是同一近似 ✓
// `alt[t+32]` 的读取由**循环条件** `t + 32u < e` 保护 ⇒ **无越界读** ✓（prefetch 本身也不产生缺页）
// 【判题机 gcc 9.3 实核】**编译 0 错误**；`--show prefetch` ⇒ **`11 × prefetchw`、`0 × prefetcht0`**
// （10 条来自 [1] 已转换的既有站点 + 1 条本发新增）✓
// 【构建完整性三查（`§2.19.444`）】① `.text` 与基座同量级 ✓ ② `#pragma GCC optimize/target` 与
// `#define MSH/MSN/XSH/NBKT/BSH/STGPADE` 全部原样在位 ✓ ③ 纯前置注释头，正文与已闸门的件逐字节相同 ✓
// 【闸门（14 组）】小 n（3000/20000，6 种数据形态）与**暴力对照 BRUTE-OK**；大 n（1e6、**生产 1e7**）FNV **逐位相同** ✓
// **纯提示、零语义**：两环的循环体**逐字相同**，元素的处理顺序与 `gCur[d]++` 的时序**完全不变** ✓
// 【口径（`§2.19.410/443`）】`mine = 207.759776 (#107073)` · `T = 208.158054` · 严支真靶 **`206.077473`**
// ⇒ 还需 **1.682303 ms（0.810%）**。**本发按真靶评估。**
// ================
// ===== 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 - 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];
alignas(64) static u64 PKA[NMAX], PKB[NMAX];
alignas(64) static u32 DUPA[NMAX];
static u32 cntb[MSN];
static u32 cnb2[128];
static u32 gH512[512];
#define NBKT 512
#define BSH 15
#define STGPADE 16 /* staging-row pad, in u64 elements (8*8 = 64 B = one L1 set) */
alignas(4096) static u64 g_STG[NMAX + 16 * NBKT]; // + one L1-set pad per staging row (see below)
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(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 u16 = 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);
g_STG[gBOff[ix>>BSH]++]=((u64)((((u32)(rec>>40)+inc)&0xFFFFFFu))<<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 (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; acc += c; } }
bnd[MSN] = np;
u32 i = 0;
for (; i + 64u < np; i++) {
u32 future_dg = x[i + 64u] >> 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]; }
}
/* recover gH512 (the d1 histogram) by summing each row, and detect u16 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 = bnd[b + 1], 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 */
}
{ u32 a2 = 0;
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;
u32 qq = cnb2[dg]++;
PKB[s + qq] = 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 += 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 = bnd[bb + 1];
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;
if (m == 1) {
{ u32 _ix = (u32)(alt[s] & 0xFFFFFFu); g_STG[gBOff[_ix >> BSH]++] = ((alt[s] >> 40) << 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] = acc; acc += c;
}
gHis[64] = acc; }
cnt_init2();
{
u32 t = s;
for (; t + 32u < e; t++) {
u32 df = (u32)(alt[t + 32u] >> 33) & 63;
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(pk + s + gCur[df])));
u64 rec = alt[t];
u32 d = (u32)(rec >> 33) & 63;
u32 inc = cnt_q2(d);
cnt_ins2(d);
u32 q = s + gCur[d]++;
u32 cnt = ((u32)(rec >> 40) + inc) & 0xFFFFFFu;
pk[q] = ((u64)cnt << 40) | (rec & 0x0000001FFFFFFFFull);
}
for (; t < e; t++) {
u64 rec = alt[t];
u32 d = (u32)(rec >> 33) & 63;
u32 inc = cnt_q2(d);
cnt_ins2(d);
u32 q = s + gCur[d]++;
u32 cnt = ((u32)(rec >> 40) + inc) & 0xFFFFFFu;
pk[q] = ((u64)cnt << 40) | (rec & 0x0000001FFFFFFFFull);
}
}
/* 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); g_STG[gBOff[_ix >> BSH]++] = ((pk[p] >> 40) << 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];
u32 t = e - gBkt[b];
for (; t + 64u < e; t++) {
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(&out[(u32)(g_STG[t + 64u] & 0xFFFFFFu)])));
u64 r = g_STG[t]; out[(u32)(r & 0xFFFFFFu)] = (u32)(r >> 24); }
for (; t < e; t++) {
u64 r = g_STG[t]; out[(u32)(r & 0xFFFFFFu)] = (u32)(r >> 24); }
}
}
}
#pragma GCC pop_options
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 219.142 ms | 267 MB + 180 KB | Accepted | Score: 100 | 显示更多 |