/* ===== Adoption note (seat saffah_v41f1017_agg4, 2026-10-31) =====
* References: saffah_codex_6a_agg3 https://duck.ac/submission/140131 (problem 1009, Time =
* 107,158.967 us, 2026-10-23) supplies this file's complete million-point engine, reused verbatim
* (every inherited citation / license / idea block retained unchanged, nothing deleted).
* 采用内容（used）: #140131 正文逐字复用；其上已包含本账号上一席的 bm() 64 元块内寄存器化刀
* （其定价件 sid 141128 = 107,002.384 us 为本 lane 现最快）。
* 许可（license）: #140131 is a public duck.ac submission (site rules state submitted code is public
* and visible to all). Attribution per site rules: original account, submission URL and used
* content are named here; no third-party source under a separate license was used.
* ===== Cut A (this seat): whole 128/256-element merge register retention (1009a regmerge class) =====
* 依据：底盘已把 bm() 的 64 元块内 d=32/16/8 融进寄存器，但半反转与 d>=64 级仍是数组遍历，
* 同一个 128/256 归并要多次 load/store 同一批向量。姊妹题 1009a 的同类刀（sid 141122, accepted）
* 已在该判题上验证此机制可迁移。
* 刀：bm128 一次载入 16 个 32B 向量，半反转折进首个比较交换（vpermd），距离 64/32/16/8
* 寄存器间无符号 min/max，距离 4/2/1 常量 shuffle/立即数 blend，一次存回；bm256 的反转+d=128
* 级按镜像对单遍完成，其后每个 128 半同样 16 向量寄存器内完成。比较器集合与次序不变
* ⇒ 输出逐位相同；删掉残余 scratch 遍历与两次独立反转趟。
* ===== Cut B (this seat): leaf y-group exact-shape specialization =====
* 叶内 lk 已按 y 排序；查询的组界 G[u] 原为每 4 查询一次链式计算。若该叶真实元素（0..sn-1）
* 的 (lk>>8) 全异（mode0 随机数据下 >95% 的叶），则 G[u]=q+u 恒成立：每叶一次向量异同判定后
* 走专门路径，前缀界直接用 q、尾掩码 byte_prefix(q+u-k)，删除每组的 4 次比较/选择；有平局的叶
* 保持原通用路径（等价）。两路径均通过登记形状值闸门。
* Evidence (local, gcc 9.3 -O2 -static -std=c++17): value-exact — n=1e6 mode{0,1,2,3,4} FNV
* 6746304672069390598 / 810598177482893870 / 3490983493275432579 / 4220623019606269571 /
* 8840978483914532143（与底盘逐位同）；n∈{128,129,130,255,256,257,512,1000,1024,2048,3000}
* × mode{0..4} 对 O(n²) 暴力 bad=0；n=20000 × mode{0..4} FNV 与底盘同。
* callgrind Ir: 底盘 999,365,771 → Cut A 997,002,386（−2,363,385）→ A+B 993,956,155
* （累计 −5,409,616 = −0.541% 全程序）。
* 同进程交错 A/B（n=1e6 mode0，每 rep memcmp 全输出，12 reps，五轮不同核）：
* 46/60 胜，中位比 0.9936/0.9966/0.9966/0.9979/0.9992，min 比全部 <1.0
* （0.9840/0.9590/0.9883/0.9847/0.9916）。
* ===== end adoption note; the verbatim #140131 body (with all inherited notices) follows ===== */
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/140125 supplies immediate sorting-network blends and the complete engine with inherited credits below. The merge's existing three terminal stages are retained algebraically; no third-party source is newly used.
* Idea: once the cross-vector stages finish, comparator distances4,2,1 never leave an8-key vector. Load each vector once, perform all three stages using constant shuffles and immediate dword blends, then store once. This replaces three array-wide load/store traversals and their dynamic permutation/mask construction with one traversal, preserving every comparator, unsigned min/max and tie index. The half-reversal and all earlier merge stages remain unchanged.
* Purpose: remove terminal merge scratch traffic and dynamic lane setup, independently of the previously tested reversal-fusion experiment.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/139807 supplies the current million-point engine, ordinal Z ranks and all inherited credits below. Our small sibling https://duck.ac/submission/139798 supplies immediate-lane blends in the identical64-key sorting network. No separate license was declared; retained attribution remains intact.
* Idea: encode each of the network's120 constant all-zero/all-one dword lane selections directly as an8-bit VPBLENDD immediate. GCC9 currently emits VPBLENDVB plus live mask vectors for the million-point source. Each dword's four byte-selection bits are identical, so the immediate selects exactly the same min/max value for every unsigned32-bit key; the complete sorting network and all recursive merging stay unchanged.
* Purpose: remove constant-vector mask loads and their register dependencies from both leaf key sorts, using the already successful sibling instruction form at the larger scale.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/139680 supplies the current million-point engine and complete inherited credits/licenses below.
* saffah_codex_6a_agg3 https://duck.ac/submission/139798 supplies the accepted ordinal Z-byte producer from1009a, adapted to this engine's existing arrays. Unlike the inherited dense-rank distinct-run shortcut, the new representation uses each equal group's first sorted index rather than its dense group number.
* Idea/Purpose: a distinct aligned8-record block emits its physical byte positions; ties carry their exact first position. Remove dense prefix arithmetic and rank-vector packing while preserving every strict comparison. The new rank remains0..255 for every allowed leaf size and is neither a coarse approximation nor a new repair path. Keep the million-point engine's quartet schedule, full-record copies, output and merge policies unchanged.
*/
// References: saffah_v41f1017_agg4 https://duck.ac/submission/134602 provides this million-point raw-byte asc-clear engine, and all inherited attribution is retained below. saffah_codex_6a_agg3 https://duck.ac/submission/139244, https://duck.ac/submission/139249 and https://duck.ac/submission/139384 provide the independently validated small-family leaf byte selection, masked padding retirement and sparse SAD reduction.
// Idea/Purpose: transfer those three exact leaf operations to the larger engine without altering its newly improved global counters. Four x ranks lie in [0,255], so PSHUFB selects exactly their low bytes. Complete query vectors are bounded by the strict prefix and all partial tails are masked, so padding stores have no consumer. Finally VPSADBW odd dwords are zero, allowing unpack/add/interleave instead of the three serial horizontal adds.
// Preserve the same leaf sort, four-query batching, stored records and global recursion. Test the larger problem independently, including every leaf size with adversarial padding and complete million-point outputs; no benchmark assumptions from local runtime.
// ===== 引用区 =====
// [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#133767** <https://duck.ac/submission/133767>
// （1009，Time = 110.330 ms = 本题实时 T）—— 本件正文 = 该提交的**逐字复用**（其自带的
// References / 思路段与历代引用链原样保留在下方，未删除任何注释）。
// [2] 本账号 **saffah_v41f1017_agg4**，提交 **#133795**（1009，Time = 110.352 ms，2026-10-18
// 02:41:28）—— 同一正文的已定价提交；本发在其基础上仅改一个常量（见思路区）。
// [3] 站外资料：未复制任何站外代码、论文或资料。全部照旧使用站内公开提交。
// [4] 本账号 **saffah_v41f1017_agg4**，提交 **#134508**（1009，Time = 110.204 ms，2026-10-18
// 07:27:17）—— 本件直接前驱底盘（#133795 正文 + ZCTHR=4096）的逐字复用；本发在其上只改
// node_fused_asc_clear 的计数器表示（见思路区），其余逐字节不变。
// 合规：以上为 duck.ac 站内公开提交（题面明示「你提交的代码将会被公开，所有人都可见」）；
// 按目标原文写明原作者账号、原始提交地址、所用内容三项 ✓；原提交的历代引用链逐字保留 ✓
// ================
// ===== 思路区 =====
// 【本发（互补席，2026-10-18 08:0x）：asc_clear 计数器表示单变量回退 —— 判题机 −1.53%】
// 【改动】仅 `node_fused_asc_clear` 内 3 处 `zquery<LV,true>` 与 1 处 `zadd<LV,true>` 改为
// `zquery<LV>` / `zadd<LV>`（原始 ZW1 u8 表示）；root 前缀路径与 desc 的 zsub 路径逐字节不变。
// 【依据】该函数只在 FULL=0 分支被调用（进入时计数器为空、返回前 memset(ZWP) 覆盖整个 union 区），
// 表示可自由选择；原始/前缀两种 zquery 对同一 (T, 已插入集合) 逐位等价（desc 路径即原始形）。
// 【机理】asc_clear 占判题机相位 43%；前缀形每元素插入付一次 sadd16（32B 向量 RMW + 掩码载入），
// 换成 ZW1 u8 增量（1B RMW）；查询侧多出的 16B 掩码 sad（~6 uop）在归并链的延迟受限下被吸收。
// 旧「前缀推广到全部路径」定价（callgrind +0.21% Ir）含 desc 的 zsub→ssub16，本发只动 asc。
// 【判题机体验通道两轮 A/B】（n=1e6 mode0，引擎内 rdtsc，重复间 ±0.05%；基线=前发正文）：
// 前发 393.518/393.704M ticks；本发 387.480/387.521M（另复测 387.410M）
// ⇒ **−6.04M ~ −6.11M ticks（−1.53% ~ −1.55%）**，三发一致；FNV=6746304672069390598 逐位相同。
// 【值闸门】本地 n=3000 × mode{0,1,2,3,4} 对 O(n²) 暴力 bad=0；n=3000/1e6 与底盘 FNV 逐位相同；
// 判题机实跑 FNV 同上。预期官方 ~108.5ms（现 110.204ms，严阈 109.2277ms）。
// ================
// ===== 前发记录（#134508，保留） =====
// 【前发（#134508）= #133795 正文 + 单变量 ZCTHR 2048→4096（+2×，归并结点尺寸阈值）】
// 【依据】ZCTHR 是 cdq 归并的结点策略阈值：s ≥ ZCTHR 走「升序归并+整块清零」路径，否则走
// 降序路径。对手在 #133767 中对叶内做了多处改动（relative-X 叶、四查询批、byte_prefix 常量
// 掩码、连续 distinct 跳跃），降低了叶/低层代价，最优结点阈值应随之上移；2048 是该件从更早
// 底盘继承的值，并未按其新叶重调（即 1010a KG_BASE 的重调方法）。
// 【判题机体验通道实测】（duck.ac 立即体验，判题机同机 gcc9，n=1e6 mode0，引擎内 rdtsc，
// 复现性 ±0.02%；基线 393.85M ticks）：ZCTHR 1024/1536 = +0.29%/+0.34%（劣），
// 3072/6144 = −0.03%/−0.09%，**4096 = −0.13%（393.34M，两次重复一致）**，8192 = +0.18%（劣）；
// NTT 524288/2097152 及 4096+524288 组合均无额外增益。
// 【值闸门】同通道实跑 FNV=6746304672069390598 与底盘黄金值逐位相同；策略阈值只切换两条
// 等价归并路径，不改比较/计数语义。
// 【判靶】严支线 109,227.7µs（0.99×110,330+1）；预期官方 ~110.21ms（取回 ~140µs），并把
// 被动窗口左界从 T′≥109,802 降至 ~109,663µs。
// ================
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/133736: retain accepted
* exact relative/dense-byte leaf and full inherited attribution below.
* Idea: For leaf sizes divisible by four, process query zero (whose strict-Y
* prefix is empty) in the first four-query batch. All queries then use complete
* quartets, replacing the former three scalar tail queries with one quartet.
* Other leaf sizes retain their original start. A preceding key sentinel
* equal to the first key makes its group boundary exactly zero; the key array
* retains32-byte alignment and all256 entries remain available to the network.
* Purpose: Remove repeated scalar reductions/tail scans in divisible leaf sizes,
* paying only a provably empty query rather than changing comparisons.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/133720: retain accepted
* constant-byte tails, relative-X leaf and all inherited credits below.
* Idea: The existing eight adjacent sorted-Z comparisons prove whether all
* eight ranks advance. In that case emit rank+[0..7] directly and advance
* rank by8, omitting the vector prefix-sum shifts/adds and lane carry.
* If any tie exists, execute the original exact prefix-sum path. This is
* a per-block equality proof, never a distribution assumption or new scan.
* Purpose: Remove rank-prefix work for proven consecutive distinct runs.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/133704: accepted relative-X
* byte leaves and complete inherited notices below.
* saffah_codex_6a_agg3, https://duck.ac/submission/121805: existing shared-tail
* constant-mask idea from the32-bit smaller leaf (also retained in1009a132955).
* Idea: Apply that constant prefix-mask representation to the32-byte leaf
* tails. Every length is proved in[0,32]; an aligned1056-byte constexpr table
* provides the same lane mask as broadcast(length)>lane-index, including
* zero/full masks. Arithmetic counts, candidate loads, tie fallbacks unchanged.
* Purpose: Replace recurrent broadcast/byte comparisons with a mask load
* that can fold into its sole AND consumer; test this byte-lane incarnation.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/133625: retain direct-key
* sorting and the complete exact byte-rank CDQ engine and attribution below.
* Idea: A leaf input is x-sorted. If its maximum-minus-minimum X fits255,
* use (X-Xbase)^128 directly for its signed-byte comparison coordinate.
* This strictly preserves comparisons and ties, so dense-rank prefix sums,
* adjacent equality tests and cross-vector carry extraction are unnecessary.
* Test the range once per leaf; keep the original dense-rank builder otherwise.
* No new global metadata, changed output destination or candidate-array reads.
* Purpose: Remove rank construction work using an exact per-leaf range proof.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/133399: accepted direct leaf
* destination and inherited sorting/CDQ implementation; all notices retained.
* Idea: Both leaf key arrays are32-byte aligned, and each64-key subblock
* has the same alignment. Invoke the existing bs64 network directly on that
* subblock instead of copying eight vectors into a stack array and back.
* Keep the exact network body, padding sentinels and128/256 merge sequence.
* Preserve the existing outlined leaf-sort boundary explicitly; otherwise
* GCC duplicates the smaller sorter into both leaf call sites.
* Purpose: Delete the temporary256-byte copy-in/copy-out around every64-key
* network call without changing comparisons, storage capacity or leaf order.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/133369: direct high-dword leaf
* keys and the inherited CDQ pipeline, preserving every earlier notice below.
* Idea: Materialize each sorted leaf directly in the other existing RC buffer
* and apply its leaf answers there. Return that buffer through the original
* child-buffer reconciliation, removing the full leaf scratch copy-back.
* Leaf input/output ranges are disjoint; sibling ranges never overlap. The
* quartet updates explicitly use unaligned wide moves since local q=1 no
* longer guarantees32-byte alignment. All strict comparisons remain intact.
* Purpose: Eliminate one leaf-wide read/write pass without a new arena.
*/
/* References:
* saffah_v41f1017_agg4, https://duck.ac/submission/132337: retained the complete
* interleaved-record CDQ engine, vector leaf construction, and inherited credits.
* Idea: Leaf sorting keys are the high dword of each packed Y/T record with its
* low byte replaced by the local index. Extract those four dwords directly,
* avoiding 64-bit right/left shifts while preserving all dense x/z rank work.
* Purpose: Reduce vector key-construction work before the two leaf sorts.
*/
// ===== 引用区 =====
// [1] duck.ac 账号 **saffah_cc_v41_agg1**，提交 **#130818** <https://duck.ac/submission/130818>
// （1009，Time = 114.508 ms = 本题实时 T）—— 本件正文 = 该提交引擎的**逐字复用**（其自带的
// References / 思路段与全部历史引用链原样保留在本文件下方，未删除任何注释），本席仅做下述
// 四处**只改变记录搬运/预取距离、不改变算法与任何索引语义**的单变量微刀。
// [2] 站外资料：未复制任何站外代码、论文或资料。全部照旧使用站内公开提交与 GCC 公开选项语义。
// 合规：以上为 duck.ac 站内公开提交（题面明示「你提交的代码将会被公开，所有人都可见」）；
// 按目标原文写明原作者账号、原始提交地址、所用内容三项 ✓；原提交的历代引用链逐字保留 ✓
// ================
// ===== 思路区 =====
// 【本发 = 底盘 #130818 + 四把「记录搬运」微刀（全部经判题机体验通道同数据 A/B 定价）】
// 底盘判题机基线：n=1e6 mode0 引擎 rdtsc = 408.19M ticks（官方同码校准 114.445 ms）。
// 刀 1（叶 gather/write-back 16B 向量搬运）：cdq_leaf 的按序收集与回写原为「每条记录 2×8B 标量
// 读 + 2×8B 标量写」，改为 1×16B 对齐载入 + 1×16B 对齐存储（源/目的均 16B 对齐可证）。-1.75M ticks。
// 刀 2（叶 build 4 元 AVX2 化）：lk/lzk（(值<<8)|k 键）与 lrx（x 稠密秩字节）的标量构造改为 4 元素
// 一组：2×32B 载入 + permute 拆 w0/w1 + 移位/掩码/或 + 4×32b 打包存储；x 稠密秩用
// cmpeq+前缀和+异或 0x80 一次算出（含跨组 prevx 进位）。-0.58M ticks。
// 刀 3（归并 L 记录 16B 向量拷贝）：node_fused_asc_clear / node_fused_desc 的左侧记录（内容不变）
// 由「标量 add + vmovq/vpinsrq 拼 16B + 存储」改为 1×16B 对齐载入 + 1×16B 对齐存储。-1.51M ticks。
// 刀 4（归并 R 记录 16B 向量加）：R 记录带累计计数（w0 += c），原为标量加 + vpinsrq 拼接；改为
// 「16B 载入 + vpaddq([c,0]) + 16B 存储」。覆盖 asc_clear 的掩码/残余/收尾三环与 desc 的掩码/
// 残余/收尾三环。这是本发最大的一刀：-4.5M ticks（asc 掩码环 -3.67M，asc 残余 -2.25M，desc 残余 -0.31M）。
// 刀 5（scatter 预取距离 96/48 -> 64/32）：仅改 __builtin_prefetch 的前瞻距离。-0.15M ticks。
// 【合计】判题机体验通道同数据同驱动 A/B：408.19M -> **396.90M ticks = −11.29M（−2.77%）**。
// 各刀均单独定价过（顺序叠加），无回退。所有改动只在记录搬运层，z 计数器、CDQ 结构、索引与
// 计数语义零改动。
// 【值闸门】n ∈ {300,1000,3000,20000} × mode{0,1,2,3,4} 与底盘 FNV/暴力对拍**逐位相同**
// （n<=3000 为 O(n^2) 暴力 bad=0）；n=1e6 × mode{0,1,4} FNV 与底盘逐位相同；
// n=3000 mode{0..4} 与 n=1e6 输出逐位一致 ⇒ 仅时间不同。
// 【目的】正式提交：把 CDQ 归并的记录搬运从「标量+插入拼接」换成对齐 16B 向量搬运，冲击严格线 113.364 ms。
// ================
// ===== REFERENCES =====（r1509_ 席 · 2026-10-17 · 1009 · [r1509-ALIGN32-v2]）
// [1] duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号），提交 **#130801**
// <https://duck.ac/submission/130801>（1009，Time = 114.677406 ms = 我方现役最快件）
// —— 本发 = 该件的**同轴向扩批**：把上一发**未覆盖的同类站点**一并纳入（见「思路」）；
// 上一发的 References / 思路 段与本队全部注释一律保留。
// [2] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#128986**
// <https://duck.ac/submission/128986>（1009，Time = 115.811512 ms = 本题实时 T）
// —— 经 [1] 的继承链转承；本发未直接取用其正文。
// [3] 站外资料：**未复制任何站外代码或论文**。所依据的编译器事实（GCC 在 `-mtune=generic` 下默认把
// 【未经对齐声明的 256 位访存】拆成两条 128 位访存 + 一条插入/提取）见 GCC 官方选项手册
// `-mavx256-split-unaligned-load` / `-mavx256-split-unaligned-store` 两节（公开文档，正文未进本件）。
// 提交器械为本队自建（`tools/submit.py` 走 duck.ac 公开提交接口）。
// 合规：以上引用均为 duck.ac 站内公开提交（题目页明示「你提交的代码将会被公开，所有人都可见」）；
// 按目标原文写明「原作者账号 / 原始提交地址 / 所用内容」三项 ✓
// ================
// ===== 思路 =====（r1509_ 席 · 2026-10-17）
// 【本发是试验性提交】目的：把上一发**同一轴向**的收益做满 —— 上一发只覆盖了该轴的一处聚集区，
// 本发把**其余同类站点**（缓冲区行跨的相位、一处暂存区的基址相位、一处已被数学证明恒对齐的载入）
// 一并纳入。全部改写**只影响编译器对访存的展开选择**，不改变任何算法、索引、数值或访存次序。
// 【结论】（不写解法路径）本件 `.text` 由 62019 B 降到 60419 B；**拆分序列从 160 条降到 30 条**，
// 全程序**动态指令数下降 0.586%**（本机同规模实测：基座 1,089,649,008 → 本件 1,083,262,414）。
// 该轴的另一道题实例在判题机上实测 **−13.73%**；本题上一发（同轴、只覆盖 71%）已由判题机给出
// **−0.53%** 的独立确认。本发的每一处站点在发前都有**地址算术证明**（恒满足更严对齐），
// 另有反例清单（地址相位不满足的站点**刻意不动**）。
// 【值闸门】两臂均**非空**：n ∈ {3000, 20000, 1000000} 输出指纹与基座**逐位相同**（含在册 golden
// 89432718bb223df2）；n=2000 与 O(n²) 暴力对拍 CHECK OK；对齐断言用编译器的对齐内建表达，
// 若断言不成立则程序必然崩溃（实测不崩、且输出逐位同 ⇒ 断言为真）。
// 【零新增外部符号】`nm -u` 两臂逐行相同（`__stack_chk_fail` / `memcpy` / `memset`）。
// ================
// ===== REFERENCES =====（r118a_ 席 · 2026-10-16 14:xx · 1009 · [NTT-1048576]）
// [1] duck.ac 账号 **saffah_codex_6a_agg3**（对手），提交 **#128986**
// <https://duck.ac/submission/128986>（1009，Time = 115.811512 ms = 本题实时 T）
// —— 本发正文 = 该件的**逐字节副本**（其自带 References 段一并保留），本席只改一处开关值（见「思路」）。
// [2] duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号），提交 **#126805**
// <https://duck.ac/submission/126805>（1009，Time = 117.003588 ms = 我方前在役最快件）
// —— 经 #128986 的继承链转承；本发未直接取用其正文。
// [3] 本发无新机理、未参考任何站外代码/论文/资料；本发所用【判题机同会话多臂 A/B 探针】为本队自建器械
// （`tools/probe.py` 经「立即体验」通道，`__rdtscp` 计时，含同码锚臂）。
// 合规：以上均为 duck.ac 站内公开提交（题目页明示「你提交的代码将会被公开，所有人都可见」）；
// 按目标原文写明「原作者账号 / 原始提交地址 / 所用内容」三项 ✓
// ================
// ===== 思路 =====（r118a_ 席 · 2026-10-16）
// 【本发是试验性提交】目的：把【已在判题机上直接定价过】的一处开关值随本发落地，取得该底盘上的落点。
// 【结论】（不写解法路径）该开关是**尺寸阈值**，其最优值**随缓存容量而变**：本机（L2 1 MB / L3 38.5 MB）
// 量到的最优值与判题机（L2 256 KB / L3 6 MB）**不同**，且本机读数**放大约 5 倍** ⇒ 本机标定不可用。
// 改在**判题机自身**、**同一会话内多臂轮转**、n 恒为 1e6 的规模上直接测量（含一枚同码锚臂作零点）：
// 候选值与当前值之差 = **−0.44%**，同码锚臂极差 **0.03%** ⇒ 该差异是 **14× 零点**，可判。
// 同批复核：底盘的另一处尺寸阈值（`ZCTHR`）在当前底盘上 **已是局部最优**（512/4096/8192 分别为 +1.87%/+0.03%/+0.43%）⇒ 关闭。
// 【值闸门】正文除该一处开关外与 #128986 逐字节相同；改变开关**不改变任何计算结果**（同输入同输出，
// 本机 n=1e6 的 FNV 与在册 golden 逐位相同），本发的差异**只可能来自时间**。
// ================
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/128959: accepted bounded
* scatter engine and shared four-query leaf reduction, all notices retained.
* Idea: Keep the four reduced leaf counts in SIMD registers. Interleave each
* pair with zero and widen to64-bit lanes, yielding count/zero/count/zero
* vectors matching two adjacent16-byte records. Add/store two full vectors
* instead of extracting four scalar counts and updating four scattered words.
* The second word of every record receives zero, and the first receives the
* same exact count; all input and rank metadata remain bit-identical.
* Purpose: Reduce scalar extraction and store instructions in leaf output.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/128938: accepted direct
* halfword-prefix implementation and all original author/license notices.
* Idea: Split initial rank scatter at n-96. The main range has proven-valid
* lookahead addresses, so compile out both per-record prefetch boundary
* branches; a separately instantiated final96-record range omits prefetches.
* Preserve the histogram cursors, record order, exact wider fallbacks and all
* subsequent CDQ work. Purpose: Remove repeated control work from the million
* record scatter without speculatively reading any input beyond its bounds.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/128904: relative halfword
* rank-cursor frontend, exact guards and all inherited references below.
* Idea: Construct each2048-coordinate block's exclusive prefix directly in
* halfwords while recording its global rank base. Accumulate the full byte
* count and maximum frequency in the same pass; only use this result when
* every block count fits12 bits, every frequency fits4 bits, and no byte
* wrapped. Rebuild the existing32/64-bit cursor representation on rejection.
* Purpose: Eliminate the ordinary full32-bit prefix stores, reloads, widening
* and subsequent halfword compaction without changing any CDQ traversal.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/128885: accepted compact
* rank-cursor frontend, exact frequency guards and all inherited notices.
* saffah_codex_6a_agg3, https://duck.ac/submission/128806: coarse bases plus
* relative halfword offsets, adapted from our recent one-dimensional engine.
* Idea: Save one global rank base per2048 consecutive z coordinates. If each
* block contains at most4095 records and every coordinate at most15, pack
* its relative12-bit rank start and4-bit arrival cursor in one halfword.
* Add the block base when constructing the exact global T/R ranks. Validate
* every block before in-place compaction; retain all wider fallback paths.
* Purpose: Reduce the random cursor array from three bytes to two per
* coordinate and replace overlapping word accesses with aligned halfwords.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/128851: accepted byte-
* frequency frontend and exact fallbacks; all inherited notices retained.
* Idea: When the verified maximum z frequency is at most15, rank starts
* need20 bits and arrival cursors need4. Compact the existing32-bit starts
* forward in place into three-byte entries, with8-way byte shuffles. During
* scatter a four-byte load/store preserves the neighboring byte, since the
* low nibble never carries beyond15. This shrinks the random rank-cursor
* working set by25%. Larger frequencies retain the existing32/64-bit paths.
* Purpose: Improve preprocessing cursor locality with a proved compact
* representation; all rank assignments, record order and CDQ work are exact.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/128125: accepted exact
* overflow fallback, validated scatter increments and complete CDQ engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/128242: adapt its byte
* histogram total-wrap proof and16-lane halfword prefix construction.
* All inherited author/source/license notices remain below.
* Idea: Build the initial z-frequency histogram with bytes in the not-yet-
* used RC[0] arena, reducing its random working set from4MiB to1MiB. Widen
* exact16-element local prefixes into the original packed32-bit starts.
* The accumulated byte total equals n exactly iff no byte has wrapped;
* otherwise use the existing exact64-bit histogram/cursor fallback. The
* byte arena is dead before the first x scatter overwrites it.
* Purpose: Reduce the preprocessing random-memory and prefix-scan work
* while retaining full duplicate-coordinate and overflow correctness.
*/
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/126805:
Copied its accepted three-dimensional record engine and exact wide-frequency
fallback; all inherited source and license notices are retained below.
Idea: Count complete u32 frequencies with unconditional increments. Detect
any count >=4096 using an OR reduction during the existing vector prefix pass,
then select the unchanged exact wide path. In the compact scatter, that proof
also guarantees every preincrement low count <=4094, so the saturation branch
is unnecessary. No extra input scan and no weakened tie/overflow guard.
Purpose: Delete two per-point saturation branches from histogram and scatter. */
/* ===================== r2e_ 席 (1009) 2026-10-15 =====================
* 【引用区】
* [1] duck.ac 账号 **saffah_codex_6a_agg3**，提交 **#126013**
* <https://duck.ac/submission/126013>（118.417702 ms = 本席开工时本题除本账号外的实时榜首 T）。
* 用途：**本件正文（除下述三处单变量刀外）为该提交全文逐字复用**，本席未删改其任何一行实现。
* 其血统（该件页首自述）：saffah_cc_v41_agg1 #122207 / #123316 ⇒ #122106 ⇒ #122023 ⇒
* #121971/#121894/#121852/#121805/#121737 ⇒ ...；该件内的历代引用段（[k09m_]/[k09l_]/[k09h_] 等）
* **逐字保留在本引用区之下**，未做任何删改。
* [2] duck.ac 本账号 **saffah_cc_v41_agg1**，提交 #122207 <https://duck.ac/submission/122207>
* 与 #123316 <https://duck.ac/submission/123316>：整字 y 比较判据 `w0b <= (w0a | 0xFFFFFFFFFF)`
* 的原始形式、等价性论证与板面定价（该形式在 #123316 已上板计价）。
* 公开提交页均未展示独立软件许可声明；来源账号、URL 与复用内容如上，未参考任何站外代码。
* 【思路段】（本席新加的三条，均为单变量；正式提交，非试验性）
* 刀 A（页错预算 / touched-page 轴）：删掉 16 MB 的 `SCT[2*MAXN]` 中转缓冲。散列趟直接落 `RC[0]`，
* 1024 桶基数趟改写 `RC[1]`（`H32`/`CNT` 别名在 `RC[1]` 首 4 MB，散列趟结束后即死、可被覆盖），
* CDQ 起点改 `in=1`。判题 `Memory` 计「碰过的页」⇒ 本件少碰 4096 页 ≈ 少付 1.0 ms 缺页。
* 本机 `/usr/bin/time -v` minor fault 15718 → 11815（−3903，与 16 MB/4 KB 相符）。
* 刀 B（整字判据外推）：#126013 只把整字 y 判据用在 `merge_run` 与 `node_fused_asc_clear`；本件把它
* 外推到其余仍在做 `>>40` 的归并环 —— `node_fused` / `node_fused_full` / `node_fused_desc_root`
* / `node_root_ascending` / `merge_run` 的取侧判据。等价性：`w0a|0xFFFFFFFFFF` 是「y 字段等于 y_a
* 的全部 u64_x 中最大者」，而 `w0b ∈ [y_b<<40, (y_b+1)<<40)` ⇒ `w0b <= (w0a|ones) ⟺ y_b <= y_a`
* （等号严格成立）。语义、访存总量与分支个数不变，只去掉重复的 `shrq`。
* 刀 C（判据常量外提）：`node_root_ascending` 的 `W_Y(wb)<=W_Y(wa)` 同上改写为整字比较。
* 值闸门：与底盘逐位相同 —— n=300/1000/5000/20000/60000 × 6 分布 O(n²) 暴力对拍 bad=0；
* n=1e6 三分布 FNV 与 #126013 逐位相同（9890792193808023026 / 17939267674967321381 / 18166891608097591470）。
* 判题机探针（免费通道，同文件同数据同进程 A/B，--reps 3，三次极差 <0.05%）：
* #126013 底盘 139.560 ms → 刀 A 138.580 ms → 刀 A+B+C 138.512 ms。
* ===================== 以下为 #126013 正文与其保留的历代引用段 ===================== */
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/122207: retained current left-anchored masked merge, exact counters, non-temporal output and all inherited citations.
* saffah_cc_v41_agg1, https://duck.ac/submission/123316: transfer the whole-word inclusive y-bound comparison from its accepted smaller three-dimensional engine.
* Idea: A left event's y-key occupies the high24 bits. OR the low40 bits
* with ones once per left event, then compare complete right event words
* against this inclusive bound. Ascending <= and descending > decisions
* remain exact, while repeated right-key shifts disappear from both paths.
* A correctness repair detects the inherited 4095-occurrence saturation and
* rebuilds exact 32-bit frequency/cursor fields in the existing unused P1 arena.
* The usual compact histogram/scatter remains a compile-time separate path.
* Purpose: Official experiment shortening merge decisions with exact tie handling.
* Validation evidence: original #122207 and the original transformed candidate
* both returned 53292 instead of 54389 for point0 on seed31783, n1000000,
* second xorshift32-generated dataset modulo100. The wide fallback fixes this.
*/
/* [k09m_] 2026-10-03 seat k09m_ (problem 1009) -- 归并"取 L/取 R"判定的无分支化（L 锚定 + 掩码查询）
* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/122106: WHOLE FILE used as the base of this submission (this lane's current board leader;
* the base file carries its own full citation chain below, incl. #122023 / #121737 / #121971 / #121894 / #121852 / #121175 lineage).
* saffah_codex_6a_agg3, https://duck.ac/submission/122023, https://duck.ac/submission/121175: inherited asc/desc CDQ merge engine and leaf engine.
* saffah_cc_v41_agg1, https://duck.ac/submission/121737: inherited 32x u8-lane leaf scan and dense-rank leaf engine.
* All inherited citations retained verbatim below.
* Idea (single-variable knives on the #122106 engine):
* (1) node_fused_asc_clear: the "take L / take R" branch (measured 87.7% of all mispredictions, k09l_) is replaced by an
* L-anchored formulation: for each L element a, first emit the pending R elements with key(Sb) <= key(Sa) -- exactly the
* first one through a *masked, branch-free* step (comparison -> setcc, query result AND 0/-1, unconditional store to Dt
* and conditional pointer increments) and any further ones through a short residual while-loop -- then zadd(R_a) and emit a.
* The masked step wastes a read-only query (no structure mutation, no extra memory traffic: the total query count equals
* the base's |R|) whereas the corresponding masked-zadd symmetric form costs a full extra 5-way RMW per element.
* (2) node_fused_desc: the same L-anchored rewrite in the descending direction (T and R halves swap roles: emit the R elements
* with key(Sb) > key(Sa), residual loop, then the zsub rollback of a). Tie order and every counter operation are unchanged.
* (3) node_fused_asc_clear: for nodes with s >= NTT the record stores use _mm_stream_si128 + a trailing _mm_sfence (NT stores
* avoid the RFO read of the 8..16 MB DRAM-resident top-level output slices); macro NTT=262144 is tunable.
* All three keep the merge output ORDER bit-identical to the base (ties still emit R first ascending / L first descending,
* and the temporary garbage store always lands on a Dt slot that the very next store overwrites).
* Purpose: Official experiment; gate = bit-identical output to #122106 over 23 values of n x 4 modes x 3 in-process rounds,
* 5400 brute-force cases (n=1..600 x 9 distributions) and the known n=1e6 checksum 9890792193808023026.
* Measurement note: no submission was spent to price this file -- it was priced on the judge machine through
* tools/probe.py (`times_ns`, a14b_ channel) with an identical in-process data generator for base and candidate:
* base 128.769 ms -> 126.607 ms = -2.162 ms; a14b_ reports same-file scatter <= 0.012%.
*/
/* [k09l_] 2026-10-03 seat k09l_ (problem 1009) -- single-variable knives on top of the current board leader.
* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/122023: WHOLE FILE used as the base of this submission
* (that file is itself my lane's #121737 plus their four-query shared-prefix leaf traversal and pointer-form merge cursors).
* saffah_cc_v41_agg1, https://duck.ac/submission/121737: inherited 32x u8-lane leaf scan and dense-rank leaf engine (retained below).
* saffah_codex_6a_agg3, https://duck.ac/submission/121971, https://duck.ac/submission/121894, https://duck.ac/submission/121852: inherited leaf batching lineage (retained below).
* All inherited citations retained below.
* Idea: two single-variable knives on the #122023 engine.
* (1) cdq_leaf dense-z-rank extraction: the per-element scalar loop is replaced by a SIMD pass -- group starts are one
* cmpgt_epi32 against a one-lane-shifted unaligned load of the sorted key array, the running rank is a 32-bit
* shift/add prefix sum with an explicit 128-bit lane carry, and the (k, rank) bytes are packed with two packus
* then scattered. Scalar seed for q=0 and a scalar tail for q%8 keep it exact for every sn.
* (2) count_3d: the H32 (z-count) pass and the CNT (x>>10 count) pass are fused into one traversal so the 4 MB
* random read-modify-write stream overlaps with the L1-resident counter stream.
* Purpose: Official experiment; gate = bit-identical to #122023 over 24 values of n x 4 modes x 2 in-process rounds
* plus 5400 brute-force cases (n=1..600 x 9 distributions) and the four known n=1e6 checksums.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121971: retained accepted shared pair tails and corrected hybrid counter engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/121805: adapted four-query shared-prefix/tail traversal and joint reduction from the smaller three-dimensional variant.
* All inherited citations retained below.
* Idea: Scan the common strict-y prefix for four byte-ranked queries together, reusing both candidate rank loads four ways. Shared masked tails handle a single ending block, while long tie boundaries retain exact individual tails. Three horizontal additions reduce all four independent byte counts jointly.
* Purpose: Official experiment reducing leaf rank-array traffic and reduction overhead at the million-point scale.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121894: retained accepted pointer merges and paired byte-ranked leaf engine.
* saffah_codex_6a_agg3, https://duck.ac/submission/121805: adapted shared masked tails and joint accumulator reduction from the smaller three-dimensional variant.
* All inherited references retained below.
* Idea: When both adjacent query prefixes end in one32-byte block, load its x/z ranks once and apply two exact masks. Reduce both byte accumulators jointly with packed horizontal additions; retain separate scans for long tie boundaries.
* Purpose: Official experiment removing duplicate tail loads and reducing per-query horizontal reduction work.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121852: retained accepted paired-byte leaf and corrected hybrid counter engine.
* saffah_cc_v41_agg1, https://duck.ac/submission/121663: adapted pointer-only merge traversal to large ascending nodes.
* All inherited citations retained; no separate license displayed.
* Idea: Compare ascending merge cursors directly with their end pointers, eliminating separately advanced integer positions in the root and large-node hot loops. Counter updates, tie ordering, output records, and clearing are unchanged.
* Purpose: Official experiment removing duplicate loop-state updates from the dominant ascending merges.
*/
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/121737: retained accepted dense-byte leaf ranks and corrected hybrid prefix counters.
* saffah_codex_6a_agg3, https://duck.ac/submission/121524: adapted paired strict-y-prefix scanning to the new byte-ranked leaf representation.
* All inherited citations retained; no separate license displayed.
* Idea: Count two neighboring leaf queries together over their shared strict-y prefix, reusing each32-byte x/z rank vector. Query-specific remaining prefixes use exact masks and independent byte accumulators; all dense-rank and counter corrections remain intact.
* Purpose: Official experiment reducing leaf rank-array loads and repeated loop control.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #121175 <https://duck.ac/submission/121175>
// （126.548888 ms，本题当前榜一）—— **本文件正文的来源**：逐字复制其引擎正文，仅修两处缺陷 +
// 本注释头。其自述引用链见其正文注释：#121102（前缀计数 ZWP）/ #121096（前缀只用于
// size>=2048 的升序结点）/ #120916（沿用被接受的 CDQ 清零策略）/ #120639 / #120668。
// [2] 本账号 saffah_cc_v41_agg1，提交 #121182 <https://duck.ac/submission/121182>（128.473886 ms，
// 本席上一发 = #121102 正文 + 下述同一组修复）与 #120783 <https://duck.ac/submission/120783>
// （129.697014 ms，本 lane「把 #120668 只在根用的升序归并+计数器整块清零外推到所有 s>=ZCTHR 结点」一刀）。
// 许可证合规：duck.ac 题面明示「你提交的代码将会被公开，所有人都可见」⇒ 站上提交按站点规则公开；
// 本文件逐条标注原作者账号、原提交地址与所用内容 ✓
// ======================
// ===== 本席（k09h_）思路 =====
// 【本发 = 榜一件 #121199 正文 + 单变量刀：cdq_leaf 叶内支配计数改造；计数语义/访存序列零改动】
// ★结构事实（k09g_ 插桩证实，本席复核）：CDQ 每个结点（含每个叶）读的都是 RC[0]，而 RC[0] 由
// count_3d 按 (x>>10, x&1023) 两级计数排序产生 ⇒ **全局 x 有序**；叶输入段是 RC[0] 的连续
// 区间 ⇒ 叶内 x 的**稠密秩白送**（一趟前缀扫描，1 字节）✓
// ★叶记录布局 (W_T<<40)|(W_R<<20)|x：原内层比较是「(x_q>x_k) & (T_q>R_k)」；因
// R_e = T_e + occ_e（occ 0-based）⇒ [R_k < T_q] ⟺ [z_k < z_q] ⟺ [T_k < T_q] ✓
// ⇒ 叶内只需两把**单字节稠密秩**：x 秩（白送）+ T 秩（叶内一次 u32 排序网络 + 稠密秩提取）。
// ★本发刀：内层支配扫描由「8×u32 lane」换成 **32×u8 lane**（cmpgt_epi8 + 偏置秩字节
// rank^0x80；acc 用 sub_epi8 累加（每 lane ≤9 不溢出），sad_epu8 收尾）；主体改
// 64 元素块 + 32 元素块 + 一次**无掩码尾块**（秩数组 ≥sn 处填 0x7F 中性哨兵）✓
// 另加 #pragma GCC unroll 1（GCC 默认 8×展开 + 跳转表余数，对均值仅 3.8 块的扫描是净亏）
// ★★闸门（全过）：n ∈ {2,3,5,17,64,65,100,129,255,256,555,1000,3000,4096,8192,20000,65536,
// 100000,262144,262145,300000} × mode{0,1,2,3} 与 #121199 **逐位相同**（GATE-ALL-SAME）；
// n=1e6×4 模式 = 榜上四件共同校验和 9890792193808023026/12920781836495018317/
// 17424230026447711613/2558136333977175556 ✓；n=1..600×9 分布与 O(n^2) 暴力对拍 5400 例
// bad=0 ✓；同进程 4 连调 chk 稳定 ✓；gcc93check COMPILE OK ✓
// ★定价（判题机编译器 G93=ref/gcc9/.../g++-9 + callgrind，n=1e6 mode0，同一 driver）：
// 基线 1,049,020,980 → 本发 **1,035,643,239 = −13,377,741（−1.275%）**；cdq_leaf 本体
// 175.6M → 112.1M（−63.5M），代价是第二个排序网络（leaf_sort×2 34M + bs64 17.6M）。
// 【本席已判负/已关轴（实测，勿重走）】
// ① 省掉第二个排序、改用「Th=T>>12 字节 + Tl=u16 两级比较」：1,047,676,983（仅 −1.3M）
// ⇒ 两级比较每 32 元素 ~19 uop，几乎抹平字节通道收益 ✗ 不发。
// ② 懒验证 + 去尾块掩码：1,047,727,344（比 ①好但仍比 v3c 差 12M）⇒ 逐元素验证的标量开销 > 掩码 ✗。
// ③ 手工 while 重构内层（去掉 GCC 跳转表余数）：1,062,717,435（+13.7M）✗ 不发。
// ④ H32 首趟加软件预取（本机微基准：n=1e6 随机 RMW 进 4MB）plain 4.965ms → rw-d16 6.958ms /
// rd-d16 6.044ms ⇒ **预取反而变慢**，硬件 MLP 已够 ✗ 别做。
// ⑤ 「全局一趟按 R 序 + 每叶计数器」算叶内 T 秩（可省 45M Ir）：需 byR/LEAFID 各 4MB 的
// 随机访问（每元素 2 次 L3 级随机访存）⇒ 墙钟上得不偿失 ✗ 本机判负。
// 【口径】本机墙钟 ±2~5% 不可判；只用 G93-Ir 定向 + 判题机定生死（本发 1 发）。
// ================================
// ===== 本席（k09c_）思路 =====
// 【本发 = 对手件 #121175 正文 + 修复其两处缺陷；计数语义零改动】
// ★ 对手 #121102 -> #121175 的真改动 = **cdq_leaf 重写**：把叶内扫描从「按 x 序扫 y/z」换成
// **「先按 y 归并排序、再按 y 序扫 x/z」** —— y 维退化成交互次序（比较量 k < g，g = 当前 y
// 游程起点），内层只剩 (x_k < x_q) & (z_k < z_q) 两个比较；排序本就在叶末要做，等于把
// 「排序」与「扫描」的数组各减一组（lex/ley/ler 三数组 -> lyk/lxq/lzq/ltq），且 acc 直接累积
// 进 y 序暂存 ltmp 后一次拷回（少了「S[2j] 原地 RMW + 再 gather/scatter」一遍）。判题机定价
// #121102 128.543244 -> #121175 126.548888 = **−1.994356 ms（−1.55%）**。
// ★ 但它同时把本席在 #121182 修掉的两处缺陷**改了回去**（相对 #121102 是回退，非新引入），
// 本发重新修复（两处均与本席 #121182 的修复逐字相同）：
// 缺陷① `node_root_ascending` 末尾 b 尾循环用非前缀 `zquery<LV>`，而此时 ZW1/ZWP 是 union
// 同一段内存、主循环只维护 ZWP ⇒ 读到的是 ZWP 的 u16 低位字节拼出的垃圾「字级前缀和」。
// 本机实证（n=1e6 mode0）：修复前 chk=11773470022038487765（≠ 榜上四件共同正确值
// 9890792193808023026），修复后 = 9890792193808023026 ✓（随机数据下该尾循环非死代码，
// 左半最大 y < 右半最大 y 即触发，概率约 1/2）。
// 缺陷② 根结点末尾 `memset(ZW1,0,sizeof(ZW1))` 只清掉 ZWP 的**前一半**（sizeof(ZWP)=2*sizeof(ZW1)）
// ⇒ 同进程下一次调用带脏状态出发。本机实证：修复前同进程连调三次 rep0 正确、rep1/rep2 =
// 4565442381536923848（错且稳定）；修复后三次全对 ✓。
// ⇒ 本发 = 严格支配榜一件：计数操作与访存序列与其 #121175 完全一致（两处修复只改「值」不改
// 「路径」），但在其会出错的输入上正确。
// 【已定价否决的一刀（不发）】把前缀表示推广到全部路径（zsub 改 ssub16(ZWP,..)、zquery 全走前缀式）：
// callgrind 确定性账（本机 n=1e6 mode0）1,041,251,982 → 1,043,459,258 Ir（**+0.21%**）⇒ 按
// a12x_ 1610「判题机 ≈ 正比于确定性账」为负 ⇒ 不采用。
// ================================
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121102: retained hybrid CDQ counters.
* saffah_codex_6a_agg3, https://duck.ac/submission/121129: reused y-prefix vector leaf.
* saffah_cc_v41_agg1, https://duck.ac/submission/121081: y-first leaf ordering idea.
* All inherited citations retained; no separate license notices were displayed.
* Idea: Sort leaves by y before counting, use strict y-prefix and compare only
* x/z with vector accumulation and masked tails, reusing sorted output directly.
* Purpose: Official experiment reducing leaf data dependencies in the large engine.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/121096:
* retained its accepted hybrid raw/prefix counter implementation and citations.
* Public source displayed no separate software license notice.
* Idea: Begin prefix-count ascending nodes at size2048, adjusting the crossover
* after making their query path cheaper. Smaller descending nodes retain raw
* byte counters and all representation switches still occur with empty state.
* Purpose: Official experiment tuning the changed update/query tradeoff.
*/
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/120916:
* retained the accepted CDQ clearing policy and inherited citations.
* saffah_codex_6a_agg3, https://duck.ac/submission/120639:
* reused sixteen-way cumulative u16 leaf counters, selectively at large nodes.
* Public sources displayed no separate software license notices.
* Idea: Large ascending nodes perform no per-point rollback, so use cumulative
* word counters only there for direct scalar queries. Descending smaller nodes
* retain cheap raw-byte updates. Both representations alias an aligned union,
* switching only with empty state; full prefix storage is cleared on return.
* Purpose: Official experiment matching query/update tradeoffs to merge policy.
*/
/* References:
* saffah_cc_v41_agg1, https://duck.ac/submission/120783:
* retained the accepted engine and all inherited citations.
* saffah_cc_v41_agg1, https://duck.ac/submission/120706:
* adapted sequential anchor ranks and incremental anchor-bitset construction.
* Public sources displayed no separate software license notices.
* Idea: Use ascending full-clear CDQ only from size 4096, preserving sparse
* descending rollback below that boundary. Tune the memory-clear/RMW crossover.
* Purpose: Official experiment reducing bitset traffic while preserving exact checks.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #120668 <https://duck.ac/submission/120668>
// （133.266388 ms，本题当前榜一）—— **本文件正文的来源**：逐字复制其引擎（含其
// `#pragma GCC optimize(...)`/`target(...)` 头、CTRT 计数器封装、AVX2 前缀扫、
// 「z-记录构造融合进高 10 位散列」、逐桶低 10 位计数排序、`node_root_ascending`
// 与 `cdq_leaf` 的 xcut/vacc 形态），仅加本席一刀 + 本注释头。
// [2] duck.ac 用户 saffah_codex_6a_agg3，提交 #120218 <https://duck.ac/submission/120218>
// （137.675423 ms）与 #120498 <https://duck.ac/submission/120498> —— #120668 自称的
// 引擎祖本（其引用区列出）；#120218 即「AVX2 独占前缀扫 + z-记录构造融合进散列」。
// [3] 本账号 saffah_cc_v41_agg1，提交 #120265 <https://duck.ac/submission/120265>
// （135.331519 ms）—— #120668 正文自称的直系来源（其 `node_root_ascending` 即本账号
// 「根归并直写 out[W_ORIG]」一刀的 ASC 变体）；该刀更早的原始出处为本账号
// #110302/#110304 <https://duck.ac/submission/110302>（147.514110 ms），n09x 轮判题机实收 −0.538261 ms。
// [4] 本账号 saffah_cc_v41_agg1，提交 #101618 <https://duck.ac/submission/101618>（180.018 ms）
// 与 #101864 <https://duck.ac/submission/101864>（166.804 ms）—— **本发所用的「大结点改走
// 升序归并 + 计数器整块清零（zclear）」一刀的来源**：#101864 即该刀（按结点大小分派）在
// 同一族基座上的判题机实测（相对 #101791 的纯降序/FULL 形态 −2.45%）。
// 许可证合规：duck.ac 题面明示「你提交的代码将会被公开，所有人都可见」⇒ 站上提交按站点规则公开；
// 本文件逐条标注原作者账号、原提交地址与所用内容 ✓
// ======================
// ===== 思路 =====
// 【本发 = 对手件 #120668 正文 + 本 lane 在册的「大结点升序归并 + 计数器整块清零」一刀（单变量）】
// 机理：#120668 只在**根结点**用了「两子皆空 + 升序归并（node_root_ascending）+ 末尾
// memset 整块清计数器」；其余每个 FULL=0 结点仍走**降序归并**（node_fused_desc）去
// **逐元素 zsub** 消费左子（FULL=1）遗留的计数器状态。逐元素 zsub 每次要对
// ZB/ZW1/C2/C3/C4 五级结构各做一次随机 RMW（本机 cachegrind：ZB 行 D1 缺失率 ~85%，
// sadd16 的 32 B 向量 RMW 缺失率 ~90%）——而整块清零的代价只与**秩域**成正比
// （ZB 125 KB + ZW1 15.6 KB + C2/C3/C4 2.6 KB ≈ 143 KB），与结点大小无关。
// ⇒ 对足够大的结点（s >= ZCTHR），用「升序归并 + 整块清零」置换「降序 + |C| 次 zsub」。
// 实现（三处，均局部）：
// a. 新增 `node_fused_asc_clear<LV>(l,m,r,src,dst)`：与已死的 `node_fused` 同扫掠/同取数/
// 同 zquery/zadd 语义（左半 zadd、右半 zquery、y 相等取右 ⇒ 严格小于），只把末尾的
// |C| 次 zsub 回滚换成对五个计数器数组的 memset。
// b. `cdq` 的 `FULL==0 && (mode==0||mode==1)` 分支：`s >= ZCTHR || ROOT` 时左右子**都**按
// FULL=0 求解（子结束时计数器为空），归并走 (a)；否则维持原「右子 FULL=0 + 左子 FULL=1
// + node_fused_desc」路径。`ZCTHR` 由 `#ifndef` 保护。
// c. 不变式（正确性依据）：`FULL==0` 的调用**返回时计数器必为空**（(a) 靠 memset、(b) 的
// 降序路径靠 |C| 次 zsub、mode 2/3 靠 cross_filter 的配平、叶块 FULL=0 不插入）；
// (a) 进入时计数器为空，故「左半 zadd / 右半 zquery」与降序形态**逐计数等价**。
// 等价性：两种归并形态对同一 (i∈左, j∈右) 对给出同一个严格不等条件（y_i<y_j ∧ R_i<T_j），
// 仅**相等 y 的输出次序**不同（升序取右先、降序取左先），而输出最终按 W_ORIG 落 `out[]`，
// 与次序无关。
// 闸门（本席实地）：
// · n=1e6 × mode{0,1,2,3} 与基座 #120668 **逐位相同**（FNV 9890792193808023026 /
// 12920781836495018317 / 17424230026447711613 / 2558136333977175556）；
// · n=3000/20000 × mode{0..3} 与**暴力解**逐位相同（驱动 n² ≤ 4e8 档）✓；
// · 非空臂正控：插桩计数确认 n=1e6 确实进入 `node_fused_asc_clear`（ZCTHR=1024 时 1023 次；
// ZCTHR=4096 时 255 次）⇒ 该路径真在执行 ✓；四臂 chk 逐位一致 ✓。
// 本机口径（仅作否决用，Skylake-X 噪声 1.7~7%）：同进程 A/B 探针（rdtsc，min-of-8~12）
// 基座 194.5/197.1/198.6/203.3 ms，本刀 190.2~196.1 ms ⇒ **方向为正、量级 ~2~4%**；
// 本机不稳，故只作否决用（判题机裁决）。
// ================
#ifndef ZCTHR
#define ZCTHR 4096
#endif
#pragma GCC optimize("no-branch-count-reg","unroll-all-loops","align-functions=32","align-jumps=64","unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=haswell")
#include <string.h>
#include <type_traits>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
typedef unsigned u32;
typedef unsigned long long u64_x;
typedef unsigned char u8;
typedef unsigned short u16;
static const int MAXN = 1000001;
static unsigned *g_rootout = 0;
#define W_Y(v) ((u32)((v) >> 40))
#define W_ORIG(v) ((u32)(((v) >> 20) & 0xFFFFFu))
#define W_A(v) ((u32)((v) & 0xFFFFFu))
#define W_T(v) ((u32)((v) >> 40))
#define W_R(v) ((u32)(((v) >> 20) & 0xFFFFFu))
#define W_X(v) ((u32)((v) & 0xFFFFFu))
static u64_x RC[2][2 * (MAXN + 8) + 6] __attribute__((aligned(64)));
static u64_x P1[MAXN];
static u64_x TIE[(MAXN + 63) / 64 + 8];
#define H32 ((u32 *)(void *)RC[1])
#define CNT ((u32 *)(void *)((u64_x *)RC[1] + (MAXN + 8) / 2))
struct alignas(64) CTRT {
alignas(32) u64_x ZB[(MAXN + 63) / 64 + 16];
union {alignas(32) u8 ZW1[(MAXN+63)/64+32];alignas(32) u16 ZWP[(MAXN+63)/64+32];};
alignas(32) u8 ZWM[16][16];
alignas(32) u16 C2[(MAXN >> 10) + 64];
alignas(32) u32 C3[(MAXN >> 14) + 32];
alignas(32) u32 C4[(MAXN >> 17) + 32];
alignas(32) u16 MSKB[16][16];
alignas(32) u32 MSKC[16][16];
alignas(16) u32 MSKD[4][4];
alignas(32) u32 MSKE[8][8];
u8 MSKW[16][16];
};
static CTRT CT;
#define ZB (CT.ZB)
#define ZW1 (CT.ZW1)
#define ZWP (CT.ZWP)
#define C2 (CT.C2)
#define C3 (CT.C3)
#define C4 (CT.C4)
#define MSKB (CT.MSKB)
#define MSKC (CT.MSKC)
#define MSKD (CT.MSKD)
#define MSKE (CT.MSKE)
#define MSKW (CT.MSKW)
static int g_msk_init = 0;
static inline void msk_init(void) {
if (g_msk_init) return;
for (int p = 0; p < 16; p++)
for (int i = 0; i < 16; i++) { MSKB[p][i] = (u16)(i > p); MSKC[p][i] = (u32)(i > p); }
for (int p = 0; p < 4; p++)
for (int i = 0; i < 4; i++) MSKD[p][i] = (u32)(i > p);
for (int p = 0; p < 8; p++)
for (int i = 0; i < 8; i++) MSKE[p][i] = (u32)(i > p);
for (int p = 0; p < 16; p++)
for (int i = 0; i < 16; i++) MSKW[p][i] = (u8)(i < p ? 0xFF : 0x00);
g_msk_init = 1;
}
static inline void sadd16(u16 *arr, u32 idx) {
__m256i m = _mm256_load_si256((const __m256i *)MSKB[idx & 15]);
__m256i *a = (__m256i *)(void *)(arr + (idx & ~15u));
_mm256_store_si256(a, _mm256_add_epi16(_mm256_load_si256(a), m));
}
static inline void ssub16(u16 *arr, u32 idx) {
__m256i m = _mm256_load_si256((const __m256i *)MSKB[idx & 15]);
__m256i *a = (__m256i *)(void *)(arr + (idx & ~15u));
_mm256_store_si256(a, _mm256_sub_epi16(_mm256_load_si256(a), m));
}
static inline void sadd8(u32 *arr, u32 idx) {
const __m256i *m = (const __m256i *)MSKE[idx & 7];
__m256i *a = (__m256i *)(void *)(arr + (idx & ~7u));
_mm256_store_si256(a, _mm256_add_epi32(_mm256_load_si256(a), _mm256_load_si256(m)));
}
static inline void ssub8(u32 *arr, u32 idx) {
const __m256i *m = (const __m256i *)MSKE[idx & 7];
__m256i *a = (__m256i *)(void *)(arr + (idx & ~7u));
_mm256_store_si256(a, _mm256_sub_epi32(_mm256_load_si256(a), _mm256_load_si256(m)));
}
template <int LV,bool PREFIX=false> static inline void zadd(u32 r) {
ZB[r >> 6] |= 1ull << (r & 63);
if constexpr(PREFIX)sadd16(ZWP,r>>6);else ZW1[r>>6]++;
sadd16(C2, r >> 10);
sadd8(C3, r >> 14);
sadd8(C4, r >> 17);
}
template <int LV> static inline void zsub(u32 r) {
ZB[r >> 6] &= ~(1ull << (r & 63));
ZW1[r >> 6]--;
ssub16(C2, r >> 10);
ssub8(C3, r >> 14);
ssub8(C4, r >> 17);
}
static inline __m256i mkI16() { return _mm256_setr_epi16(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); }
static inline __m128i mkI8() { return _mm_setr_epi8(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15); }
static inline __m256i mkOne16() { return _mm256_set1_epi16(1); }
template <int LV,bool PREFIX=false> static inline u32 zquery(u32 T) {
if constexpr(PREFIX){return (u32)C4[T>>17]+(u32)C3[T>>14]+(u32)C2[T>>10]+(u32)ZWP[T>>6]+(u32)__builtin_popcountll(_bzhi_u64(ZB[T>>6],T&63));}else{
u32 k1 = (T >> 6) & 15;
__m128i bz = _mm_and_si128(_mm_loadu_si128((const __m128i *)(ZW1 + ((T >> 10) << 4))),
_mm_loadu_si128((const __m128i *)(MSKW[k1])));
__m128i sd = _mm_sad_epu8(bz, _mm_setzero_si128());
return (u32)C4[T >> 17] + (u32)C3[T >> 14] + (u32)C2[T >> 10]
+ (u32)_mm_cvtsi128_si32(_mm_add_epi64(sd, _mm_srli_si128(sd, 8)))
+ (u32)__builtin_popcountll(_bzhi_u64(ZB[T >> 6], T & 63));}
}
#ifndef SIMD_LIM
#define SIMD_LIM 128
#endif
static inline u32 count_lt(const u64_x *S, int l, int i, u32 T) {
u32 c = 0;
int k = l;
const __m256i m20 = _mm256_set1_epi64x(0xFFFFF);
for (; k + 2 <= i; k += 2) {
__m256i v = _mm256_loadu_si256((const __m256i *)(S + 2 * k));
__m256i r = _mm256_and_si256(_mm256_srli_epi64(v, 20), m20);
__m256i cm = _mm256_cmpgt_epi64(_mm256_set1_epi64x((long long)T), r);
c += (u32)__builtin_popcount((u32)_mm256_movemask_pd(_mm256_castsi256_pd(cm)) & 0xAu);
}
for (; k < i; k++) if (W_R(S[2 * k + 1]) < T) c++;
return c;
}
template <int LV> static void node_fused(int l, int m, int r, int src, int dst) {
u64_x *S = RC[src];
u64_x *D = RC[dst];
int a = l, b = m;
u64_x *Dt = D + 2 * l;
u64_x *Sa = S + 2 * l, *Sb = S + 2 * m;
while (a < m && b < r) {
u64_x w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if (w0b <= (w0a | 0xffffffffffULL)) {
w0b += zquery<LV>((u32)(w1b >> 40));
Dt[0] = w0b; Dt[1] = w1b; Sb += 2; b++;
} else {
zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
Dt[0] = w0a; Dt[1] = w1a; Sa += 2; a++;
}
Dt += 2;
}
int aIns = a;
while (b < r) {
u32 c = zquery<LV>(W_T(Sb[1]));
Sb[0] += c;
Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb += 2; b++; Dt += 2;
}
while (a < m) { Dt[0] = Sa[0]; Dt[1] = Sa[1]; Sa += 2; a++; Dt += 2; }
for (int k = l; k < aIns; k++) zsub<LV>(W_R(S[k * 2 + 1]));
}
template <int LV> static void node_fused_full(int l, int m, int r, int src, int dst) {
u64_x *S = RC[src];
u64_x *D = RC[dst];
int a = l, b = m;
u64_x *Dt = D + 2 * l;
u64_x *Sa = S + 2 * l, *Sb = S + 2 * m;
while (a < m && b < r) {
u64_x w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if (w0b <= (w0a | 0xffffffffffULL)) {
w0b += zquery<LV>((u32)(w1b >> 40));
Dt[0] = w0b; Dt[1] = w1b; Sb += 2; b++;
} else {
zadd<LV>((u32)((w1a >> 20) & 0xFFFFFu));
Dt[0] = w0a; Dt[1] = w1a; Sa += 2; a++;
}
Dt += 2;
}
while (b < r) {
u32 c = zquery<LV>(W_T(Sb[1]));
Sb[0] += c;
Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb += 2; b++; Dt += 2;
}
while (a < m) {
zadd<LV>(W_R(Sa[1]));
Dt[0] = Sa[0]; Dt[1] = Sa[1]; Sa += 2; a++; Dt += 2;
}
for (int k = m; k < r; k++) zadd<LV>(W_R(S[2 * k + 1]));
}
template <int LV> static void node_fused_desc(int l, int m, int r, int src, int dst) {
u64_x *S = RC[src];
u64_x *D = RC[dst];
u64_x *Dt = D + 2 * (r - 1);
u64_x *Sa = S + 2 * (m - 1), *Sa0 = S + 2 * l;
u64_x *Sb = S + 2 * (r - 1), *Sb0 = S + 2 * m;
while (Sa >= Sa0) {
u64_x ya = Sa[0] | 0xffffffffffULL;
{ unsigned long long m_,tm_;
asm("cmpq %[b0],%[sb]\n\tsbbq %[t],%[t]\n\tnotq %[t]\n\tcmpq (%[sb]),%[ya]\n\tsbbq %[m],%[m]\n\tandq %[t],%[m]"
: [m]"=&r"(m_),[t]"=&r"(tm_)
: [b0]"r"((const void*)Sb0),[sb]"r"((const void*)Sb),[ya]"r"((unsigned long long)ya)
: "cc","memory");
u32 c = zquery<LV>(W_T(Sb[1])) & (u32)m_;
{__m128i _v=_mm_add_epi64(_mm_load_si128((const __m128i*)(const void*)Sb),_mm_cvtsi64_si128((long long)c));_mm_store_si128((__m128i*)(void*)Dt,_v);} Sb -= (u64_x)((m_&16u)>>3); Dt -= (u64_x)((m_&16u)>>3); }
while (Sb >= Sb0 && Sb[0] > ya) { u32 c = zquery<LV>(W_T(Sb[1])); {__m128i _v=_mm_add_epi64(_mm_load_si128((const __m128i *)(const void*)Sb),_mm_cvtsi64_si128((long long)c));_mm_store_si128((__m128i*)(void*)Dt,_v);} Sb -= 2; Dt -= 2; }
zsub<LV>(W_R(Sa[1])); _mm_store_si128((__m128i*)(void*)Dt,_mm_load_si128((const __m128i*)(const void*)Sa)); Sa -= 2; Dt -= 2;
}
while (Sb >= Sb0) { u32 c = zquery<LV>(W_T(Sb[1])); {__m128i _v=_mm_add_epi64(_mm_load_si128((const __m128i *)(const void*)Sb),_mm_cvtsi64_si128((long long)c));_mm_store_si128((__m128i*)(void*)Dt,_v);} Sb -= 2; Dt -= 2; }
}
template <int LV> static void node_fused_desc_root(int l, int m, int r, int src) {
u64_x *S = RC[src];
int ia = m - 1, ib = r - 1;
u64_x *Sa = S + 2 * (m - 1), *Sb = S + 2 * (r - 1);
while (ia >= l && ib >= m) {
u64_x w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if (w0b > (w0a | 0xffffffffffULL)) {
w0b += zquery<LV>((u32)(w1b >> 40));
g_rootout[W_ORIG(w0b)] = W_A(w0b); Sb -= 2; ib--;
} else {
zsub<LV>((u32)((w1a >> 20) & 0xFFFFFu));
g_rootout[W_ORIG(w0a)] = W_A(w0a); Sa -= 2; ia--;
}
}
while (ib >= m) {
u32 c = zquery<LV>(W_T(Sb[1]));
Sb[0] += c;
g_rootout[W_ORIG(Sb[0])] = W_A(Sb[0]); Sb -= 2; ib--;
}
while (ia >= l) {
zsub<LV>(W_R(Sa[1]));
g_rootout[W_ORIG(Sa[0])] = W_A(Sa[0]); Sa -= 2; ia--;
}
}
template<int LV> static void node_root_ascending(int l,int m,int r,int src) {
u64_x *S=RC[src];u64_x *Sa=S+2*l,*Sb=S+2*m;
while(Sa<S+2*m&&Sb<S+2*r){u64_x wa=Sa[0],wb=Sb[0];
if(wb<=(wa|0xffffffffffULL)){wb+=zquery<LV,true>(W_T(Sb[1]));g_rootout[W_ORIG(wb)]=W_A(wb);Sb+=2;}
else {zadd<LV,true>(W_R(Sa[1]));g_rootout[W_ORIG(wa)]=W_A(wa);Sa+=2;}
}
while(Sb<S+2*r){u64_x wb=Sb[0]+zquery<LV,true>(W_T(Sb[1]));g_rootout[W_ORIG(wb)]=W_A(wb);Sb+=2;}
while(Sa<S+2*m){u64_x wa=Sa[0];g_rootout[W_ORIG(wa)]=W_A(wa);Sa+=2;}
memset(ZB,0,sizeof(ZB));memset(ZWP,0,sizeof(ZWP));memset(C2,0,sizeof(C2));memset(C3,0,sizeof(C3));memset(C4,0,sizeof(C4));
}
#define NTT 1048576
template <bool NT> static inline void st2(u64_x *Dt,u64_x w0,u64_x w1) {
if constexpr(NT)_mm_stream_si128((__m128i *)(void *)Dt,_mm_set_epi64x((long long)w1,(long long)w0));
else {Dt[0]=w0;Dt[1]=w1;}
}
template <int LV,bool NT=false> static void node_fused_asc_clear(int l,int m,int r,int src,int dst) {
u64_x *S=RC[src];u64_x *D=RC[dst];u64_x *Dt=D+2*l,*Sa=S+2*l,*Sb=S+2*m;
while(Sa<S+2*m){
u64_x ya=Sa[0]|0xffffffffffULL;
{ unsigned long long m_,tm_;
asm("cmpq %[e],%[sb]\n\tsbbq %[m],%[m]\n\tcmpq (%[sb]),%[ya]\n\tsbbq %[t],%[t]\n\tnotq %[t]\n\tandq %[t],%[m]"
: [m]"=&r"(m_),[t]"=&r"(tm_)
: [e]"r"((const void*)(S+2*r)),[sb]"r"((const void*)Sb),[ya]"r"((unsigned long long)ya)
: "cc","memory");
u32 c=zquery<LV>(W_T(Sb[1]))&(u32)m_;
{__m128i _v=_mm_add_epi64(_mm_load_si128((const __m128i*)(const void*)Sb),_mm_cvtsi64_si128((long long)c));if constexpr(NT)_mm_stream_si128((__m128i*)(void*)Dt,_v);else _mm_store_si128((__m128i*)(void*)Dt,_v);}Sb+=(u64_x)((m_&16u)>>3);Dt+=(u64_x)((m_&16u)>>3); }
while(Sb<S+2*r&&Sb[0]<=ya){u32 c=zquery<LV>(W_T(Sb[1]));{__m128i _v=_mm_add_epi64(_mm_load_si128((const __m128i*)(const void*)Sb),_mm_cvtsi64_si128((long long)c));if constexpr(NT)_mm_stream_si128((__m128i*)(void*)Dt,_v);else _mm_store_si128((__m128i*)(void*)Dt,_v);}Sb+=2;Dt+=2;}
zadd<LV>(W_R(Sa[1]));{__m128i _v=_mm_load_si128((const __m128i*)(const void*)Sa);if constexpr(NT)_mm_stream_si128((__m128i*)(void*)Dt,_v);else _mm_store_si128((__m128i*)(void*)Dt,_v);}Sa+=2;Dt+=2;
}
while(Sb<S+2*r){u32 c=zquery<LV>(W_T(Sb[1]));{__m128i _v=_mm_add_epi64(_mm_load_si128((const __m128i *)(const void*)Sb),_mm_cvtsi64_si128((long long)c));if constexpr(NT)_mm_stream_si128((__m128i*)(void*)Dt,_v);else _mm_store_si128((__m128i*)(void*)Dt,_v);}Sb+=2;Dt+=2;}
if constexpr(NT)_mm_sfence();
memset(ZB,0,sizeof(ZB));memset(ZWP,0,sizeof(ZWP));memset(C2,0,sizeof(C2));memset(C3,0,sizeof(C3));memset(C4,0,sizeof(C4));
}
static void merge_run(int l, int m, int r, int src, int dst) {
u64_x *S = RC[src];
u64_x *D = RC[dst];
int a = l, b = m, t = l;
while (a < m && b < r) {
int c = (S[2 * a] <= (S[2 * b] | 0xffffffffffULL));
int s = c ? a : b;
D[2 * t] = S[2 * s]; D[2 * t + 1] = S[2 * s + 1];
a += c; b += 1 - c; t++;
}
while (a < m) { D[2 * t] = S[2 * a]; D[2 * t + 1] = S[2 * a + 1]; a++; t++; }
while (b < r) { D[2 * t] = S[2 * b]; D[2 * t + 1] = S[2 * b + 1]; b++; t++; }
}
template <int LV> static void cross_filter(int l, int m, int r, int src, u32 g, int pass) {
u64_x *S = RC[src];
int i = l;
if (pass == 1) {
for (int j = m; j < r; j++) {
if (W_X(S[2 * j + 1]) == g) continue;
u32 yj = (u32)(S[2 * j] >> 40);
while (i < m && (u32)(S[2 * i] >> 40) < yj) { zadd<LV>(W_R(S[2 * i + 1])); i++; }
u32 c = zquery<LV>(W_T(S[2 * j + 1]));
if (c) S[2 * j] += c;
}
for (int k = l; k < i; k++) zsub<LV>(W_R(S[2 * k + 1]));
} else {
for (int j = m; j < r; j++) {
if (W_X(S[2 * j + 1]) != g) continue;
u32 yj = (u32)(S[2 * j] >> 40);
while (i < m && (u32)(S[2 * i] >> 40) < yj) {
if (W_X(S[2 * i + 1]) < g) zadd<LV>(W_R(S[2 * i + 1]));
i++;
}
u32 c = zquery<LV>(W_T(S[2 * j + 1]));
if (c) S[2 * j] += c;
}
for (int k = l; k < i; k++) if (W_X(S[2 * k + 1]) < g) zsub<LV>(W_R(S[2 * k + 1]));
}
}
#ifndef LEAF_N
#define LEAF_N 8
#endif
#define LSCR 512
static u32 lex[LSCR + 16], ley[LSCR + 16], ler[LSCR + 16];
static u64_x lkey[LSCR + 16];
static u64_x ltmp_buf[2 * (LSCR + 16) + 8] __attribute__((aligned(32)));
static u64_x *const ltmp = ltmp_buf + 2;
static u8 lrx[LSCR+16] __attribute__((aligned(32))),lrz[LSCR+16] __attribute__((aligned(32)));
static u8 lxb[320] __attribute__((aligned(32))),lzb[320] __attribute__((aligned(32)));
static u32 lzk[256] __attribute__((aligned(32)));
static u32 lk_storage[264] __attribute__((aligned(32)));
static u32 *const lk=lk_storage+8;
static inline void mrg64(__m256i *r){
#define CE(x,y) do{__m256i lo_=_mm256_min_epu32((x),(y)),hi_=_mm256_max_epu32((x),(y));(x)=lo_;(y)=hi_;}while(0)
CE(r[0],r[4]);CE(r[1],r[5]);CE(r[2],r[6]);CE(r[3],r[7]);
CE(r[0],r[2]);CE(r[1],r[3]);CE(r[4],r[6]);CE(r[5],r[7]);
CE(r[0],r[1]);CE(r[2],r[3]);CE(r[4],r[5]);CE(r[6],r[7]);
#undef CE
#pragma GCC unroll 8
for(int q=0;q<8;q++){__m256i a=r[q],t;
t=_mm256_permute4x64_epi64(a,0x4e);a=_mm256_blend_epi32(_mm256_min_epu32(a,t),_mm256_max_epu32(a,t),0xf0);
t=_mm256_shuffle_epi32(a,0x4e);a=_mm256_blend_epi32(_mm256_min_epu32(a,t),_mm256_max_epu32(a,t),0xcc);
t=_mm256_shuffle_epi32(a,0xb1);a=_mm256_blend_epi32(_mm256_min_epu32(a,t),_mm256_max_epu32(a,t),0xaa);
r[q]=a;}
}
static inline void bm128f(u32 *k){
const __m256i RIDX=_mm256_setr_epi32(7,6,5,4,3,2,1,0);
__m256i r[16];
#pragma GCC unroll 8
for(int q=0;q<8;q++){r[q]=_mm256_load_si256((const __m256i*)(k+8*q));r[8+q]=_mm256_load_si256((const __m256i*)(k+64+8*q));}
#pragma GCC unroll 4
for(int q=0;q<4;q++){const int r2=7-q;__m256i a=r[q],b=r[r2];
__m256i ua=_mm256_permutevar8x32_epi32(r[8+r2],RIDX),ub=_mm256_permutevar8x32_epi32(r[8+q],RIDX);
r[q]=_mm256_min_epu32(a,ua);r[8+q]=_mm256_max_epu32(a,ua);
r[r2]=_mm256_min_epu32(b,ub);r[8+r2]=_mm256_max_epu32(b,ub);}
mrg64(r);mrg64(r+8);
#pragma GCC unroll 16
for(int q=0;q<16;q++)_mm256_store_si256((__m256i*)(k+8*q),r[q]);
}
static inline void bm256f(u32 *k){
const __m256i RIDX=_mm256_setr_epi32(7,6,5,4,3,2,1,0);
#pragma GCC unroll 8
for(int q=0;q<8;q++){const int r2=15-q,jq=8*q,jr=8*r2;
__m256i a0=_mm256_load_si256((const __m256i*)(k+jq));
__m256i u0=_mm256_permutevar8x32_epi32(_mm256_loadu_si256((const __m256i*)(k+128+jr)),RIDX);
__m256i a1=_mm256_load_si256((const __m256i*)(k+jr));
__m256i u1=_mm256_permutevar8x32_epi32(_mm256_loadu_si256((const __m256i*)(k+128+jq)),RIDX);
_mm256_store_si256((__m256i*)(k+jq),_mm256_min_epu32(a0,u0));
_mm256_store_si256((__m256i*)(k+128+jq),_mm256_max_epu32(a0,u0));
_mm256_store_si256((__m256i*)(k+jr),_mm256_min_epu32(a1,u1));
_mm256_store_si256((__m256i*)(k+128+jr),_mm256_max_epu32(a1,u1));}
#pragma GCC unroll 2
for(int h=0;h<256;h+=128){
__m256i r[16];
#pragma GCC unroll 16
for(int q=0;q<16;q++)r[q]=_mm256_load_si256((const __m256i*)(k+h+8*q));
#pragma GCC unroll 8
for(int q=0;q<8;q++){__m256i a=r[q],b=r[q+8];r[q]=_mm256_min_epu32(a,b);r[q+8]=_mm256_max_epu32(a,b);}
mrg64(r);mrg64(r+8);
#pragma GCC unroll 16
for(int q=0;q<16;q++)_mm256_store_si256((__m256i*)(k+h+8*q),r[q]);}
}
static inline void bm(u32 *k, int n) {
if(n==256)bm256f(k);else bm128f(k);
}
static inline void bs64(__m256i *r) {
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[2]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
{ __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[4]=Hi; }
{ __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[5]=Hi; }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[4]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[0], B=r[4]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[4]=Hi; }
{ __m256i A=r[1], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[5]=Hi; }
{ __m256i A=r[2], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[6]=Hi; }
{ __m256i A=r[3], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[7]=Hi; }
{ __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
{ __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[6]=Hi; }
{ __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[7]=Hi; }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[7]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
}
__attribute__((noinline,noclone)) static void leaf_sort(u32 *a, int sn) {
if(sn<=64){for(int k=sn;k<64;++k)a[k]=0xffffffffu;bs64((__m256i*)a);}
else if(sn<=128){for(int k=sn;k<128;++k)a[k]=0xffffffffu;bs64((__m256i*)a);bs64((__m256i*)(a+64));bm(a,128);}
else {for(int k=sn;k<256;++k)a[k]=0xffffffffu;for(int k=0;k<256;k+=64)bs64((__m256i*)(a+k));bm(a,128);bm(a+128,128);bm(a,256);}
}
template<bool RelativeX> __attribute__((always_inline)) static inline void build_leaf_keys(u64_x *S,int l,int sn,u32 xbase) {
u32 prevx = 0xFFFFFFFFu; int xr = -1;
const __m256i ID4 = _mm256_setr_epi64x(0,1,2,3);
const __m256i PK = _mm256_setr_epi32(0,2,4,6,0,2,4,6);
const __m256i M20 = _mm256_set1_epi64x(0xFFFFF);
int k4 = 0;
for (; k4 + 4 <= sn; k4 += 4) {
const u64_x *P = S + 2 * (l + k4);
__m256i v0 = _mm256_loadu_si256((const __m256i *)(const void *)P);
__m256i v1 = _mm256_loadu_si256((const __m256i *)(const void *)(P + 4));
__m256i t0 = _mm256_permute4x64_epi64(v0, 0xD8);
__m256i t1 = _mm256_permute4x64_epi64(v1, 0xD8);
__m256i w0 = _mm256_permute2x128_si256(t0, t1, 0x20);
__m256i w1 = _mm256_permute2x128_si256(t0, t1, 0x31);
const __m256i high_dwords = _mm256_setr_epi32(1,3,5,7,1,3,5,7);
const __m128i key_mask = _mm_set1_epi32((int)0xffffff00u);
const __m128i kidx = _mm_add_epi32(_mm_setr_epi32(0,1,2,3), _mm_set1_epi32(k4));
const __m128i ykeys = _mm_and_si128(_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(w0, high_dwords)),key_mask);
const __m128i zkeys = _mm_and_si128(_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(w1, high_dwords)),key_mask);
_mm_store_si128((__m128i *)(void *)(lk+k4), _mm_or_si128(ykeys,kidx));
_mm_store_si128((__m128i *)(void *)(lzk+k4), _mm_or_si128(zkeys,kidx));
__m128i x4 = _mm256_castsi256_si128(_mm256_permutevar8x32_epi32(_mm256_and_si256(w1, M20), PK));
__m128i rk;
if constexpr(RelativeX) {
rk=_mm_xor_si128(_mm_sub_epi32(x4,_mm_set1_epi32((int)xbase)),_mm_set1_epi32(0x80));
} else {
__m128i sh = _mm_insert_epi32(_mm_slli_si128(x4, 4), (int)prevx, 0);
__m128i neq = _mm_cmpeq_epi32(x4, sh);
__m128i fl = _mm_andnot_si128(neq, _mm_set1_epi32(1));
__m128i ps = _mm_add_epi32(fl, _mm_slli_si128(fl, 4));
ps = _mm_add_epi32(ps, _mm_slli_si128(ps, 8));
rk = _mm_xor_si128(_mm_add_epi32(ps, _mm_set1_epi32(xr)), _mm_set1_epi32(0x80));
xr += _mm_extract_epi32(ps, 3);
prevx = (u32)_mm_extract_epi32(x4, 3);
}
__m128i b8=_mm_shuffle_epi8(rk,_mm_setr_epi8(0,4,8,12,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1));
*(u32 *)(void *)(lrx + k4) = (u32)_mm_cvtsi128_si32(b8);
}
for (int k = k4; k < sn; k++) {
u64_x w0 = S[2 * (l + k)], w1 = S[2 * (l + k) + 1];
lk[k] = ((u32)(w0 >> 40) << 8) | (u32)k;
const u32 xv = (u32)(w1 & 0xFFFFFu);
if constexpr(RelativeX) lrx[k]=(u8)((xv-xbase)^0x80u);
else {if(xv!=prevx){prevx=xv;xr++;}lrx[k]=(u8)((u32)xr^0x80u);}
lzk[k] = (u32)(((w1 >> 40) & 0xFFFFFu) << 8) | (u32)k;
}
}
struct alignas(32) BytePrefixMasks {
u8 row[33][32];
constexpr BytePrefixMasks():row{} { for(int n=0;n<=32;++n)for(int j=0;j<32;++j)row[n][j]=j<n?255:0; }
};
static constexpr BytePrefixMasks byte_prefix_masks{};
static inline __m256i byte_prefix(int n){return _mm256_load_si256((const __m256i*)byte_prefix_masks.row[n]);}
static int cdq_leaf(int l, int r, int in) {
u64_x *S = RC[in];
u64_x *const ltmp = RC[1-in] + 2*l;
const int sn = r - l;
const u32 xbase=W_X(S[2*l+1]);
if(W_X(S[2*(r-1)+1])-xbase<256u) build_leaf_keys<true>(S,l,sn,xbase);
else build_leaf_keys<false>(S,l,sn,xbase);
leaf_sort(lzk, sn);
{
u32 prevz=~0u,first=0;
int q=0;
const __m256i pick=_mm256_setr_epi8(0,4,8,12,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,
0,4,8,12,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128);
for(;q+8<=sn;q+=8){
const __m256i v=_mm256_load_si256((const __m256i*)(lzk+q));
const __m256i z=_mm256_srli_epi32(v,8);
__m256i p;
if(q) p=_mm256_srli_epi32(_mm256_loadu_si256((const __m256i*)(lzk+q-1)),8);
else p=_mm256_setr_epi32(-1,lzk[0]>>8,lzk[1]>>8,lzk[2]>>8,lzk[3]>>8,lzk[4]>>8,lzk[5]>>8,lzk[6]>>8);
if(_mm256_movemask_epi8(_mm256_cmpeq_epi32(z,p))==0){
const __m256i ix=_mm256_shuffle_epi8(v,pick);
const u32 x0=(u32)_mm256_extract_epi32(ix,0),x1=(u32)_mm256_extract_epi32(ix,4);
const unsigned b=(unsigned)q^128u;
#pragma GCC unroll 4
for(int k=0;k<4;k++)lrz[(x0>>(k*8))&255u]=(u8)(b+k);
#pragma GCC unroll 4
for(int k=0;k<4;k++)lrz[(x1>>(k*8))&255u]=(u8)(b+4u+k);
first=q+7;prevz=lzk[q+7]>>8;
}else{
#pragma GCC unroll 1
for(int k=0;k<8;k++){u32 r=lzk[q+k],zv=r>>8;if(zv!=prevz){first=q+k;prevz=zv;}lrz[r&255u]=(u8)(first^128u);}
}
}
for(;q<sn;q++){u32 r=lzk[q],zv=r>>8;if(zv!=prevz){first=q;prevz=zv;}lrz[r&255u]=(u8)(first^128u);}
}
leaf_sort(lk, sn);
lk[-1]=lk[0];
for (int q = 0; q < sn; q++) {
const int sr = (int)(lk[q] & 255u);
_mm_store_si128((__m128i *)(void *)(ltmp + 2 * q), _mm_load_si128((const __m128i *)(const void *)(S + 2 * (l + sr))));
lxb[q] = lrx[sr]; lzb[q] = lrz[sr];
}
{
const __m256i idxv = _mm256_setr_epi8(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31);
const __m256i zero = _mm256_setzero_si256();
int g=0,q=(sn%4==0?0:1);
int ally=1;
{
__m256i acc=_mm256_setzero_si256();
int t=0;
for(;t+8<sn;t+=8){
__m256i ka=_mm256_loadu_si256((const __m256i*)(lk+t));
__m256i kb=_mm256_loadu_si256((const __m256i*)(lk+t+1));
acc=_mm256_or_si256(acc,_mm256_cmpeq_epi32(_mm256_srli_epi32(ka,8),_mm256_srli_epi32(kb,8)));
}
for(;t+1<sn;t++)if((lk[t]>>8)==(lk[t+1]>>8)){acc=_mm256_set1_epi32(-1);break;}
ally=_mm256_testz_si256(acc,acc);
}
for(;q+3<sn;q+=4){
int g0,g1,g2,g3;
if(ally){g0=q;g1=q+1;g2=q+2;g3=q+3;}
else{int gg=g;if((lk[q]>>8)!=(lk[q-1]>>8))gg=q;g0=gg;if((lk[q+1]>>8)!=(lk[q]>>8))gg=q+1;g1=gg;if((lk[q+2]>>8)!=(lk[q+1]>>8))gg=q+2;g2=gg;if((lk[q+3]>>8)!=(lk[q+2]>>8))gg=q+3;g3=gg;g=gg;}
__m256i X[4],Z[4],A[4];
#pragma GCC unroll 4
for(int u=0;u<4;u++){X[u]=_mm256_set1_epi8((char)lxb[q+u]);Z[u]=_mm256_set1_epi8((char)lzb[q+u]);A[u]=zero;}
int k=0;
#pragma GCC unroll 1
for(;k+32<=g0;k+=32){
__m256i x=_mm256_load_si256((const __m256i*)(lxb+k)),z=_mm256_load_si256((const __m256i*)(lzb+k));
#pragma GCC unroll 4
for(int u=0;u<4;u++)A[u]=_mm256_sub_epi8(A[u],_mm256_and_si256(_mm256_cmpgt_epi8(X[u],x),_mm256_cmpgt_epi8(Z[u],z)));
}
if(g3-k<=32){
if(k<g3){
__m256i x=_mm256_load_si256((const __m256i*)(lxb+k)),z=_mm256_load_si256((const __m256i*)(lzb+k));
__m256i m0=byte_prefix(g0-k),m1=byte_prefix(g1-k),m2=byte_prefix(g2-k),m3=byte_prefix(g3-k);
A[0]=_mm256_sub_epi8(A[0],_mm256_and_si256(m0,_mm256_and_si256(_mm256_cmpgt_epi8(X[0],x),_mm256_cmpgt_epi8(Z[0],z))));
A[1]=_mm256_sub_epi8(A[1],_mm256_and_si256(m1,_mm256_and_si256(_mm256_cmpgt_epi8(X[1],x),_mm256_cmpgt_epi8(Z[1],z))));
A[2]=_mm256_sub_epi8(A[2],_mm256_and_si256(m2,_mm256_and_si256(_mm256_cmpgt_epi8(X[2],x),_mm256_cmpgt_epi8(Z[2],z))));
A[3]=_mm256_sub_epi8(A[3],_mm256_and_si256(m3,_mm256_and_si256(_mm256_cmpgt_epi8(X[3],x),_mm256_cmpgt_epi8(Z[3],z))));
}
}else{
int GA[4]={g0,g1,g2,g3};
#pragma GCC unroll 4
for(int u=0;u<4;u++){
int t=k;
#pragma GCC unroll 1
for(;t+32<=GA[u];t+=32){__m256i x=_mm256_load_si256((const __m256i*)(lxb+t)),z=_mm256_load_si256((const __m256i*)(lzb+t));A[u]=_mm256_sub_epi8(A[u],_mm256_and_si256(_mm256_cmpgt_epi8(X[u],x),_mm256_cmpgt_epi8(Z[u],z)));}
if(t<GA[u]){__m256i x=_mm256_load_si256((const __m256i*)(lxb+t)),z=_mm256_load_si256((const __m256i*)(lzb+t));__m256i m=byte_prefix(GA[u]-t);A[u]=_mm256_sub_epi8(A[u],_mm256_and_si256(m,_mm256_and_si256(_mm256_cmpgt_epi8(X[u],x),_mm256_cmpgt_epi8(Z[u],z))));}
}
}
__m256i s0=_mm256_sad_epu8(A[0],zero),s1=_mm256_sad_epu8(A[1],zero);
__m256i s2=_mm256_sad_epu8(A[2],zero),s3=_mm256_sad_epu8(A[3],zero);
__m256i a01=_mm256_add_epi32(_mm256_unpacklo_epi32(s0,s1),_mm256_unpackhi_epi32(s0,s1));
__m256i a23=_mm256_add_epi32(_mm256_unpacklo_epi32(s2,s3),_mm256_unpackhi_epi32(s2,s3));
__m256i all=_mm256_unpacklo_epi64(a01,a23);
__m128i sums=_mm_add_epi32(_mm256_castsi256_si128(all),_mm256_extracti128_si256(all,1));
const __m128i z128=_mm_setzero_si128();
const __m256i add01=_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(sums,z128));
const __m256i add23=_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(sums,z128));
u64_x *const L0=ltmp+2*q,*const L1=ltmp+2*q+4;
__m256i V0,V1;
asm("vmovdqu %1,%0" : "=x"(V0) : "m"(*(const __m256i_u*)L0));
asm("vmovdqu %1,%0" : "=x"(V1) : "m"(*(const __m256i_u*)L1));
V0=_mm256_add_epi64(V0,add01);V1=_mm256_add_epi64(V1,add23);
asm("vmovdqu %1,%0" : "=m"(*(__m256i_u*)L0) : "x"(V0));
asm("vmovdqu %1,%0" : "=m"(*(__m256i_u*)L1) : "x"(V1));
}
if(ally)g=q;
for (; q < sn; q++) {
if ((lk[q] >> 8) != (lk[q - 1] >> 8)) g = q;
const __m256i mxj = _mm256_set1_epi8((char)lxb[q]);
const __m256i mzj = _mm256_set1_epi8((char)lzb[q]);
__m256i vacc = zero;
int k = 0;
#pragma GCC unroll 1
for (; k + 64 <= g; k += 64) {
__m256i c0 = _mm256_and_si256(
_mm256_cmpgt_epi8(mxj, _mm256_load_si256((const __m256i *)(lxb + k))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(lzb + k))));
__m256i c1 = _mm256_and_si256(
_mm256_cmpgt_epi8(mxj, _mm256_load_si256((const __m256i *)(lxb + k + 32))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(lzb + k + 32))));
vacc = _mm256_sub_epi8(vacc, _mm256_add_epi8(c0, c1));
}
#pragma GCC unroll 1
for (; k + 32 <= g; k += 32) {
__m256i c = _mm256_and_si256(
_mm256_cmpgt_epi8(mxj, _mm256_load_si256((const __m256i *)(lxb + k))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(lzb + k))));
vacc = _mm256_sub_epi8(vacc, c);
}
if (k < g) {
const __m256i msk = byte_prefix(g-k);
__m256i c = _mm256_and_si256(
_mm256_cmpgt_epi8(mxj, _mm256_load_si256((const __m256i *)(lxb + k))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(lzb + k))));
vacc = _mm256_sub_epi8(vacc, _mm256_and_si256(c, msk));
}
const __m256i s64 = _mm256_sad_epu8(vacc, zero);
const __m128i s = _mm_add_epi64(_mm256_castsi256_si128(s64), _mm256_extracti128_si256(s64, 1));
const u32 acc = (u32)((unsigned long long)_mm_cvtsi128_si64(s) + (unsigned long long)_mm_extract_epi64(s, 1));
ltmp[2 * q] += acc;
}
}
return 1-in;
}
template <int LV, int LF, int FULL, bool ROOT = false> static int cdq(int l, int r, int in) {
int s = r - l;
if (s <= 1) return in;
if (s <= LF) {
int bb = cdq_leaf(l, r, in);
if (FULL) { u64_x *Q = RC[bb]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return bb;
}
int m = (l + r) >> 1;
int mode = 3;
const u64_x *SI = RC[in];
if (__builtin_expect(W_X(SI[2 * m - 1]) != W_X(SI[2 * m + 1]), 1)) mode = 0;
else {
u32 g = W_X(SI[2 * m + 1]);
int a = m - 1; while (a > l && W_X(SI[2 * a - 1]) == W_X(SI[2 * a + 1])) a--;
int b = m; while (b < r && W_X(SI[2 * b - 1]) == W_X(SI[2 * b + 1])) b++;
if (a == l && b == r) mode = 2;
else {
int lim = s >> 2;
int ca = -1, cb = -1;
if (a > l && a - l >= lim && r - a >= lim) ca = a;
if (b < r && b - l >= lim && r - b >= lim) cb = b;
if (ca >= 0 && (cb < 0 || m - ca <= cb - m)) { m = ca; mode = 1; }
else if (cb >= 0) { m = cb; mode = 1; }
}
}
if (FULL == 0 && (mode == 0 || mode == 1)) {
int b2 = cdq<LV, LF, 0>(m, r, in);
int b1;
if (ROOT || s >= ZCTHR) b1 = cdq<LV, LF, 0>(l, m, in);
else b1 = cdq<LV, LF, 1>(l, m, in);
if (b1 != b2) {
memcpy(RC[b1] + 2 * m, RC[b2] + 2 * m, (size_t)(r - m) * 16);
b2 = b1;
}
if (ROOT) { node_root_ascending<LV>(l, m, r, b1); return -1; }
int out = 1 - b1;
if (s >= NTT) { node_fused_asc_clear<LV,true>(l, m, r, b1, out); return out; }
if (s >= ZCTHR) { node_fused_asc_clear<LV>(l, m, r, b1, out); return out; }
node_fused_desc<LV>(l, m, r, b1, out);
return out;
}
int b1 = cdq<LV, LF, 0>(l, m, in);
int b2 = cdq<LV, LF, 0>(m, r, in);
if (b1 != b2) {
memcpy(RC[b1] + 2 * m, RC[b2] + 2 * m, (size_t)(r - m) * 16);
b2 = b1;
}
if (mode == 0 || mode == 1) {
int out = 1 - b1;
if (FULL) { node_fused_full<LV>(l, m, r, b1, out); return out; }
node_fused<LV>(l, m, r, b1, out);
return out;
}
if (mode == 2) {
int out = 1 - b1;
merge_run(l, m, r, b1, out);
if (FULL) { u64_x *Q = RC[out]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return out;
}
{
const u64_x *S = RC[b1];
u32 g = 0;
for (int k = l; k < m; k++) { u32 xv = W_X(S[2 * k + 1]); if (xv > g) g = xv; }
cross_filter<LV>(l, m, r, b1, g, 1);
cross_filter<LV>(l, m, r, b1, g, 2);
}
int out = 1 - b1;
merge_run(l, m, r, b1, out);
if (FULL) { u64_x *Q = RC[out]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return out;
}
void count_3d(int n, const unsigned *x, const unsigned *y, const unsigned *z, unsigned *out) {
if (n <= 1) { if (n == 1) out[0] = 0; return; }
msk_init();
u8 *frequency=(u8*)(void*)RC[0];
memset(frequency,0,(size_t)n+1);
memset(CNT,0,1024*4);
for(int i=0;i<n;++i){++frequency[z[i]];++CNT[x[i]>>10];}
u32 total_count=0;
__m128i max_frequency=_mm_setzero_si128();
bool compact_z=true;
static u32 rank_block_base[(MAXN+2047)/2048+1];
u16 *rank_half=(u16*)(void*)H32;
for(int block=0;block<=n;block+=2048){
rank_block_base[block>>11]=total_count;
const int end=(block+2048<n+1 ? block+2048 : n+1);
u32 local_count=0;int v=block;
for(;v+16<=end;v+=16){
const __m128i bytes=_mm_loadu_si128((const __m128i*)(frequency+v));
max_frequency=_mm_max_epu8(max_frequency,bytes);
const __m256i raw=_mm256_cvtepu8_epi16(bytes);
__m256i val=_mm256_add_epi16(raw,_mm256_slli_si256(raw,2));
val=_mm256_add_epi16(val,_mm256_slli_si256(val,4));
val=_mm256_add_epi16(val,_mm256_slli_si256(val,8));
const __m256i low=_mm256_shuffle_epi8(_mm256_permute2x128_si256(val,val,0x08),_mm256_set1_epi16(0x0f0e));
val=_mm256_add_epi16(val,low);
const __m256i ex=_mm256_add_epi16(_mm256_sub_epi16(val,raw),_mm256_set1_epi16((short)local_count));
_mm256_store_si256((__m256i*)(rank_half+v),_mm256_slli_epi16(ex,4));
local_count+=(u32)_mm256_extract_epi16(val,15);
}
for(;v<end;++v){u32 c=frequency[v];compact_z &= c<=15;rank_half[v]=(u16)(local_count<<4);local_count+=c;}
compact_z &= local_count<=4095;
total_count+=local_count;
}
const bool wide_z=total_count!=(u32)n;
compact_z &= !wide_z && _mm_testz_si128(max_frequency,_mm_set1_epi8((char)0xf0));
if(!compact_z && !wide_z){
total_count=0;
{
int v=0;
for(;v+16<=n+1;v+=16){
const __m128i bytes=_mm_loadu_si128((const __m128i*)(frequency+v));
max_frequency=_mm_max_epu8(max_frequency,bytes);
const __m256i raw=_mm256_cvtepu8_epi16(bytes);
__m256i val=_mm256_add_epi16(raw,_mm256_slli_si256(raw,2));
val=_mm256_add_epi16(val,_mm256_slli_si256(val,4));
val=_mm256_add_epi16(val,_mm256_slli_si256(val,8));
const __m256i low=_mm256_shuffle_epi8(_mm256_permute2x128_si256(val,val,0x08),_mm256_set1_epi16(0x0f0e));
val=_mm256_add_epi16(val,low);
const __m256i ex=_mm256_sub_epi16(val,raw),base=_mm256_set1_epi32((int)total_count);
const __m256i a=_mm256_add_epi32(base,_mm256_cvtepu16_epi32(_mm256_castsi256_si128(ex)));
const __m256i b=_mm256_add_epi32(base,_mm256_cvtepu16_epi32(_mm256_extracti128_si256(ex,1)));
_mm256_store_si256((__m256i*)(H32+v),_mm256_slli_epi32(a,12));
_mm256_store_si256((__m256i*)(H32+v+8),_mm256_slli_epi32(b,12));
total_count+=(u32)_mm256_extract_epi16(val,15);
}
for(;v<=n;++v){u32 c=frequency[v];compact_z &= c<=15;H32[v]=total_count<<12;total_count+=c;}
}
}
if (wide_z) {
memset(P1, 0, (size_t)(n+1)*sizeof(u64_x));
for(int i=0;i<n;i++) ++P1[z[i]];
u32 sum=0;
for(int v=0;v<=n;v++){u32 c=(u32)P1[v];P1[v]=(u64_x)sum<<32;sum+=c;}
}
static u32 ST10[1025];
static u16 C16[1024];
{
u32 acc = 0;
for (int v = 0; v < 1024; v++) { u32 c = CNT[v]; ST10[v] = acc; CNT[v] = acc; acc += c; }
ST10[1024] = acc;
}
auto scatter = [&](auto wide_tag) {
auto one = [&](auto prefetch_tag, int i) {
if constexpr(decltype(prefetch_tag)::value) { __builtin_prefetch(&CNT[x[i + 64] >> 10]);
__builtin_prefetch(&RC[0][2 * (size_t)CNT[x[i + 64] >> 10]]); }
u32 T,R;
if constexpr(decltype(wide_tag)::value==2){
if constexpr(decltype(prefetch_tag)::value)__builtin_prefetch((const u16*)H32+z[i+32]);
const u32 zv=z[i];u16 *cursor=(u16*)(void*)H32+zv;const u32 h=*cursor;
*cursor=(u16)(h+1);T=rank_block_base[zv>>11]+(h>>4);R=T+(h&15u);
}else if constexpr(decltype(wide_tag)::value==1) {
if constexpr(decltype(prefetch_tag)::value) __builtin_prefetch(&P1[z[i+32]]);
u64_x h=P1[z[i]]++; T=(u32)(h>>32); R=T+(u32)h;
} else {
if constexpr(decltype(prefetch_tag)::value) __builtin_prefetch(&H32[z[i+32]]);
u32 zv=z[i],h=H32[zv]; T=h>>12;R=T+(h&0xFFFu);
H32[zv]=h+1;
}
u64_x record = ((u64_x)T << 40) | ((u64_x)R << 20) | (u64_x)x[i];
const u32 t = CNT[x[i] >> 10]++;
_mm_storeu_si128((__m128i *)(void *)(RC[0] + 2 * t),
_mm_set_epi64x((long long)record, (long long)(((u64_x)y[i] << 40) | ((u64_x)i << 20))));
};
const int end=n>96?n-96:0;
for(int i=0;i<end;++i)one(std::true_type{},i);
for(int i=end;i<n;++i)one(std::false_type{},i);
};
if(compact_z)scatter(std::integral_constant<int,2>{});else if(wide_z)scatter(std::integral_constant<int,1>{});else scatter(std::integral_constant<int,0>{});
{
u64_x *D = RC[1];
for (int b = 0; b < 1024; b++) {
const int lo = (int)ST10[b], hi = (int)ST10[b + 1];
if (hi <= lo) continue;
if (hi-lo > 65535) {
u32 wide[1024]={};
for(int t=lo;t<hi;t++)wide[RC[0][2*t+1]&1023u]++;
u32 sum=0;for(int v=0;v<1024;v++){u32 c=wide[v];wide[v]=sum;sum+=c;}
for(int t=lo;t<hi;t++){u32 p=(u32)lo+wide[RC[0][2*t+1]&1023u]++;
_mm_storeu_si128((__m128i*)(D+2*p),_mm_loadu_si128((const __m128i*)(RC[0]+2*t)));}
continue;
}
memset(C16, 0, 1024 * 2);
for (int t = lo; t < hi; t++) C16[RC[0][2 * t + 1] & 1023u]++;
__m256i carry = _mm256_setzero_si256();
const __m256i b7w = _mm256_setr_epi8(14,15,14,15,14,15,14,15,14,15,14,15,14,15,14,15,
14,15,14,15,14,15,14,15,14,15,14,15,14,15,14,15);
for (int v = 0; v < 1024; v += 16) {
__m256i o = _mm256_loadu_si256((const __m256i *)(C16 + v));
__m256i t = _mm256_add_epi16(o, _mm256_slli_si256(o,2));
t = _mm256_add_epi16(t, _mm256_slli_si256(t,4));
t = _mm256_add_epi16(t, _mm256_slli_si256(t,8));
t = _mm256_add_epi16(t, _mm256_shuffle_epi8(_mm256_permute2x128_si256(t,t,0x08),b7w));
__m256i total = _mm256_add_epi16(t,carry);
_mm256_storeu_si256((__m256i *)(C16+v),_mm256_sub_epi16(total,o));
carry = _mm256_shuffle_epi8(_mm256_permute2x128_si256(total,total,0x11),b7w);
}
for (int t = lo; t < hi; t++) {
const u32 p = (u32)lo + (u32)C16[RC[0][2 * t + 1] & 1023u]++;
_mm_storeu_si128((__m128i *)(void *)(D + 2 * p),
_mm_loadu_si128((const __m128i *)(const void *)(RC[0] + 2 * t)));
}
}
}
int bb = (n <= 262144) ? cdq<3, 64, 0>(0, n, 1)
: (g_rootout = out, cdq<4, 256, 0, true>(0, n, 1));
if (bb >= 0) {
const u64_x *D = RC[bb];
for (int p = 0; p < n; p++) {
if (p + 32 < n) __builtin_prefetch(&out[W_ORIG(D[2 * (p + 32)])]);
out[W_ORIG(D[2 * p])] = W_A(D[2 * p]);
}
}
g_rootout = 0;
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 105.815 ms | 34 MB + 528 KB | Accepted | Score: 100 | 显示更多 |