/* 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 2048
#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;
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 RC[2][2 * (MAXN + 8)] __attribute__((aligned(64)));
static u64 P1[MAXN];
static u64 TIE[(MAXN + 63) / 64 + 8];
#define H32 ((u32 *)(void *)RC[1])
#define CNT ((u32 *)(void *)((u64 *)RC[1] + (MAXN + 8) / 2))
struct alignas(64) CTRT {
alignas(32) u64 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 *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 *S = RC[src];
u64 *D = RC[dst];
int a = l, b = m;
u64 *Dt = D + 2 * l;
u64 *Sa = S + 2 * l, *Sb = S + 2 * m;
while (a < m && b < r) {
u64 w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if ((w0b >> 40) <= (w0a >> 40)) {
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 *S = RC[src];
u64 *D = RC[dst];
int a = l, b = m;
u64 *Dt = D + 2 * l;
u64 *Sa = S + 2 * l, *Sb = S + 2 * m;
while (a < m && b < r) {
u64 w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if ((w0b >> 40) <= (w0a >> 40)) {
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 *S = RC[src];
u64 *D = RC[dst];
u64 *Dt = D + 2 * (r - 1);
u64 *Sa = S + 2 * (m - 1), *Sa0 = S + 2 * l;
u64 *Sb = S + 2 * (r - 1), *Sb0 = S + 2 * m;
while (Sa >= Sa0) {
u64 ya = Sa[0] | 0xffffffffffULL;
{ u32 t = (u32)((Sb >= Sb0) & (Sb[0] > ya));
u32 c = zquery<LV>(W_T(Sb[1])) & (0u - t);
Sb[0] += c; Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb -= 2*(u64)t; Dt -= 2*(u64)t; }
while (Sb >= Sb0 && Sb[0] > ya) { u32 c = zquery<LV>(W_T(Sb[1])); Sb[0] += c; Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb -= 2; Dt -= 2; }
zsub<LV>(W_R(Sa[1])); Dt[0] = Sa[0]; Dt[1] = Sa[1]; Sa -= 2; Dt -= 2;
}
while (Sb >= Sb0) { u32 c = zquery<LV>(W_T(Sb[1])); Sb[0] += c; Dt[0] = Sb[0]; Dt[1] = Sb[1]; Sb -= 2; Dt -= 2; }
}
template <int LV> static void node_fused_desc_root(int l, int m, int r, int src) {
u64 *S = RC[src];
int ia = m - 1, ib = r - 1;
u64 *Sa = S + 2 * (m - 1), *Sb = S + 2 * (r - 1);
while (ia >= l && ib >= m) {
u64 w0b = Sb[0], w1b = Sb[1], w0a = Sa[0], w1a = Sa[1];
if ((w0b >> 40) > (w0a >> 40)) {
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 *S=RC[src];u64 *Sa=S+2*l,*Sb=S+2*m;
while(Sa<S+2*m&&Sb<S+2*r){u64 wa=Sa[0],wb=Sb[0];
if(W_Y(wb)<=W_Y(wa)){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 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 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));
}
#ifndef NTT
#define NTT 262144
#endif
template <bool NT> static inline void st2(u64 *Dt,u64 w0,u64 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 *S=RC[src];u64 *D=RC[dst];u64 *Dt=D+2*l,*Sa=S+2*l,*Sb=S+2*m;
while(Sa<S+2*m){
u64 ya=Sa[0]|0xffffffffffULL;
{ u32 t=(u32)((Sb<S+2*r)&(Sb[0]<=ya));
u32 c=zquery<LV,true>(W_T(Sb[1]))&(0u-t);
Sb[0]+=c;st2<NT>(Dt,Sb[0],Sb[1]);Sb+=2*(u64)t;Dt+=2*(u64)t; }
while(Sb<S+2*r&&Sb[0]<=ya){u32 c=zquery<LV,true>(W_T(Sb[1]));Sb[0]+=c;st2<NT>(Dt,Sb[0],Sb[1]);Sb+=2;Dt+=2;}
zadd<LV,true>(W_R(Sa[1]));st2<NT>(Dt,Sa[0],Sa[1]);Sa+=2;Dt+=2;
}
while(Sb<S+2*r){u32 c=zquery<LV,true>(W_T(Sb[1]));Sb[0]+=c;st2<NT>(Dt,Sb[0],Sb[1]);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 *S = RC[src];
u64 *D = RC[dst];
int a = l, b = m, t = l;
while (a < m && b < r) {
int c = ((S[2 * a] >> 40) <= (S[2 * b] >> 40));
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 *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 lkey[LSCR + 16], ltmp[2 * (LSCR + 16)];
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[256] __attribute__((aligned(32)));
static inline void bm(u32 *k, int n) {
const __m256i RIDX = _mm256_setr_epi32(7, 6, 5, 4, 3, 2, 1, 0);
{
for (int i = n / 2, j = n - 8; i < j; i += 8, j -= 8) {
__m256i a = _mm256_permutevar8x32_epi32(_mm256_loadu_si256((const __m256i *)(k + i)), RIDX);
__m256i b = _mm256_permutevar8x32_epi32(_mm256_loadu_si256((const __m256i *)(k + j)), RIDX);
_mm256_storeu_si256((__m256i *)(k + i), b);
_mm256_storeu_si256((__m256i *)(k + j), a);
}
if (n / 2 < n - 8 && (n / 2) % 8 == 0) { }
}
for (int d = n / 2; d >= 8; d >>= 1) {
for (int base = 0; base < n; base += 2 * d)
for (int j = 0; j < d; j += 8) {
__m256i a = _mm256_loadu_si256((const __m256i *)(k + base + j));
__m256i b = _mm256_loadu_si256((const __m256i *)(k + base + j + d));
_mm256_storeu_si256((__m256i *)(k + base + j), _mm256_min_epu32(a, b));
_mm256_storeu_si256((__m256i *)(k + base + j + d), _mm256_max_epu32(a, b));
}
}
for (int d = 4; d >= 1; d >>= 1) {
__m256i idx = _mm256_setr_epi32(0^d, 1^d, 2^d, 3^d, 4^d, 5^d, 6^d, 7^d);
__m256i bsel = _mm256_setr_epi32((0&d)?-1:0, (1&d)?-1:0, (2&d)?-1:0, (3&d)?-1:0,
(4&d)?-1:0, (5&d)?-1:0, (6&d)?-1:0, (7&d)?-1:0);
for (int base = 0; base < n; base += 8) {
__m256i a = _mm256_loadu_si256((const __m256i *)(k + base));
__m256i q = _mm256_permutevar8x32_epi32(a, idx);
__m256i lo = _mm256_min_epu32(a, q), hi = _mm256_max_epu32(a, q);
_mm256_storeu_si256((__m256i *)(k + base), _mm256_blendv_epi8(lo, hi, bsel));
}
}
}
static inline void bs64(__m256i *r) {
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,-1,0,0,-1,-1,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,-1,0,-1,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __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_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __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_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,-1,-1,0,0,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,-1,0,0,-1,-1,0,0)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(-1,0,-1,0,-1,0,-1,0)); }
{ __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_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,0,0,-1,-1,-1,-1)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,0,-1,-1,0,0,-1,-1)); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blendv_epi8(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),_mm256_setr_epi32(0,-1,0,-1,0,-1,0,-1)); }
}
static inline void leaf_sort(u32 *a, int sn) {
if (sn <= 64) {
for (int k = sn; k < 64; k++) a[k] = 0xFFFFFFFFu;
{ __m256i r0[8];
for (int q = 0; q < 8; q++) r0[q] = _mm256_load_si256((const __m256i *)(a + 8 * q));
bs64(r0);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(a + 8 * q), r0[q]); }
} else if (sn <= 128) {
for (int k = sn; k < 128; k++) a[k] = 0xFFFFFFFFu;
{ __m256i r0[8];
for (int q = 0; q < 8; q++) r0[q] = _mm256_load_si256((const __m256i *)(a + 8 * q));
bs64(r0);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(a + 8 * q), r0[q]);
for (int q = 0; q < 8; q++) r0[q] = _mm256_load_si256((const __m256i *)(a + 64 + 8 * q));
bs64(r0);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(a + 64 + 8 * q), r0[q]); }
bm(a,128);
} else {
for (int k = sn; k < 256; k++) a[k] = 0xFFFFFFFFu;
{ __m256i r0[8];
for (int q = 0; q < 8; q++) r0[q] = _mm256_load_si256((const __m256i *)(a + 8 * q));
bs64(r0);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(a + 8 * q), r0[q]);
for (int q = 0; q < 8; q++) r0[q] = _mm256_load_si256((const __m256i *)(a + 64 + 8 * q));
bs64(r0);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(a + 64 + 8 * q), r0[q]);
for (int q = 0; q < 8; q++) r0[q] = _mm256_load_si256((const __m256i *)(a + 128 + 8 * q));
bs64(r0);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(a + 128 + 8 * q), r0[q]);
for (int q = 0; q < 8; q++) r0[q] = _mm256_load_si256((const __m256i *)(a + 192 + 8 * q));
bs64(r0);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(a + 192 + 8 * q), r0[q]); }
bm(a,128); bm(a+128,128); bm(a,256);
}
}
static int cdq_leaf(int l, int r, int in) {
u64 *S = RC[in];
const int sn = r - l;
{
u32 prevx = 0xFFFFFFFFu; int xr = -1;
for (int k = 0; k < sn; k++) {
u64 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 (xv != prevx) { prevx = xv; xr++; }
lrx[k] = (u8)((u32)xr ^ 0x80u);
lzk[k] = (u32)(((w1 >> 40) & 0xFFFFFu) << 8) | (u32)k;
}
}
leaf_sort(lzk, sn);
{
/* [k09l_] vectorised dense-rank extraction */
u32 prevz = lzk[0] >> 8, rk = 1;
lrz[lzk[0] & 255u] = (u8)0x80u;
int q = 1;
const __m256i vzero = _mm256_setzero_si256();
const __m256i vbias = _mm256_set1_epi32(0x80);
const __m256i v255 = _mm256_set1_epi32(255);
for (; q + 8 <= sn; q += 8) {
__m256i vc = _mm256_loadu_si256((const __m256i *)(lzk + q));
__m256i vp = _mm256_loadu_si256((const __m256i *)(lzk + q - 1));
__m256i d = _mm256_cmpgt_epi32(_mm256_srli_epi32(vc, 8), _mm256_srli_epi32(vp, 8));
__m256i inc = _mm256_sub_epi32(vzero, d);
__m256i t = _mm256_add_epi32(inc, _mm256_slli_si256(inc, 4));
t = _mm256_add_epi32(t, _mm256_slli_si256(t, 8));
__m256i hi = _mm256_shuffle_epi32(_mm256_permute2x128_si256(t, t, 0x00), 0xFF);
t = _mm256_blend_epi32(t, _mm256_add_epi32(t, hi), 0xF0);
u32 grp = (u32)_mm256_extract_epi32(t, 7);
__m256i rv = _mm256_xor_si256(_mm256_add_epi32(t, _mm256_set1_epi32((int)rk - 1)), vbias);
rk += grp;
__m256i kk = _mm256_and_si256(vc, v255);
__m256i p8 = _mm256_packus_epi16(_mm256_packus_epi32(kk, kk), _mm256_packus_epi32(kk, kk));
__m256i b8 = _mm256_packus_epi16(_mm256_packus_epi32(rv, rv), _mm256_packus_epi32(rv, rv));
u64 km0 = (u64)_mm256_extract_epi64(p8, 0), km1 = (u64)_mm256_extract_epi64(p8, 2);
u64 bm0 = (u64)_mm256_extract_epi64(b8, 0), bm1 = (u64)_mm256_extract_epi64(b8, 2);
for (int i = 0; i < 4; i++) lrz[(km0 >> (8 * i)) & 255u] = (u8)(bm0 >> (8 * i));
for (int i = 0; i < 4; i++) lrz[(km1 >> (8 * i)) & 255u] = (u8)(bm1 >> (8 * i));
}
if (q > 1) prevz = lzk[q - 1] >> 8;
for (; q < sn; q++) {
const u32 v = lzk[q], zv = v >> 8;
if (zv != prevz) { prevz = zv; rk++; }
lrz[v & 255u] = (u8)((rk - 1u) ^ 0x80u);
}
}
leaf_sort(lk, sn);
for (int q = 0; q < sn; q++) {
const int sr = (int)(lk[q] & 255u);
ltmp[2 * q] = S[2 * (l + sr)];
ltmp[2 * q + 1] = S[2 * (l + sr) + 1];
lxb[q] = lrx[sr]; lzb[q] = lrz[sr];
}
{
const __m256i v7 = _mm256_set1_epi8(0x7F);
for (int k = sn; k < 288; k += 32) {
_mm256_storeu_si256((__m256i *)(lxb + k), v7);
_mm256_storeu_si256((__m256i *)(lzb + k), v7);
}
}
{
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=1;
for(;q+3<sn;q+=4){
int G[4];
for(int u=0;u<4;u++){int t=q+u;if((lk[t]>>8)!=(lk[t-1]>>8))g=t;G[u]=g;}
__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<=G[0];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(G[3]-k<=32){
if(k<G[3]){
__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++){
__m256i m=_mm256_cmpgt_epi8(_mm256_set1_epi8((char)(G[u]-k)),idxv);
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))));
}
}
}else{
#pragma GCC unroll 4
for(int u=0;u<4;u++){
int t=k;
#pragma GCC unroll 1
for(;t+32<=G[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<G[u]){__m256i x=_mm256_load_si256((const __m256i*)(lxb+t)),z=_mm256_load_si256((const __m256i*)(lzb+t));__m256i m=_mm256_cmpgt_epi8(_mm256_set1_epi8((char)(G[u]-t)),idxv);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 a01=_mm256_hadd_epi32(_mm256_sad_epu8(A[0],zero),_mm256_sad_epu8(A[1],zero));
__m256i a23=_mm256_hadd_epi32(_mm256_sad_epu8(A[2],zero),_mm256_sad_epu8(A[3],zero));
__m256i all=_mm256_hadd_epi32(a01,a23);
__m128i sums=_mm_add_epi32(_mm256_castsi256_si128(all),_mm256_extracti128_si256(all,1));
ltmp[2*q]+=(u32)_mm_extract_epi32(sums,0);ltmp[2*(q+1)]+=(u32)_mm_extract_epi32(sums,1);
ltmp[2*(q+2)]+=(u32)_mm_extract_epi32(sums,2);ltmp[2*(q+3)]+=(u32)_mm_extract_epi32(sums,3);
}
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 = _mm256_cmpgt_epi8(_mm256_set1_epi8((char)(g - k)), idxv);
__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;
}
}
for (int k = 0; k < sn; k++) { S[2 * (l + k)] = ltmp[2 * k]; S[2 * (l + k) + 1] = ltmp[2 * k + 1]; }
return 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 *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 *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 *Q = RC[out]; for (int k = l; k < r; k++) zadd<LV>(W_R(Q[2 * k + 1])); }
return out;
}
{
const u64 *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 *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();
memset(H32, 0, (size_t)(n + 1) * 4);
memset(CNT, 0, 1024 * 4);
bool wide_z = false;
for (int i = 0; i < n; i++) {
u32 h = H32[z[i]];
if ((h & 0xFFFu) != 0xFFFu) H32[z[i]] = h + 1; else wide_z = true;
CNT[x[i] >> 10]++;
}
{
__m256i carry = _mm256_setzero_si256();
int v = 0;
for (; v + 8 <= n + 1; v += 8) {
__m256i o = _mm256_loadu_si256((const __m256i *)(H32 + v));
__m256i t = _mm256_add_epi32(o, _mm256_slli_si256(o, 4));
t = _mm256_add_epi32(t, _mm256_slli_si256(t, 8));
t = _mm256_add_epi32(t, _mm256_shuffle_epi32(_mm256_permute2x128_si256(t,t,0x08),0xff));
__m256i total = _mm256_add_epi32(t, carry);
__m256i ex = _mm256_sub_epi32(total, o);
_mm256_storeu_si256((__m256i *)(H32 + v), _mm256_slli_epi32(ex,12));
carry = _mm256_shuffle_epi32(_mm256_permute2x128_si256(total,total,0x11),0xff);
}
u32 acc = (u32)_mm256_extract_epi32(carry,0);
for (; v <= n; v++) { u32 c=H32[v]&0xfffu;H32[v]=acc<<12;acc+=c; }
}
if (wide_z) {
memset(P1, 0, (size_t)(n+1)*sizeof(u64));
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)sum<<32;sum+=c;}
}
static u64 SCT[2 * MAXN];
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) {
for (int i = 0; i < n; i++) {
if (i + 96 < n) { __builtin_prefetch(&CNT[x[i + 96] >> 10]);
__builtin_prefetch(&SCT[2 * (size_t)CNT[x[i + 96] >> 10]]); }
u32 T,R;
if constexpr(decltype(wide_tag)::value) {
if(i+48<n) __builtin_prefetch(&P1[z[i+48]]);
u64 h=P1[z[i]]++; T=(u32)(h>>32); R=T+(u32)h;
} else {
if(i+48<n) __builtin_prefetch(&H32[z[i+48]]);
u32 zv=z[i],h=H32[zv]; T=h>>12;R=T+(h&0xFFFu);
if((h&0xFFFu)!=0xFFFu)H32[zv]=h+1;
}
u64 record = ((u64)T << 40) | ((u64)R << 20) | (u64)x[i];
const u32 t = CNT[x[i] >> 10]++;
_mm_storeu_si128((__m128i *)(void *)(SCT + 2 * t),
_mm_set_epi64x((long long)record, (long long)(((u64)y[i] << 40) | ((u64)i << 20))));
}
};
if(wide_z)scatter(std::true_type{});else scatter(std::false_type{});
{
u64 *D = RC[0];
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[SCT[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[SCT[2*t+1]&1023u]++;
_mm_storeu_si128((__m128i*)(D+2*p),_mm_loadu_si128((const __m128i*)(SCT+2*t)));}
continue;
}
memset(C16, 0, 1024 * 2);
for (int t = lo; t < hi; t++) C16[SCT[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[SCT[2 * t + 1] & 1023u]++;
_mm_storeu_si128((__m128i *)(void *)(D + 2 * p),
_mm_loadu_si128((const __m128i *)(const void *)(SCT + 2 * t)));
}
}
}
int bb = (n <= 262144) ? cdq<3, 64, 0>(0, n, 0)
: (g_rootout = out, cdq<4, 256, 0, true>(0, n, 0));
if (bb >= 0) {
const u64 *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 | 118.418 ms | 49 MB + 800 KB | Accepted | Score: 100 | 显示更多 |