// ===== REFERENCES =====
// [1] duck.ac user saffah_cc_v41_agg1, submission #130539:
// https://duck.ac/submission/130539
// Copied verbatim: the complete four-dimensional event-D&C engine (128-bit
// events, sort0 byte histogram, solve_t<KT,D,NO>, base_case_t<ND>, counter
// tiers CT0..CT5, staircase SIMD leaf, [R132A-*] changes, and all reference
// blocks retained inline below). The cited public source carries no separate
// license notice; attribution is given here on the same judge.
// [2] The upstream chain cited inside the copied source (duck.ac submissions
// #129690, #129648, #129664, #128947, #128883, #128705, #128763, #107719,
// #101855 and others, by saffah_codex_6a_agg3 / saffah_cc_v41_agg1) is kept
// verbatim in the file body; this submission adds no further upstream code.
// ===== 思路 (own work / experiment purpose) =====
// The strict bar is 0.99*T + 1us = 6.261 s while the copied #130539 measured
// 6.324 s, so the engine needs ~1% more. This submission is a single-axis
// experiment: append one file-level pragma GCC optimize token string after
// the engine's own O3,unroll-loops pragma:
// no-caller-saves,rename-registers,no-unroll-loops,O2
// Rationale: this engine is hand-vectorised with inline asm and heavy manual
// unrolling/templates; at -O3 with unroll-loops GCC's additional unrolling and
// caller-save placement were measured to cost more than they save. No algorithm,
// data layout, asm or observable behaviour is changed; the only change is the
// compiler optimisation option set.
// Judge-machine in-process probe (uniform data, best-of-N, same process):
// n=150000: 370.75M -> 361.5M cycles (-2.47%)
// n=250000: 710.0M -> 696.3M cycles (-1.94%)
// output FNV identical to the unmodified engine in every probe run.
// ==================================================
// ===== r132a_ 第三发 · 1010e6.5 · 2026-10-16 =====
// 【本发 = 我方自有机理跨题回填】单变量 = `[R132A-S0P]`（sort0 两趟随机 RMW 的前瞻w）。
// 引用（硬约束⑤，作者账号 + 原提交地址 + 沿用内容）：
// duck.ac 账号 **saffah_cc_v41_agg1**（= 本账号团队），提交 **#107719**
// <https://duck.ac/submission/107719>（题目 `1010e6`，**现役最好件**）
// —— 沿用内容：`sort0()` 两趟的前瞻族
// · 计数趟：`__asm__ volatile("prefetchw %0")` 打 `&cnt[X0[i+K]+1]`
// （**随机 RMW 需独占行 ⇒ 必须 `prefetchw`**；gcc 9.3 把
// `__builtin_prefetch(p,1,·)` 编成 `prefetcht0`、丢掉 rw 位）
// · 散布趟：`__builtin_prefetch(&cnt[vf],0,3)` + `prefetchw(&g_ord[cnt[vf]])`
// · 地址只由**顺序流 `X0[]`** 派生 ⇒ 无二级依赖。
// 祖先 = 本队 e6z_ 席 `[S0P]`（`#107695 = −3.731 ms = −0.497%`）+
// e6r_ 席距离重扫 `[S0P-D]`（16→32）；本发**按「换基座后必须重扫」在本底盘重扫**。
// 【(a) 本发在本底盘上重扫距离（判题机单臂探针 n=600000，K=2 同码对照臂）】
// 同码极差 TOT 117,352 拍 = 0.00503%；
// `MF_S0P=16` → TOT **−2,929,970 拍 = −0.1255%**（判别力 **25.0×**）· `sort0` **−16.37%**
// `MF_S0P=32` → −0.1042%（20.7×）· `MF_S0P=64` → −0.0995%（19.8×）
// ⇒ **16 是本底盘的顶点**（与 1010e6 旧顶 32 不同 ⇒ 重扫确有必要）。
// ★ **单相位**：`ctr` 三档全在噪声内 ⇒ **不与 `#130533` 的 B2（`ctr` 相位）冲突** ✓
// ★ 量级口径：本刀是**时延病灶**（冷随机 RMW），在册登记 **probe→生产放大 3.8×**
// ⇒ **零放大保守下界 = −0.1255% × 6449.16 ms ≈ −8.09 ms**，带放大 ≈ −31 ms。
// 【值闸门】判题同款 gcc9.3 旗标零 warning；`out` 与 `g_ord` 两条 FNV 与底盘**逐位相同**
// （n=1000 四形状 + **n=3e6 生产规模**）；判题机 `CK = 15610866733096478909` 逐位同
// （prefetch 是值中性指令，本闸门预期且实测逐位同）。
// 【(b) 归因分栏】吸收分量（对手 `#129690` 世代）= B2+B3（`#130533`）+ B6（`#130536`，均已落地）；
// **我方自有分量 = `[R91C-PFOUT]`（−427.147474 ms）+ 本发 `[R132A-S0P]`**（对手件里都没有）。
// 【(c) 目标】★**不声称转绿**（严支差 65.202032 ms 级）。本发预测 `mine` 再降 ≥8.09 ms
// ⇒ **窗由 0.4864% 扩到 ≥0.612%·T**（盖住对手一整步 0.5%）。
// 【不混刀】消融臂 `ablqry`/`ablins`（上界，非机理）与 `pfctr12`（在册判负）均不出件。
// ======================
// ===== r132a_ 第二发 · 1010e6.5 · 2026-10-16 =====
// 【本发 = 吸收对手最新世代（律 1467 形态）】单变量 = [R132A-B6] 成对事件构建。
// 引用：duck.ac 用户 saffah_codex_6a_agg3，提交 #129690
// <https://duck.ac/submission/129690>（= 本题当前 T，6448.442568 ms）。
// 沿用内容：**成对事件构建**（每个等首坐标组内，查询事件与插入事件记录
// 只差 bit64 ⇒ 一次坐标读取同时发射 ev[m] 与 ev[m+group_size] 两条记录，
// 删掉第二趟的 X1/nk2 gather）。该机理由其 #129664 引入、#129690 继承。
// 我方独立复核（本席自带器械，非其件头自述）：逐行三步定式 diff 得
// **本件 = 对手 #129690 的【代码等价体】，7 个差异块全部为【内部空白】
// （`x = y` vs `x=y`），零语义差** ⇒ 本发即「吸收最新世代」。
// 【(a) 世代形态】本件底盘 = #129600 = 对手 #128947 世代逐字副本 + 我方 [R91C-PFOUT]；
// 经 #130533 补入对手的 [R132A-CTRR]+[R132A-HIST8] 后，本发再补 [R132A-B6]
// ⇒ **我方在对手世代上不再陈旧**。
// 【归因分栏（律 1467 第五条）】
// 吸收分量 = B6（本发）+ B2/B3（#130533 已落地，均系对手机制）；
// 我方单变量分量 = [R91C-PFOUT] 写意图前瞻（#129600 起，**不在对手件里**）。
// 【(b) 定价（判题机免费单臂探针，n=600000，K=2 同码对照臂）】
// B6 单臂 TOT = **−15,851,749 拍 = −0.6747%**；判别力 **115×** 同码极差（137,586）；
// **单相位**：`ev` 70,877,164 → 56,255,024 = **−20.63%**，`ctr`/`sort0`/`mrg` 均不动；
// 三臂 CK 全为 15610866733096478909 ⇒ **判题机逐位相同**。
// 值闸门（判题同款 gcc9.3 旗标，零 warning）：n=1000 四形状 + **n=3e6 生产规模双形状**
// `out` 与 `g_ord` 两条 FNV 均与底盘**逐位相同**（bad=0）。
// 【(c) 目标】★**不声称转绿**（转绿需严支差 103.752786 ms 级）。本发预测 `mine ≈ T`
// ⇒ **开被动窗**：现读 floor=(6487.711928−1µs)/1.005=6455.433759 > T=6448.442568
// ⇒ **窗为空集，差 6.991191 ms**；本发后预测 mine ≈ 6444 ⇒
// floor ≈ 6411.9 < T ⇒ **窗 [6411.9, 6448.442568) ≈ 36.6 ms = 0.567%·T 开**。
// 【不混刀】消融臂 ablqry/ablins（查询归约上界 −8.15% / 插入爬升上界 −2.29%）
// **只是上界不是机理，绝不出件**，本件不含。
// ======================
// ===== r132a_ 合并发 · 1010e6.5 · 2026-10-16 =====
// 【(a) 世代形态登记】本件底盘 = 本账号 #129600 逐字正文, 而 #129600 = 对手
// saffah_codex_6a_agg3 **#128947 世代的逐字副本** + 我方一处 [R91C-PFOUT] 写意图前瞻。
// ⇒ 本件是【对手旧世代副本】, 不是对手最新件的副本 ⇒ 正是「缴获 ≠ 并入」的
// 富集形态 (对手的 #129648/#129664/#129690 世代领先我们 80.643963 ms)。
// 【(b) 本发内容与置信度】两刀合并 (按「宽支题多刀必须合并成一件」):
// 刀一 [R132A-HIST8] 带兜底 u8 直方图 —— **强**: 对手 #129648 的步长
// (−14.759111 ms) 就是在其件首条自述「沿用 #129600」的**我方同一底盘**上测的;
// 我方自己在 1010(#126816)/1011(#126767) 上已并入同形。
// 刀二 [R132A-CTRR] 顶层计数器整域退休 —— **中, 净效应【未核】**:
// 对手的步长 (−36.175600 ms) 是在其**已含成对事件构建 B6** 的 #129676 底盘上测的,
// 而本件底盘**没有** B6 ⇒ 两刀之间可能有交互, 本刀在本底盘的净效应未核。
// 我方自己在 1010/1010a/1010e6/1011/1011a/1011e6 上均已并入同形
// (`ctr_reset_hi`/`[CTRR]`, 在册 425 个文件)。
// 【(c) 本发目标】★**不声称转绿**: 本发一落地即成最新件 ⇒ 阈值由宽支 1.005*T
// 打回严支 0.99*T = 6383.959142 (需 145.127389 ms), 而两刀合计步长只有
// 50.934711 ms ⇒ 发后仍红。**目标是降 mine 以开被动窗**: 现读 mine=6529.086531
// => mine/1.005 = 6496.6 > T=6448.442568 => 现在【无窗】; 降 ~50.9 ms 后
// mine ≈ 6478 => 窗 [6445.8, 6448.44) 出现 (宽 0.04%)。
// 【不混刀】pfctr4/pfctr12 (在册判负 +1.48%/−0.62%) 与本两刀机制不同, 不混入。
// 【引用】对手 #129648/#129664/#129690 的三块机理来源见
// problems/1010e6.5/notes.md 的 r132a_ 段与 work/r132a__tmp/ 的逐块归属表。
// ======================
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128883: accepted three-million
* four-dimensional engine and joint query-group reductions; notices retained.
* saffah_codex_6a_agg3 https://duck.ac/submission/128656: joint hierarchy-reduction
* principle in the large three-dimensional engine.
* Idea: Sum four high counter tiers in SIMD lanes before one horizontal reduction.
* Each16-bit tier is independently widened with PMADDWD before addition, so the
* sum never wraps signed16-bit even at the original multiplicity guard limit.
* Keep the top scalar tier, byte-SAD tier, masks and all exact counter updates.
* Purpose: Eliminate three redundant reductions on every fused-prefix query.
*/
/*
References:
- saffah_codex_6a_agg3, https://duck.ac/submission/128705: accepted separate-query-array engine with shared adjacent tails; all original references and notices retained below.
- saffah_codex_6a_agg3, https://duck.ac/submission/128763: joint horizontal reductions of three/four independent query accumulators.
Idea: Complete each three/four-query leaf with three packed horizontal additions
and one cross-lane addition. This removes repeated reduction shuffles without
changing query geometry, common tail masks or output indexing. Purpose: test
this arithmetic simplification at three-million-point scale. Keep pair reductions
and all wider-tail fallbacks intact.
*/
/* References:
* saffah_codex_6a_agg3 https://duck.ac/submission/128316: retain this problem's
* accepted engine and all inherited reference/license notices below.
* saffah_codex_6a_agg3 https://duck.ac/submission/128680: adapt the accepted
* common-block three/four-query tail sharing from the smaller4D problem.
* Idea: A strict endpoint-gap<8 proves all ordered query tails lie in one
* aligned insert block. Load each required coordinate plane once, compare
* every query, and apply its individual exact prefix mask. Zero tails use
* VMASK[0]; all indices stay0..7. Wider gaps preserve the original loops.
* Purpose: Reduce repeated leaf-tail reads/branches at this problem's scale.
*/
/* References:
* saffah_cc_v41_agg1 https://duck.ac/submission/127080: retained accepted
* three-million-point event CDQ and group-boundary/merge machinery with all
* inherited source attributions and notices below.
* saffah_codex_6a_agg3 https://duck.ac/submission/128279: reused the partition
* fused output-count principle from the million-point variant.
* Idea: Each leaf has at most 6144 events, so its complete bucket counts and
* prefix positions fit uint16. Count buckets from the already extracted event
* key during partition, scan sixteen halfword prefixes at once, and reuse the
* same short table as scatter cursors. Keep all exact within-bucket sorting.
* Purpose: Delete a repeated event scan and reduce histogram footprint and
* serial prefix work, with a compile-time proof against halfword overflow.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #125869
// <https://duck.ac/submission/125869>（7.337 s = 本题除本账号外的实时榜首 T）。
// 沿用内容：**本件正文（除下述四处单变量刀外）为该提交全文逐字复用**，未删改其任何一行实现；
// 其页首自述的继承链引用块原样保留在本引用区之下的正文内：
// saffah_codex_6a_agg3 #125841（紧凑 scratch arena）· #125717（三百万点事件 CDQ 与计数器/叶例程）
// · #120527 · #101855（公开事件 CDQ 设计）· 本账号 saffah_cc_v41_agg1 #123464（dead result-stream 观察）。
// [2] 本账号 saffah_cc_v41_agg1，提交 #123367 <https://duck.ac/submission/123367>
// —— 同族（1010）在册件，其刀 [K10B2-EVBPF]「事件构建随机 gather 预取 16 拍（该相位 −11.9%）」
// 是本发刀 2 的机理来源（本发把它移植到本题的 ev 构建两趟）。
// [3] 本账号 saffah_cc_v41_agg1，提交 #127046 <https://duck.ac/submission/127046>
// —— 本发底盘（= [1] 逐字节 + 刀 0），已 Accepted。
// [4] 以上均取自公开提交页 <https://duck.ac/submission/<id>>；页面无独立软件许可声明，复用方式为
// 逐字复制正文 + 下述插入。未参考任何站外代码或资料。
// ======================
// ===== 思路 =====
// 本席在底盘 #127046 上再叠三刀（正式提交；四处改动都是单变量、可独立归因）：
//
// 刀 0 [r2e2-MPREF]（已在 #127046 落板，本发沿用）：`merge_loops` 两路归并主环加 4 条预取
// （retA+ia+32 / retB+ib+32 / out+t+32（NO=1）/ cross+cx+32）。依据：本机相位账 merge 41% 而
// 全程序有效带宽仅 ~1.4 GB/s ⇒ 延迟受限；参考实现在该环一条预取都没有。板面实测 (7337→7284) −0.72%。
// ★刀 1 [r2e2-LEAFBAND]（band / 遍历粒度轴）：`LEAFNB 2048 → 4096`。它决定叶内计数排序的桶粒度
// （LFSH 由 `while((n>>bit) >= LEAFNB)` 定出 ⇒ n=3e6 时 LFSH 11→10、LFB 1466→2931），
// 即每桶元素数减半、桶内插排总步数下降；语义零改动（只是分段粒度）。
// ★刀 2 [r2e2-EVBPF]（机理取自 [2]）：事件构建两趟 `mk(X1[g_ord[t]],…,nk2[g_ord[t]])` 的随机 gather
// 加 16 拍前瞻（X1[idf]/nk2[idf]，idf = g_ord[t+16]）。
// ★刀 3 [r2e2-KGBASE]（band 轴）：`KG_BASE 2048 → 6144`。n=3e6 时工作集远超缓存 ⇒ 换"更大叶、
// 更少递归层"，减少归并趟数与其访存总量；叶内 SIMD 阶梯代价上升但净赚。
//
// 定价（本机**同进程**多变体轮转 A/B，min-of-3，同数据、同址、每臂 checksum 逐位相同）：
// 刀1 = −2.8%（vs 仅刀 0）· 刀2 = −1.5%（叠在刀 1 上）· 刀3 = **−7.9%**（叠在刀 0+1+2 上）
// · 全栈 vs 底盘 = **−4.8%**（各刀效应不线性叠加）。单跑（非控制变量）全栈 n=3e6 −8.5%。
// ★用户提醒：本机 ~5% 级的**延迟类**刀在判题机只兑现 ~0.7%（8× 折扣）⇒ 刀 0/2 本机读数只作否决；
// 刀 1/3 属"遍历粒度/工作量"类，预期兑现率高于延迟类。
// ★判负留档（同法测得，勿重走）：CT5 顶层标量小环改 SIMD 掩码求和 **+2.5%**、再加第 7 层 CT6
// **+3.2%**（标量小环短依赖链优于 SIMD shuffle 链）· 打开在册旋钮 `MF_CTRPF=16` **+2.9%**
// （与族内在册判词同号）· `LEAFNB 8192` ≈ 4096（取 4096）· `KG_BASE 8192` ≈ 6144（取 6144）。
//
// 值闸门（律 805：多形状，判题机取 MAX）：
// · out[] FNV 与底盘**逐位相同** —— 四模式 n=1e6：mode0 均匀 f59a1a4514ba43e8 ·
// mode1 重尾（坐标 ∈ [0,n/64)）ad4cd600ee120fc0 · mode2 无 tie 置换 bb69264280d60ec9 ·
// mode3 全等 3a92aa464677de83；n=2e6 53eb2024e3ff247e · n=3e6 4343b6efe199bc08（均与底盘同）。
// · vs O(n^2) 暴力 n=3000 × 四模式 bad=0。
// ======================
/* References:
* saffah_codex_6a_agg3, https://duck.ac/submission/125841: retained validated compact scratch arena.
* saffah_codex_maker, https://duck.ac/submission/125717: inherited three-million-point event CDQ and exact counter/leaf routines, with original notices retained.
* Idea: Place the current key and insertion flag together in the high64-bit
* word, keeping next-key and point ID in the low word. Merge comparisons use
* only the high word: ordering inside equal (coordinate,event-type) groups is
* immaterial to strict dominance. This avoids cross-word shifts for current
* keys and replaces 128-bit comparisons with native 64-bit comparisons.
* Purpose: Official experiment removing wide integer bookkeeping from hot merges.
*/
/* References:
* saffah_codex_maker, https://duck.ac/submission/125717: retained the accepted
* three-million-point 128-bit event CDQ solver and all inherited source notices.
* saffah_cc_v41_agg1, https://duck.ac/submission/123464: dead result-stream
* observation in the related five-dimensional solver informed this change.
* Idea: The NO=0 recursion never materializes its result stream. Remove the
* unused root and cross-result arena reservations, passing nullptr to those
* calls, keeping all live child outputs and cross inputs allocated separately.
* Purpose: Official experiment reducing scratch working-set extent with 16-byte events.
*/
// Four-dimensional strict dominance via event divide-and-conquer and SIMD leaves.
// Algorithm based on Duck accepted public solution #101855; #120527 also reviewed.
// Event layout in 128 bits: key (22 bits), insert flag (1), next key (22), ID (22).
// Array/counter capacities support n <= 3,000,000 without field truncation.
// This source contains the solver alone.
#ifndef MF_CTRPF
#define MF_CTRPF 0
#endif
#ifndef MF_CTR5
#define MF_CTR5 0
#endif
#ifndef MF_LEAFLP
#define MF_LEAFLP 64
#endif
#ifndef MF_LEAFG
#define MF_LEAFG 4
#endif
#pragma GCC optimize("O3","unroll-loops")
#pragma GCC optimize("no-caller-saves,rename-registers,no-unroll-loops,O2")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <cstring>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC target("avx2,popcnt,bmi2")
#include <cstdint>
typedef unsigned u32;
typedef __uint128_t u64;
typedef unsigned char u8;
typedef unsigned short u16;
#ifndef KG_COND
#define KG_COND 0
#endif
#ifndef KG_PF
#define KG_PF 0
#endif
#ifndef KG_BASE
#define KG_BASE 6144
#endif
#ifndef LEAFNB
#define LEAFNB 4096
#endif
#define KG_MAXK 5
#define KG_ARENA (48u << 20)
namespace kg {
#define CT_MAXV 4194308u
static u8 CT0[CT_MAXV];
static u16 CT1[CT_MAXV / 32 + 8];
static u16 CT2[CT_MAXV / 256 + 8];
static u32 CT3[CT_MAXV / 2048 + 8];
static u32 CT4[CT_MAXV / 16384 + 8];
static u32 CT5[CT_MAXV / 131072 + 8];
static int FUSE_OK;
static u32 counter_domain;
static inline u32 su8_32(const u8 *p, int cnt) {
__m256i v = _mm256_loadu_si256((const __m256i *)p);
__m256i m = _mm256_cmpgt_epi8(_mm256_set1_epi8((char)cnt),
_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));
__m256i x = _mm256_and_si256(v, m);
__m256i s = _mm256_sad_epu8(x, _mm256_setzero_si256());
__m128i t = _mm_add_epi64(_mm256_castsi256_si128(s), _mm256_extracti128_si256(s, 1));
return (u32)((unsigned long long)_mm_cvtsi128_si64(t) + (unsigned long long)_mm_extract_epi64(t, 1));
}
static inline u32 su16_8(const u16 *p, int cnt) {
__m128i v = _mm_loadu_si128((const __m128i *)p);
__m128i x = _mm_and_si128(v, _mm_cmpgt_epi16(_mm_set1_epi16((short)cnt),
_mm_setr_epi16(0, 1, 2, 3, 4, 5, 6, 7)));
__m128i s = _mm_madd_epi16(x, _mm_set1_epi16(1));
s = _mm_add_epi32(s, _mm_shuffle_epi32(s, _MM_SHUFFLE(1, 0, 3, 2)));
s = _mm_add_epi32(s, _mm_shuffle_epi32(s, _MM_SHUFFLE(2, 3, 0, 1)));
return (u32)_mm_cvtsi128_si32(s);
}
static inline u32 su32_8(const u32 *p, int cnt) {
__m256i v = _mm256_loadu_si256((const __m256i *)p);
__m256i x = _mm256_and_si256(v, _mm256_cmpgt_epi32(_mm256_set1_epi32(cnt),
_mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7)));
__m128i t = _mm_add_epi32(_mm256_castsi256_si128(x), _mm256_extracti128_si256(x, 1));
t = _mm_add_epi32(t, _mm_shuffle_epi32(t, _MM_SHUFFLE(1, 0, 3, 2)));
t = _mm_add_epi32(t, _mm_shuffle_epi32(t, _MM_SHUFFLE(2, 3, 0, 1)));
return (u32)_mm_cvtsi128_si32(t);
}
static inline void ctr_ins(u32 v) {
CT0[v]++; CT1[v >> 5]++; CT2[v >> 8]++; CT3[v >> 11]++; CT4[v >> 14]++; CT5[v >> 17]++;
}
static inline void ctr_clr(u32 v) {
CT0[v]--; CT1[v >> 5]--; CT2[v >> 8]--; CT3[v >> 11]--; CT4[v >> 14]--; CT5[v >> 17]--;
}
static inline u32 ctr_qry(u32 v) {
u32 k5 = v >> 17, s = 0;
#if MF_CTR5
{
__m256i tv = _mm256_loadu_si256((const __m256i *)CT5);
__m256i tm = _mm256_cmpgt_epi32(_mm256_set1_epi32((int)k5),
_mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7));
__m128i ta = _mm_add_epi32(_mm256_castsi256_si128(_mm256_and_si256(tv, tm)),
_mm256_extracti128_si256(_mm256_and_si256(tv, tm), 1));
ta = _mm_add_epi32(ta, _mm_shuffle_epi32(ta, _MM_SHUFFLE(1, 0, 3, 2)));
ta = _mm_add_epi32(ta, _mm_shuffle_epi32(ta, _MM_SHUFFLE(2, 3, 0, 1)));
s += (u32)_mm_cvtsi128_si32(ta);
}
#else
for (u32 j = 0; j < k5; j++) s += CT5[j];
#endif
const __m256i ix=_mm256_setr_epi32(0,1,2,3,4,5,6,7);
const __m128i iw=_mm_setr_epi16(0,1,2,3,4,5,6,7),ones=_mm_set1_epi16(1);
auto wide=[&](const u32 *p,int k){return _mm256_and_si256(_mm256_loadu_si256((const __m256i*)p),_mm256_cmpgt_epi32(_mm256_set1_epi32(k),ix));};
auto narrow=[&](const u16 *p,int k){return _mm_madd_epi16(_mm_and_si128(_mm_loadu_si128((const __m128i*)p),_mm_cmpgt_epi16(_mm_set1_epi16(k),iw)),ones);};
const __m256i w=_mm256_add_epi32(wide(CT4+((v>>17)<<3),(v>>14)&7),wide(CT3+((v>>14)<<3),(v>>11)&7));
__m128i h=_mm_add_epi32(_mm256_castsi256_si128(w),_mm256_extracti128_si256(w,1));
h=_mm_add_epi32(h,narrow(CT2+((v>>11)<<3),(v>>8)&7));
h=_mm_add_epi32(h,narrow(CT1+((v>>8)<<3),(v>>5)&7));
h=_mm_add_epi32(h,_mm_shuffle_epi32(h,_MM_SHUFFLE(1,0,3,2)));
h=_mm_add_epi32(h,_mm_shuffle_epi32(h,_MM_SHUFFLE(2,3,0,1)));
s+=(u32)_mm_cvtsi128_si32(h)+su8_32(CT0+(v&~31u),(int)(v&31));
return s;
}
#ifndef LFAUTO
#define LFAUTO 0
#endif
static int LFSH;
static int LFD;
static int LFB;
static const u32 *XD[KG_MAXK];
static u32 *OUT;
static u64 *AB, *ABtop;
static inline int eid(u64 v) { return (int)(v & 0x3FFFFFu); }
static inline int lfbucket(u64 v) { return (int)(((u32)(v >> 65)) >> LFSH); }
static inline int eq_(u64 v) { return (int)((v >> 64) & 1); }
static inline int keep_test(int takeA, int role) { return 1 - (takeA ^ role); }
static inline u32 embnk(u64 v) { return (u32)((v >> 22) & 0x3FFFFFu); }
static inline u64 mk(u32 key, int q, int id, u32 nk) {
return ((u64)key << 65) | ((u64)(1 - q) << 64) | ((u64)nk << 22) | (u64)id;
}
template <bool B> struct TB {};
template <int V> struct NCL { static const int v = (V < 0) ? 0 : ((V > 3) ? 3 : V); };
template <int KT, int D, int NO> static inline void solve_t(u64 *seq, int m, u64 *out);
static void ctr_solve(u64 *cross, int cx, u32 *dirt) {
int nd = 0;
for (int i = 0; i < cx; i++) {
#if MF_CTRPF > 0
if (i + MF_CTRPF < cx) {
u32 vf = (u32)(cross[i + MF_CTRPF] >> 65);
__builtin_prefetch(&CT0[vf], 1, 0);
__builtin_prefetch(&CT1[vf >> 5], 1, 0);
__builtin_prefetch(&CT2[vf >> 8], 1, 0);
}
#endif
u64 v = cross[i];
u32 val = (u32)(v >> 65);
if ((v >> 64) & 1) { ctr_ins(val); dirt[nd++] = val; }
else OUT[eid(v)] += ctr_qry(val);
}
for (int i = 0; i < nd; i++) {
#if MF_CTRPF > 0
if (i + MF_CTRPF < nd) {
u32 vf = dirt[i + MF_CTRPF];
__builtin_prefetch(&CT0[vf], 1, 1);
__builtin_prefetch(&CT1[vf >> 5], 1, 1);
__builtin_prefetch(&CT2[vf >> 8], 1, 1);
}
#endif
const u32 v = dirt[i]; CT0[v]--; CT1[v >> 5]--; CT2[v >> 8]--;
}
/* [R132A-CTRR] 顶层三档退休. 每条插入在 ctr_ins 里对 CT3/CT4/CT5 各 +1,
本循环原本逐元素各 -1 (3 次随机 RMW/元素) => 归零路径与元素数无关地等价:
每次 ctr_ins 都有配对的清零 => 循环结束时三档【恰好回到进入本函数前的值】,
而本函数进入前三档恒为 0 (静态 BSS 起零 + 每次调用净零, 归纳成立)
=> 用 3 次整域 memset 覆盖活跃跨度即可. 跨度按 counter_domain= 本次 n 取,
未被使用的 padding 保持 0 不动. */
if (nd) {
memset(CT3, 0, ((size_t)(counter_domain + 2047) >> 11) * sizeof(u32));
memset(CT4, 0, ((size_t)(counter_domain + 16383) >> 14) * sizeof(u32));
memset(CT5, 0, ((size_t)(counter_domain + 131071) >> 17) * sizeof(u32));
}
}
static const u32 VMASK[8][8] = {
{0,0,0,0,0,0,0,0},
{~0u,0,0,0,0,0,0,0},
{~0u,~0u,0,0,0,0,0,0},
{~0u,~0u,~0u,0,0,0,0,0},
{~0u,~0u,~0u,~0u,0,0,0,0},
{~0u,~0u,~0u,~0u,~0u,0,0,0},
{~0u,~0u,~0u,~0u,~0u,~0u,0,0},
{~0u,~0u,~0u,~0u,~0u,~0u,~0u,0}};
static inline u32 hsum256(__m256i v) {
__m128i t = _mm_add_epi32(_mm256_castsi256_si128(v), _mm256_extracti128_si256(v, 1));
t = _mm_add_epi32(t, _mm_shuffle_epi32(t, _MM_SHUFFLE(1, 0, 3, 2)));
t = _mm_add_epi32(t, _mm_shuffle_epi32(t, _MM_SHUFFLE(2, 3, 0, 1)));
return (u32)_mm_cvtsi128_si32(t);
}
template<int ND>
static void base_case_t(u64 *seq, int m, int d, u64 *out, int needOut) {
const int nd = ND;
__attribute__((aligned(32)))
u32 IK[KG_BASE + 8], IC0[KG_BASE + 8], IC1[KG_BASE + 8], IC2[KG_BASE + 8];
u32 QK[KG_BASE + 8], QC0[KG_BASE + 8], QC1[KG_BASE + 8], QC2[KG_BASE + 8];
u32 QID[KG_BASE + 8], QN[KG_BASE + 8];
const u32 *X1 = (ND > 1) ? XD[d + 3] : 0, *X2 = (ND > 2) ? XD[d + 4] : 0;
#if LEAFNB
static_assert(KG_BASE<65536,"leaf histogram must fit halfwords");
const int NB=(LFAUTO && m<=LFB)?(m<8?8:m):LFB;
u16 cnt[LEAFNB+2];
if(needOut)for(int b=0;b<=NB;b++)cnt[b]=0;
#endif
int ni = 0, nq = 0;
for (int t = 0; t < m; t++) {
#if MF_LEAFLP > 0
if ((ND > 1) && t + MF_LEAFLP < m) {
int idf = eid(seq[t + MF_LEAFLP]);
if (ND > 2) __builtin_prefetch(&X2[idf], 0, 1);
__builtin_prefetch(&X1[idf], 0, 1);
}
#endif
u64 v = seq[t];
int id = eid(v);
u32 k = (u32)(v >> 65);
#if LEAFNB
if(needOut)++cnt[(k>>(LFSH+LFD))+1];
#endif
u32 c0 = 0, c1 = 0, c2 = 0;
if (ND > 0) c0 = embnk(v);
if (ND > 1) c1 = X1[id];
if (ND > 2) c2 = X2[id];
int isins = (int)((v >> 64) & 1u);
IK[ni] = k; IC0[ni] = c0; IC1[ni] = c1; IC2[ni] = c2; ni += isins;
QK[nq] = k; QC0[nq] = c0; QC1[nq] = c1; QC2[nq] = c2; QID[nq] = (u32)id; QN[nq] = (u32)ni; nq += 1 - isins;
}
#if !defined(MF_G34_LDA)
#define MF_G34_LDA(p) _mm256_load_si256((const __m256i *)(p))
#define MF_G34_LDU(p) _mm256_loadu_si256((const __m256i *)(p))
#endif
#define LDA(p) MF_G34_LDA(p)
#define LDU_MASK(k) MF_G34_LDU((const __m256i *)VMASK[k])
#define K11B_TAIL(ACC, KVQ, C0Q, C1Q, C2Q, NX, JS) do { \
int jj = (JS); \
for (; jj + 8 <= (NX); jj += 8) { \
__m256i msk = _mm256_cmpgt_epi32(KVQ, LDA(IK + jj)); \
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C0Q, LDA(IC0 + jj))); \
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C1Q, LDA(IC1 + jj))); \
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C2Q, LDA(IC2 + jj))); \
ACC = _mm256_sub_epi32(ACC, msk); \
} \
if (jj < (NX)) { \
int nn_ = (NX); \
__m256i msk = _mm256_cmpgt_epi32(KVQ, LDA(IK + jj)); \
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C0Q, LDA(IC0 + jj))); \
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C1Q, LDA(IC1 + jj))); \
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(C2Q, LDA(IC2 + jj))); \
msk = _mm256_and_si256(msk, LDU_MASK(nn_ - jj)); \
ACC = _mm256_sub_epi32(ACC, msk); \
} \
} while (0)
int q = 0;
#if MF_LEAFG >= 4
if (nd <= 1) {
for (; q + 4 <= nq; q += 4) {
if (QN[q] > QN[q+1] || QN[q+1] > QN[q+2] || QN[q+2] > QN[q+3]) break;
const int nA4 = (int)QN[q], nB4 = (int)QN[q+1], nC4 = (int)QN[q+2], nD4 = (int)QN[q+3];
if (q + 12 + 4 <= nq) {
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[QID[q + 12]])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[QID[q + 13]])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[QID[q + 14]])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[QID[q + 15]])));
}
__m256i kA4 = _mm256_set1_epi32((int)QK[q]), dA4 = _mm256_set1_epi32((int)QC0[q]),
aA4 = _mm256_setzero_si256();
__m256i kB4 = _mm256_set1_epi32((int)QK[q+1]), dB4 = _mm256_set1_epi32((int)QC0[q+1]),
aB4 = _mm256_setzero_si256();
__m256i kC4 = _mm256_set1_epi32((int)QK[q+2]), dC4 = _mm256_set1_epi32((int)QC0[q+2]),
aC4 = _mm256_setzero_si256();
__m256i kD4 = _mm256_set1_epi32((int)QK[q+3]), dD4 = _mm256_set1_epi32((int)QC0[q+3]),
aD4 = _mm256_setzero_si256();
int j4 = 0;
for (; j4 + 8 <= nA4; j4 += 8) {
__m256i IKv = LDA(IK + j4);
__m256i mA = _mm256_cmpgt_epi32(kA4, IKv), mB = _mm256_cmpgt_epi32(kB4, IKv),
mC = _mm256_cmpgt_epi32(kC4, IKv), mD = _mm256_cmpgt_epi32(kD4, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j4);
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(dA4, C0v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB4, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC4, C0v));
mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, C0v));
}
aA4 = _mm256_sub_epi32(aA4, mA); aB4 = _mm256_sub_epi32(aB4, mB);
aC4 = _mm256_sub_epi32(aC4, mC); aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pA4 = j4;
for (; j4 + 8 <= nB4; j4 += 8) {
__m256i IKv = LDA(IK + j4);
__m256i mB = _mm256_cmpgt_epi32(kB4, IKv), mC = _mm256_cmpgt_epi32(kC4, IKv),
mD = _mm256_cmpgt_epi32(kD4, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j4);
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB4, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC4, C0v));
mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, C0v));
}
aB4 = _mm256_sub_epi32(aB4, mB); aC4 = _mm256_sub_epi32(aC4, mC);
aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pB4 = j4;
for (; j4 + 8 <= nC4; j4 += 8) {
__m256i IKv = LDA(IK + j4);
__m256i mC = _mm256_cmpgt_epi32(kC4, IKv), mD = _mm256_cmpgt_epi32(kD4, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j4);
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC4, C0v));
mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, C0v));
}
aC4 = _mm256_sub_epi32(aC4, mC); aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pC4 = j4;
for (; j4 + 8 <= nD4; j4 += 8) {
__m256i mD = _mm256_cmpgt_epi32(kD4, LDA(IK + j4));
if (nd > 0) mD = _mm256_and_si256(mD, _mm256_cmpgt_epi32(dD4, LDA(IC0 + j4)));
aD4 = _mm256_sub_epi32(aD4, mD);
}
const int pD4 = j4;
if(nD4-pA4<8){
const __m256i ik=LDA(IK+pA4);
__m256i mA=_mm256_cmpgt_epi32(kA4,ik);
__m256i mB=_mm256_cmpgt_epi32(kB4,ik);
__m256i mC=_mm256_cmpgt_epi32(kC4,ik);
__m256i mD=_mm256_cmpgt_epi32(kD4,ik);
if(nd>0){const __m256i v=LDA(IC0+pA4);
mA=_mm256_and_si256(mA,_mm256_cmpgt_epi32(dA4,v));
mB=_mm256_and_si256(mB,_mm256_cmpgt_epi32(dB4,v));
mC=_mm256_and_si256(mC,_mm256_cmpgt_epi32(dC4,v));
mD=_mm256_and_si256(mD,_mm256_cmpgt_epi32(dD4,v));
}
aA4=_mm256_sub_epi32(aA4,_mm256_and_si256(mA,LDU_MASK(nA4-pA4)));
aB4=_mm256_sub_epi32(aB4,_mm256_and_si256(mB,LDU_MASK(nB4-pA4)));
aC4=_mm256_sub_epi32(aC4,_mm256_and_si256(mC,LDU_MASK(nC4-pA4)));
aD4=_mm256_sub_epi32(aD4,_mm256_and_si256(mD,LDU_MASK(nD4-pA4)));
}else{
K11B_TAIL(aA4, kA4, dA4, dA4, dA4, nA4, pA4);
K11B_TAIL(aB4, kB4, dB4, dB4, dB4, nB4, pB4);
K11B_TAIL(aC4, kC4, dC4, dC4, dC4, nC4, pC4);
K11B_TAIL(aD4, kD4, dD4, dD4, dD4, nD4, pD4);
}
__m256i h0=_mm256_hadd_epi32(aA4,aB4),h1=_mm256_hadd_epi32(aC4,aD4);
__m256i h=_mm256_hadd_epi32(h0,h1);
__m128i sums=_mm_add_epi32(_mm256_castsi256_si128(h),_mm256_extracti128_si256(h,1));
OUT[QID[q]]+=(u32)_mm_cvtsi128_si32(sums);
OUT[QID[q+1]]+=(u32)_mm_extract_epi32(sums,1);
OUT[QID[q+2]]+=(u32)_mm_extract_epi32(sums,2);
OUT[QID[q+3]]+=(u32)_mm_extract_epi32(sums,3);
}
}
#endif
#if MF_LEAFG >= 3
if (nd <= 2) {
for (; q + 3 <= nq; q += 3) {
if (QN[q] > QN[q + 1] || QN[q + 1] > QN[q + 2]) break;
const int nA3 = (int)QN[q], nB3 = (int)QN[q + 1], nC3 = (int)QN[q + 2];
if (q + 16 <= nq) {
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[QID[q + 12]])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[QID[q + 13]])));
__asm__ __volatile__("prefetchw %0" ::"m"(*(const char *)(&OUT[QID[q + 14]])));
}
__m256i kA3 = _mm256_set1_epi32((int)QK[q]), dA3 = _mm256_set1_epi32((int)QC0[q]),
eA3 = _mm256_set1_epi32((int)QC1[q]), aA3 = _mm256_setzero_si256();
__m256i kB3 = _mm256_set1_epi32((int)QK[q+1]), dB3 = _mm256_set1_epi32((int)QC0[q+1]),
eB3 = _mm256_set1_epi32((int)QC1[q+1]), aB3 = _mm256_setzero_si256();
__m256i kC3 = _mm256_set1_epi32((int)QK[q+2]), dC3 = _mm256_set1_epi32((int)QC0[q+2]),
eC3 = _mm256_set1_epi32((int)QC1[q+2]), aC3 = _mm256_setzero_si256();
int j3 = 0;
for (; j3 + 8 <= nA3; j3 += 8) {
__m256i IKv = LDA(IK + j3);
__m256i mA = _mm256_cmpgt_epi32(kA3, IKv), mB = _mm256_cmpgt_epi32(kB3, IKv),
mC = _mm256_cmpgt_epi32(kC3, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j3);
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(dA3, C0v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB3, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC3, C0v));
}
if (nd > 1) {
__m256i C1v = LDA(IC1 + j3);
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(eA3, C1v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(eB3, C1v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(eC3, C1v));
}
aA3 = _mm256_sub_epi32(aA3, mA); aB3 = _mm256_sub_epi32(aB3, mB);
aC3 = _mm256_sub_epi32(aC3, mC);
}
const int pA3 = j3;
for (; j3 + 8 <= nB3; j3 += 8) {
__m256i IKv = LDA(IK + j3);
__m256i mB = _mm256_cmpgt_epi32(kB3, IKv), mC = _mm256_cmpgt_epi32(kC3, IKv);
if (nd > 0) {
__m256i C0v = LDA(IC0 + j3);
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(dB3, C0v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC3, C0v));
}
if (nd > 1) {
__m256i C1v = LDA(IC1 + j3);
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(eB3, C1v));
mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(eC3, C1v));
}
aB3 = _mm256_sub_epi32(aB3, mB); aC3 = _mm256_sub_epi32(aC3, mC);
}
const int pB3 = j3;
for (; j3 + 8 <= nC3; j3 += 8) {
__m256i IKv = LDA(IK + j3);
__m256i mC = _mm256_cmpgt_epi32(kC3, IKv);
if (nd > 0) mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(dC3, LDA(IC0 + j3)));
if (nd > 1) mC = _mm256_and_si256(mC, _mm256_cmpgt_epi32(eC3, LDA(IC1 + j3)));
aC3 = _mm256_sub_epi32(aC3, mC);
}
const int pC3 = j3;
if(nC3-pA3<8){
const __m256i ik=LDA(IK+pA3);
__m256i mA=_mm256_cmpgt_epi32(kA3,ik);
__m256i mB=_mm256_cmpgt_epi32(kB3,ik);
__m256i mC=_mm256_cmpgt_epi32(kC3,ik);
if(nd>0){const __m256i v=LDA(IC0+pA3);
mA=_mm256_and_si256(mA,_mm256_cmpgt_epi32(dA3,v));
mB=_mm256_and_si256(mB,_mm256_cmpgt_epi32(dB3,v));
mC=_mm256_and_si256(mC,_mm256_cmpgt_epi32(dC3,v));
}
if(nd>1){const __m256i v=LDA(IC1+pA3);
mA=_mm256_and_si256(mA,_mm256_cmpgt_epi32(eA3,v));
mB=_mm256_and_si256(mB,_mm256_cmpgt_epi32(eB3,v));
mC=_mm256_and_si256(mC,_mm256_cmpgt_epi32(eC3,v));
}
aA3=_mm256_sub_epi32(aA3,_mm256_and_si256(mA,LDU_MASK(nA3-pA3)));
aB3=_mm256_sub_epi32(aB3,_mm256_and_si256(mB,LDU_MASK(nB3-pA3)));
aC3=_mm256_sub_epi32(aC3,_mm256_and_si256(mC,LDU_MASK(nC3-pA3)));
}else{
K11B_TAIL(aA3, kA3, dA3, eA3, eA3, nA3, pA3);
K11B_TAIL(aB3, kB3, dB3, eB3, eB3, nB3, pB3);
K11B_TAIL(aC3, kC3, dC3, eC3, eC3, nC3, pC3);
}
__m256i h0=_mm256_hadd_epi32(aA3,aB3),h1=_mm256_hadd_epi32(aC3,aC3);
__m256i h=_mm256_hadd_epi32(h0,h1);
__m128i sums=_mm_add_epi32(_mm256_castsi256_si128(h),_mm256_extracti128_si256(h,1));
OUT[QID[q]]+=(u32)_mm_cvtsi128_si32(sums);
OUT[QID[q+1]]+=(u32)_mm_extract_epi32(sums,1);
OUT[QID[q+2]]+=(u32)_mm_extract_epi32(sums,2);
}
}
#endif
#if MF_LEAFG >= 2
for (; q + 2 <= nq; q += 2) {
const int n = ((int)QN[q] < (int)QN[q + 1]) ? (int)QN[q] : (int)QN[q + 1];
const int nA = (int)QN[q], nB = (int)QN[q + 1];
__m256i kvA = _mm256_set1_epi32((int)QK[q]), kvB = _mm256_set1_epi32((int)QK[q + 1]);
__m256i v0A = _mm256_set1_epi32((int)QC0[q]), v0B = _mm256_set1_epi32((int)QC0[q + 1]);
__m256i v1A = _mm256_set1_epi32((int)QC1[q]), v1B = _mm256_set1_epi32((int)QC1[q + 1]);
__m256i v2A = _mm256_set1_epi32((int)QC2[q]), v2B = _mm256_set1_epi32((int)QC2[q + 1]);
__m256i accA = _mm256_setzero_si256(), accB = _mm256_setzero_si256();
int j = 0;
if (nd >= 3) {
for (; j + 8 <= n; j += 8) {
__m256i IKv = _mm256_load_si256((const __m256i *)(IK + j));
__m256i C0v = _mm256_load_si256((const __m256i *)(IC0 + j));
__m256i C1v = _mm256_load_si256((const __m256i *)(IC1 + j));
__m256i C2v = _mm256_load_si256((const __m256i *)(IC2 + j));
__m256i mA = _mm256_and_si256(_mm256_cmpgt_epi32(kvA, IKv), _mm256_cmpgt_epi32(v0A, C0v));
__m256i mB = _mm256_and_si256(_mm256_cmpgt_epi32(kvB, IKv), _mm256_cmpgt_epi32(v0B, C0v));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v1A, C1v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v1B, C1v));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v2A, C2v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v2B, C2v));
accA = _mm256_sub_epi32(accA, mA);
accB = _mm256_sub_epi32(accB, mB);
}
} else {
for (; j + 8 <= n; j += 8) {
__m256i IKv = _mm256_load_si256((const __m256i *)(IK + j));
__m256i mA = _mm256_cmpgt_epi32(kvA, IKv);
__m256i mB = _mm256_cmpgt_epi32(kvB, IKv);
if (nd > 0) {
__m256i C0v = _mm256_load_si256((const __m256i *)(IC0 + j));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v0A, C0v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v0B, C0v));
}
if (nd > 1) {
__m256i C1v = _mm256_load_si256((const __m256i *)(IC1 + j));
mA = _mm256_and_si256(mA, _mm256_cmpgt_epi32(v1A, C1v));
mB = _mm256_and_si256(mB, _mm256_cmpgt_epi32(v1B, C1v));
}
accA = _mm256_sub_epi32(accA, mA);
accB = _mm256_sub_epi32(accB, mB);
}
}
{
int jj = j;
__m256i acc = accA;
for (; jj + 8 <= nA; jj += 8) {
__m256i msk = _mm256_cmpgt_epi32(kvA, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0A, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1A, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2A, _mm256_load_si256((const __m256i *)(IC2 + jj))));
acc = _mm256_sub_epi32(acc, msk);
}
if (jj < nA) {
int n = nA;
__m256i msk = _mm256_cmpgt_epi32(kvA, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0A, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1A, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2A, _mm256_load_si256((const __m256i *)(IC2 + jj))));
msk = _mm256_and_si256(msk, _mm256_loadu_si256((const __m256i *)VMASK[n - jj]));
acc = _mm256_sub_epi32(acc, msk);
}
OUT[QID[q]] += hsum256(acc);
}
{
int jj = j;
__m256i acc = accB;
for (; jj + 8 <= nB; jj += 8) {
__m256i msk = _mm256_cmpgt_epi32(kvB, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0B, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1B, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2B, _mm256_load_si256((const __m256i *)(IC2 + jj))));
acc = _mm256_sub_epi32(acc, msk);
}
if (jj < nB) {
int n = nB;
__m256i msk = _mm256_cmpgt_epi32(kvB, _mm256_load_si256((const __m256i *)(IK + jj)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0B, _mm256_load_si256((const __m256i *)(IC0 + jj))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1B, _mm256_load_si256((const __m256i *)(IC1 + jj))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2B, _mm256_load_si256((const __m256i *)(IC2 + jj))));
msk = _mm256_and_si256(msk, _mm256_loadu_si256((const __m256i *)VMASK[n - jj]));
acc = _mm256_sub_epi32(acc, msk);
}
OUT[QID[q + 1]] += hsum256(acc);
}
}
#endif
for (; q < nq; q++) {
const int n = (int)QN[q];
__m256i kv = _mm256_set1_epi32((int)QK[q]);
__m256i v0 = _mm256_set1_epi32((int)QC0[q]);
__m256i v1 = _mm256_set1_epi32((int)QC1[q]);
__m256i v2 = _mm256_set1_epi32((int)QC2[q]);
__m256i acc = _mm256_setzero_si256();
int j = 0;
switch (nd) {
case 0:
for (; j + 8 <= n; j += 8)
acc = _mm256_sub_epi32(acc, _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j))));
break;
case 1:
for (; j + 8 <= n; j += 8) {
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
acc = _mm256_sub_epi32(acc, msk);
}
break;
case 2:
for (; j + 8 <= n; j += 8) {
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1, _mm256_load_si256((const __m256i *)(IC1 + j))));
acc = _mm256_sub_epi32(acc, msk);
}
break;
default:
for (; j + 8 <= n; j += 8) {
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1, _mm256_load_si256((const __m256i *)(IC1 + j))));
msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2, _mm256_load_si256((const __m256i *)(IC2 + j))));
acc = _mm256_sub_epi32(acc, msk);
}
break;
}
if (j < n) {
__m256i msk = _mm256_cmpgt_epi32(kv, _mm256_load_si256((const __m256i *)(IK + j)));
if (nd > 0) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v0, _mm256_load_si256((const __m256i *)(IC0 + j))));
if (nd > 1) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v1, _mm256_load_si256((const __m256i *)(IC1 + j))));
if (nd > 2) msk = _mm256_and_si256(msk, _mm256_cmpgt_epi32(v2, _mm256_load_si256((const __m256i *)(IC2 + j))));
msk = _mm256_and_si256(msk, _mm256_loadu_si256((const __m256i *)VMASK[n - j]));
acc = _mm256_sub_epi32(acc, msk);
}
u32 c = hsum256(acc);
OUT[QID[q]] += c;
}
if (!needOut) return;
#if LEAFNB
{
unsigned sum=0;int b=0;
for(;b+16<=NB+1;b+=16){
__m256i v=_mm256_loadu_si256((const __m256i*)(cnt+b));
v=_mm256_add_epi16(v,_mm256_slli_si256(v,2));
v=_mm256_add_epi16(v,_mm256_slli_si256(v,4));
v=_mm256_add_epi16(v,_mm256_slli_si256(v,8));
__m256i lo=_mm256_permute2x128_si256(v,v,0x08);
lo=_mm256_shuffle_epi8(lo,_mm256_set1_epi16(0x0f0e));
v=_mm256_add_epi16(_mm256_add_epi16(v,lo),_mm256_set1_epi16((short)sum));
_mm256_storeu_si256((__m256i*)(cnt+b),v);
sum=(unsigned)_mm256_extract_epi16(v,15);
}
for(;b<=NB;b++){sum+=cnt[b];cnt[b]=(u16)sum;}
for (int t = 0; t < m; t++) { u64 v = seq[t]; out[cnt[(int)(((u32)(v >> 65)) >> (LFSH + LFD))]++] = v; }
int lo = 0;
for (int b = 0; b < NB; b++) {
int hi = (int)cnt[b];
if (hi - lo > 1)
for (int t = lo + 1; t < hi; t++) {
u64 v = out[t];
int q = t - 1;
while (q >= lo && (unsigned long long)(v >> 64) < (unsigned long long)(out[q] >> 64)) { out[q + 1] = out[q]; q--; }
out[q + 1] = v;
}
lo = hi;
}
}
#else
for (int t = 1; t < m; t++) {
u64 v = seq[t];
int q = t - 1;
while (q >= 0 && (unsigned long long)(v >> 64) < (unsigned long long)(seq[q] >> 64)) { seq[q + 1] = seq[q]; q--; }
seq[q + 1] = v;
}
memcpy(out, seq, sizeof(u64) * (size_t)m);
#endif
}
#define MKE_CROSS(V, EMB) ((RK ? (((((V) >> 22) & 0x3FFFFFull) << 65) | ((V) & (((u64)1 << 64) | 0x3FFFFFull))) \
: ((V) & (((u64)1 << 64) | 0x3FFFFFull))) \
| (GAT ? ((u64)(EMB)[eid(V)] << 22) : 0ull))
#define MF_EMB_NONE 0
template<int NO, int RK, int GAT>
static inline void merge_loops(const u64 *retA, int h, const u64 *retB, int r,
u64 *out, u64 *cross, const u32 *XN, const u32 *XE, int &cx) {
(void)XN;
int ia = 0, ib = 0, t = 0;
while (ia < h && ib < r) {
__builtin_prefetch(retA + ia + 32);
__builtin_prefetch(retB + ib + 32);
if (NO) __builtin_prefetch(out + t + 32);
__builtin_prefetch(cross + cx + 32);
u64 ea = retA[ia], eb = retB[ib];
int takeA = ((unsigned long long)(ea >> 64) < (unsigned long long)(eb >> 64));
ia += takeA; ib += 1 - takeA;
u64 v = takeA ? ea : eb;
if (NO) out[t] = v;
t++;
int role = (int)((v >> 64) & 1);
u64 c = MKE_CROSS(v, XE);
cross[cx] = c;
cx += keep_test(takeA, role);
}
while (ia < h) {
u64 v = retA[ia++];
if (NO) out[t] = v;
t++;
if ((v >> 64) & 1) cross[cx++] = MKE_CROSS(v, XE);
}
while (ib < r) {
u64 v = retB[ib++];
if (NO) out[t] = v;
t++;
if (!((v >> 64) & 1)) cross[cx++] = MKE_CROSS(v, XE);
}
}
template <int KT, int D, int NO>
static void solve_b(u64 *seq, int m, u64 *out, TB<true>) {
(void)out;
int cnt = 0;
for (int t = 0; t < m; t++) {
u64 v = seq[t];
if ((v >> 64) & 1) cnt++;
else OUT[eid(v)] += (u32)cnt;
}
}
template <int KT, int D, int NO>
static void solve_b(u64 *seq, int m, u64 *out, TB<false>) {
if (m <= KG_BASE) {
base_case_t<NCL< KT - (D + 2) >::v>(seq, m, D, out, NO);
return;
}
int h = m >> 1, r = m - h;
u64 *save = ABtop;
u64 *retA = ABtop; ABtop += h;
u64 *retB = ABtop; ABtop += r;
solve_t<KT, D, 1>(seq, h, retA);
solve_t<KT, D, 1>(seq + h, r, retB);
u64 *cross = ABtop; ABtop += m + 1;
const int RK = (D + 2 <= KT - 1) ? 1 : 0;
const int GAT = (D + 3 <= KT - 1) ? 1 : 0;
const u32 *XN = RK ? XD[D + 2] : 0;
const u32 *XE = GAT ? XD[D + 3] : 0;
int cx = 0;
merge_loops<NO, RK, GAT>(retA, h, retB, r, out, cross, XN, XE, cx);
if (FUSE_OK && D == KT - 3) {
u32 *dirt = (u32 *)ABtop; ABtop += (cx + 3) / 2 + 1;
ctr_solve(cross, cx, dirt);
} else {
solve_t<KT, D + 1, 0>(cross, cx, nullptr);
}
ABtop = save;
}
template <int KT, int D, int NO>
static inline void solve_t(u64 *seq, int m, u64 *out) {
if (m <= 1) return;
solve_b<KT, D, NO>(seq, m, out, TB<(D >= KT - 1)>());
}
#ifndef MF_S0P
#define MF_S0P 16
#endif
static u32 *g_ord, *g_x;
static void sort0(int n) {
const u32 *X0 = XD[0];
u32 *cnt = g_x;
/* [R132A-HIST8] 第一轴计数表 u32 -> u8. 死事件竞技场 AB 在 sort0 期间未被使用
(run_t: ABtop=AB -> FNV probe -> sort0 -> ev=AB, 见下) => 直接借用, 零额外静态内存.
精确终population 证明无字节回绕: 若任一桶 >255, u8 回绕使 sum==n-256k != n
=> 走 u32 重建原路. 桶大小 ~1 (坐标 [0,n) 随机) => 生产上兜底从不触发. */
u8 *hist = reinterpret_cast<u8 *>(AB);
memset(hist, 0, (size_t)n + 1);
for (int i = 0; i < n; i++) {
// [R132A-S0P] 计数趟随机 RMW 的写意图前瞻(我方在册机理, 见件头引用)
if (i + MF_S0P < n) {
u32 vf = X0[i + MF_S0P];
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(&hist[vf + 1])));
}
++hist[X0[i] + 1];
}
u32 sum = 0;
for (int v = 0; v <= n; v++) { sum += hist[v]; cnt[v] = sum; }
if (sum != (u32)n) {
memset(cnt, 0, sizeof(u32) * (size_t)(n + 1));
for (int i = 0; i < n; i++) cnt[X0[i] + 1]++;
for (int i = 0; i < n; i++) cnt[i + 1] += cnt[i];
}
for (int i = 0; i < n; i++) {
if (i + MF_S0P < n) {
u32 vf = X0[i + MF_S0P];
__builtin_prefetch(&cnt[vf], 0, 3);
__asm__ __volatile__("prefetchw %0" :: "m"(*(const char *)(&g_ord[cnt[vf]])));
}
g_ord[cnt[X0[i]]++] = (u32)i;
}
}
template <int KT>
static void run_t(int n, const u32 **x, u32 *out) {
LFSH = 0; LFD = 0;
for (int d = 0; d < KT; d++) XD[d] = x[d];
OUT = out;
ABtop = AB;
if (n <= 1) return;
FUSE_OK = 0;
counter_domain = (u32)n;
if (KT >= 4 && n > 2 && (u32)n < CT_MAXV) {
const u32 *XL = XD[KT - 1];
memset(CT0, 0, (size_t)n);
int ok = 1;
for (int i = 0; i < n; i++) if (++CT0[XL[i]] > 127) { ok = 0; break; }
memset(CT0, 0, (size_t)n);
FUSE_OK = ok;
}
{
int bit = 0;
while ((n >> bit) >= LEAFNB && bit < 30) bit++;
LFSH = bit; LFD = 0;
LFB = (int)((((u32)(n - 1)) >> (LFSH + LFD)) + 2u);
if (LFB > LEAFNB) LFB = LEAFNB;
if (LFB < 8) LFB = 8;
}
sort0(n);
const u32 *X0 = XD[0], *X1 = XD[1];
const u32 *nk2 = (KT >= 3) ? XD[2] : X0;
u64 *ev = AB;
int m = 0, g = 0;
while (g < n) {
int g1 = g;
u32 v = X0[g_ord[g]];
while (g1 < n && X0[g_ord[g1]] == v) g1++;
const int group_size = g1 - g;
for (int t = g; t < g1; t++) {
if (t + 16 < g1) { u32 idf = g_ord[t + 16]; __builtin_prefetch(&X1[idf], 0, 1); __builtin_prefetch(&nk2[idf], 0, 1); }
const u32 id = g_ord[t];
const u64 event = mk(X1[id], 1, (int)id, nk2[id]);
ev[m] = event;
ev[m + group_size] = event | ((u64)1 << 64);
++m;
}
m += group_size;
g = g1;
}
ABtop = AB + m;
solve_t<KT, 0, 0>(ev, m, nullptr);
}
}
static u64 g_arena[KG_ARENA];
static u32 g_ord_st[4194308], g_x_st[4194308];
static int g_ready = 0;
static void setup() {
if (g_ready) return;
g_ready = 1;
kg::AB = g_arena;
kg::g_ord = g_ord_st;
kg::g_x = g_x_st;
}
void count_4d(int n, const unsigned *x[4], unsigned *out) {
setup();
memset(out, 0, sizeof(unsigned) * (size_t)n);
kg::run_t<4>(n, (const unsigned **)x, out);
}
#pragma GCC pop_options
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 6.313 s | 406 MB + 540 KB | Accepted | Score: 100 | 显示更多 |