// ===== 引用区（本发增量）=====
// [1] 本账号 saffah_v41f1017_agg4，提交 #135855 <https://duck.ac/submission/135855>
// （题 1009a，7.233 ms，Accepted，rank1 现役 best）—— 本发底盘（正文逐字节副本；其引用链/思路区保留于下方）。
// [2] duck.ac 题页 <https://duck.ac/problem/1009a>（公开提交正文；无外部仓库/论文引用）。
// ===== 思路区（本发）=====
// 【单变量/组合 .text 对齐：byte_rank_leaf query 环前 .p2align 3（8B）（叠加现役 nf_s32）】
// 值精确：n=1e5 mode0 FNV=9686403496873044668（与底盘逐位同）；
// .text 逐字节 md5 = 79a26f1994f604fedba0f7d04b69bea7（≠ 底盘 b9434b25256f8fb2527fe1c4c033acfe；非等价件，查重通过）。
// ================================================
// ===== 引用区（本发增量）=====
// [1] 本账号 saffah_v41f1017_agg4，提交 #135777 <https://duck.ac/submission/135777>
// （题 1009a，7.249 ms，Accepted，现役 best）—— 本发底盘（正文逐字节副本；其引用链/思路区保留于下方）。
// [2] duck.ac 题页 <https://duck.ac/problem/1009a>（公开提交正文；无外部仓库/论文引用）。
// ===== 思路区（本发）=====
// 【单变量 .text 对齐/位移：node_fused 主环前 "jmp 9f/.space 32/9:"（32B 位移，跳过填充）】正文仅加一行 asm；与底盘逐行 diff 仅此一处。
// 值精确：n=1e5 mode0 FNV=9686403496873044668（与底盘逐位同）；
// .text 逐字节 md5 = b9434b25256f8fb2527fe1c4c033acfe（≠ 底盘 0a0e35ddc361a003a67f3b7f9141d203；非等价件，查重通过）。
// vendor gcc9 9.3.0 -O2 -std=c++17 -c + objcopy 配方。
// ================================================
// ===== 引用区（本发增量）=====
// [1] 本账号 saffah_v41f1017_agg4，提交 #134476 <https://duck.ac/submission/134476>
// （题 1009a，7.270163ms，rank1）—— 本发底盘（正文逐字节副本；其引用链/思路区保留于下方）。
// [2] duck.ac 题页 <https://duck.ac/problem/1009a>（公开提交正文）。
// ===== 思路区（本发）=====
// 【单变量 CODE生成pragma：no-tree-pre】值精确（n=1e5 mode0 FNV=9686403496873044668），.text md5 已记录且 ≠ 底盘。
// 官方 ns 单发定价。
// ===== 引用区 =====
// [1] duck.ac 公开提交（具名引用）：本账号 saffah_v41f1017_agg4 的 1009a 引擎链 #132831、#132955
// <https://duck.ac/submission/132955>；其上游为账号 saffah_codex_6a_agg3 的 #130047 谱系。
// 均为站点公开提交，无独立许可证声明，按站点规则与 RULES 具名引用。
// [2] duck.ac 公开提交（具名引用）：账号 saffah_codex_6a_agg3 的 #133749（稠密字节叶/归并引擎）、
// #133835 <https://duck.ac/submission/133835>（叶记录融合）。本文件正文 = #133835 正文的逐字节
// 副本（仅去注释；其自带引用链已在 [1][2] 具名列出）。
// [3] 题目页 <https://duck.ac/problem/1009a>（提交正文按站规公开可见）。
// ===== 思路区 =====
// 【本发单机制·代码对齐格 AF】在 #134380（= #133835 正文去注释，官方 7.274291ms）基座上仅追加
// `#pragma GCC optimize("align-functions=128")`；不改任何代码/常数/算法/存储顺序。
// 此前只测过 AF32（官方 7.322ms，负）；本发定价 AF=128 对齐格。
// 【闸门】n=100000 模式 0..4 全输出 FNV 与底盘逐位相同（模式0 = 9686403496873044668）。
// ============================================================
#include <string.h>
#include <immintrin.h>
#pragma GCC push_options
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,tune=sandybridge")
#pragma GCC optimize("O2","unroll-loops","no-inline-functions-called-once","no-ipa-cp","sched-pressure","no-tree-ch","no-ipa-sra","no-tree-vrp")
#pragma GCC optimize("align-functions=128")
#pragma GCC optimize("no-tree-pre")
typedef unsigned u32;
typedef unsigned long long u64;
typedef unsigned char u8;
typedef unsigned short u16;
static const int MAXN = 100001;
static unsigned *g_rootout = 0;
static int g_root_pending = 0;
int g_nz = 0;
#ifndef ZCTHR
#define ZCTHR 16
#endif
#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) & 0xFFFFFu))
#define W_X(v) ((u32)(((v) >> 20) & 0xFFFFFu))
static u64 RC[2][2 * (MAXN + 8)] __attribute__((aligned(64)));
static u64 TIE[(MAXN + 63) / 64 + 8];
#define H64 ((u64 *)(void *)RC[1])
#define CNT ((u32 *)(void *)(RC[1] + (MAXN + 8)))
#define NGRP ((MAXN + 1023) / 1024 + 8)
struct alignas(64) SmallCounters {
alignas(64) u8 M2TAB[NGRP * 32];
alignas(64) u8 M3TAB[NGRP * 32];
alignas(64) u64 ZB[(MAXN + 63) / 64 + 16];
alignas(64) u16 C1[(MAXN + 63) / 64 + 32];
alignas(64) u16 C2[(MAXN + 1023) / 1024 + 32];
alignas(64) u32 C3[8];
};
static SmallCounters smallct;
#define ZB (smallct.ZB)
#define C1 (smallct.C1)
#define C2 (smallct.C2)
#define C3 (smallct.C3)
#define M2TAB (smallct.M2TAB)
#define M3TAB (smallct.M3TAB)
static u8 ZW1[(MAXN + 63) / 64 + 32];
static u16 ZW2[(MAXN + 1023) / 1024 + 32];
static u16 ZW3[(MAXN + 16383) / 16384 + 32];
static u32 ZW4[(MAXN + 262143) / 262144 + 32];
static const u16 IDX16[16] __attribute__((aligned(32))) = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
static const u32 IDX8[8] __attribute__((aligned(32))) = {0,1,2,3,4,5,6,7};
alignas(32) static const u16 PREFIX16[16][16]={{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}};
alignas(32) static const u32 PREFIX8[8][8]={{0,1,1,1,1,1,1,1},{0,0,1,1,1,1,1,1},{0,0,0,1,1,1,1,1},{0,0,0,0,1,1,1,1},{0,0,0,0,0,1,1,1},{0,0,0,0,0,0,1,1},{0,0,0,0,0,0,0,1},{0,0,0,0,0,0,0,0}};
static inline void k09k_zr(void *p, size_t n) {
char *q = (char *)p;
__m256i z = _mm256_setzero_si256();
size_t i = 0;
for (; i + 128 <= n; i += 128) {
_mm256_storeu_si256((__m256i *)(void *)(q + i), z);
_mm256_storeu_si256((__m256i *)(void *)(q + i + 32), z);
_mm256_storeu_si256((__m256i *)(void *)(q + i + 64), z);
_mm256_storeu_si256((__m256i *)(void *)(q + i + 96), z);
}
for (; i < n; i += 32) _mm256_storeu_si256((__m256i *)(void *)(q + i), z);
}
#define memset0(p, n) k09k_zr((p), ((n) + 31u) & ~31u)
static constexpr int CounterDomain=100000;
static void mktab(void) {
const int ng = (CounterDomain + 1023) / 1024 + 1;
for (int p = 0; p < ng && p < NGRP; p++) {
__m256i m = _mm256_load_si256((const __m256i *)PREFIX16[p & 15]);
_mm256_store_si256((__m256i *)(void *)(M2TAB + 32 * p), m);
__m256i n = _mm256_load_si256((const __m256i *)PREFIX8[(p >> 4) < 8 ? (p >> 4) : 7]);
_mm256_store_si256((__m256i *)(void *)(M3TAB + 32 * p), n);
}
}
static inline void grp16v(void *p, const void *m, int sgn) {
__m256i x = _mm256_load_si256((const __m256i *)p), y = _mm256_load_si256((const __m256i *)m);
_mm256_store_si256((__m256i *)p, sgn > 0 ? _mm256_add_epi16(x, y) : _mm256_sub_epi16(x, y));
}
static inline void grp8v(void *p, const void *m, int sgn) {
__m256i x = _mm256_load_si256((const __m256i *)p), y = _mm256_load_si256((const __m256i *)m);
_mm256_store_si256((__m256i *)p, sgn > 0 ? _mm256_add_epi32(x, y) : _mm256_sub_epi32(x, y));
}
static inline void grp16b(void *p,u32 t4,int sgn){
__m256i x=_mm256_load_si256((const __m256i*)p),m=_mm256_load_si256((const __m256i*)(const void*)((const char*)PREFIX16+(size_t)t4*8));
_mm256_store_si256((__m256i*)p,sgn>0?_mm256_add_epi16(x,m):_mm256_sub_epi16(x,m));
}
static inline void grp8b(void *p,u32 t4,int sgn){
__m256i x=_mm256_load_si256((const __m256i*)p),m=_mm256_load_si256((const __m256i*)(const void*)((const char*)PREFIX8+(size_t)t4*8));
_mm256_store_si256((__m256i*)p,sgn>0?_mm256_add_epi32(x,m):_mm256_sub_epi32(x,m));
}
template <int LV> static inline void zclear() {
memset0(ZB, (size_t)((CounterDomain + 63) / 64) * 8);
memset0(C1, (size_t)(((CounterDomain + 63) / 64 + 15) / 16) * 32);
memset0(C2, (size_t)(((CounterDomain + 1023) / 1024 + 15) / 16) * 32);
memset0(C3, 32);
if (LV >= 4) {
memset(ZW1, 0, (size_t)((CounterDomain + 63) / 64));
memset(ZW2, 0, (size_t)((CounterDomain + 1023) / 1024) * 2);
memset(ZW3, 0, (size_t)((CounterDomain + 16383) / 16384) * 2);
memset(ZW4, 0, (size_t)((CounterDomain + 262143) / 262144) * 4);
}
}
static inline void zclear_upper() {
__m128i z = _mm_setzero_si128();
int i2 = (CounterDomain + 1023) / 1024, q2 = (i2 + 7) >> 3;
for (int q = 0; q < q2; q++) _mm_storeu_si128((__m128i *)(void *)(ZW2 + 8 * q), z);
int i3 = (CounterDomain + 16383) / 16384, q3 = (i3 + 7) >> 3;
for (int q = 0; q < q3; q++) _mm_storeu_si128((__m128i *)(void *)(ZW3 + 8 * q), z);
int i4 = (CounterDomain + 262143) / 262144, q4 = (i4 + 3) >> 2;
for (int q = 0; q < q4; q++) _mm_storeu_si128((__m128i *)(void *)(ZW4 + 4 * q), z);
int i1 = (CounterDomain + 63) / 64, q1 = (i1 + 15) >> 4;
for (int q = 0; q < q1; q++) _mm_storeu_si128((__m128i *)(void *)(ZW1 + 16 * q), z);
}
template <int LV> static inline void zclear_touched(int l, int aIns, const u64 *S) {
__m256i z = _mm256_setzero_si256();
for (int k = l; k < aIns; k++) {
u32 r = W_R(S[2 * k + 1]);
ZB[r >> 6] = 0;
if (LV <= 3) {
_mm256_store_si256((__m256i *)(void *)(C1 + ((r >> 6) & ~15u)), z);
_mm256_store_si256((__m256i *)(void *)(C2 + ((r >> 10) & ~15u)), z);
}
}
if (LV <= 3) _mm256_store_si256((__m256i *)(void *)C3, z);
else zclear_upper();
}
#ifndef C1GRP
#define C1GRP 98
#endif
#ifndef ZBTHR
#define ZBTHR 400
#endif
static inline void zclear_C23() {
__m256i z = _mm256_setzero_si256();
int i2 = (CounterDomain + 1023) / 1024, q2 = (i2 + 15) >> 4;
for (int q = 0; q < q2; q++) _mm256_store_si256((__m256i *)(void *)(C2 + 16 * q), z);
_mm256_store_si256((__m256i *)(void *)C3, z);
}
template <int LV> static inline void zclear_cheap(int l, int aIns, const u64 *S) {
if (LV <= 3) {
if (aIns - l >= C1GRP) {
for (int k = l; k < aIns; k++) ZB[W_R(S[2 * k + 1]) >> 6] = 0;
memset0(C1, (size_t)(((CounterDomain + 63) / 64 + 15) / 16) * 32);
} else {
__m256i z = _mm256_setzero_si256();
for (int k = l; k < aIns; k++) {
u32 r = W_R(S[2 * k + 1]);
ZB[r >> 6] = 0;
_mm256_store_si256((__m256i *)(void *)(C1 + ((r >> 6) & ~15u)), z);
}
}
zclear_C23();
} else {
for (int k = l; k < aIns; k++) ZB[W_R(S[2 * k + 1]) >> 6] = 0;
zclear_upper();
}
}
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> static inline void zadd(u32 r) {
if (LV <= 3) {
const u32 g1 = (r >> 5) & ~31u;
const u32 g2 = (g1 >> 4) & ~31u;
ZB[r >> 6] |= 1ull << (r & 63);
grp16b((char*)C1 + g1, (r >> 4) & 60u, +1);
grp16v((char*)C2 + g2, M2TAB + g1, +1);
grp8v ((char*)C3, M3TAB + g1, +1);
} else { ZB[r>>6] |= 1ull<<(r&63); ZW1[r >> 6]++; ZW2[r >> 10]++; ZW3[r >> 14]++; ZW4[r >> 18]++; }
}
template <int LV> static inline void zsub(u32 r) {
if (LV <= 3) {
const u32 g1 = (r >> 5) & ~31u;
const u32 g2 = (g1 >> 4) & ~31u;
ZB[r >> 6] &= ~(1ull << (r & 63));
grp16b((char*)C1 + g1, (r >> 4) & 60u, -1);
grp16v((char*)C2 + g2, M2TAB + g1, -1);
grp8v ((char*)C3, M3TAB + g1, -1);
} else { ZB[r>>6] &= ~(1ull<<(r&63)); ZW1[r >> 6]--; ZW2[r >> 10]--; ZW3[r >> 14]--; ZW4[r >> 18]--; }
}
static inline u32 hsum256(__m256i s) {
__m128i lo = _mm256_castsi256_si128(s), hi = _mm256_extracti128_si256(s, 1);
__m128i t = _mm_add_epi32(lo, hi);
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 LV> static inline u32 zquery(u32 T) {
if (LV <= 3) {
u32 w = T >> 6;
u32 s = (u32)C3[T >> 14] + (u32)C2[T >> 10] + (u32)C1[w];
return s + (u32)__builtin_popcountll(_bzhi_u64(ZB[w], T & 63));
}
u32 k4 = T >> 18, k3 = (T >> 14) & 15, k2 = (T >> 10) & 15, k1 = (T >> 6) & 15, rem = T & 63;
__m256i acc = _mm256_setzero_si256();
if (LV >= 4) acc = _mm256_and_si256(_mm256_loadu_si256((const __m256i *)ZW4),
_mm256_cmpgt_epi32(_mm256_set1_epi32((int)k4), _mm256_setr_epi32(0,1,2,3,4,5,6,7)));
acc = _mm256_add_epi32(acc, _mm256_madd_epi16(_mm256_and_si256(
_mm256_loadu_si256((const __m256i *)(ZW3 + (k4 << 4))),
_mm256_cmpgt_epi16(_mm256_set1_epi16((short)k3), mkI16())), mkOne16()));
acc = _mm256_add_epi32(acc, _mm256_madd_epi16(_mm256_and_si256(
_mm256_loadu_si256((const __m256i *)(ZW2 + ((T >> 14) << 4))),
_mm256_cmpgt_epi16(_mm256_set1_epi16((short)k2), mkI16())), mkOne16()));
__m128i s8 = _mm_sad_epu8(_mm_and_si128(
_mm_loadu_si128((const __m128i *)(ZW1 + ((T >> 10) << 4))),
_mm_cmpgt_epi8(_mm_set1_epi8((char)k1), mkI8())), _mm_setzero_si128());
u32 s = hsum256(acc) + (u32)_mm_cvtsi128_si32(s8) + (u32)(_mm_extract_epi16(s8, 4) & 0xFFFF);
s += (u32)__builtin_popcountll(_bzhi_u64(ZB[T >> 6], rem));
return s;
}
#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_root(int l, int m, int r, int src) {
u64 *S = RC[src];
int a = l, b = m;
if (a < m && b < r) {
const u64 *pa = S + 2 * a, *pb = S + 2 * b;
const u64 *const pae = S + 2 * m, *const pbe = S + 2 * r;
u64 w0a = pa[0], w1a = pa[1]; u32 ya = (u32)(w0a >> 40);
u64 w0b = pb[0], w1b = pb[1]; u32 yb = (u32)(w0b >> 40);
for (;;) {
const u64 na0=pa[2],na1=pa[3],nb0=pb[2],nb1=pb[3];
if (yb <= ya) {
w0b += zquery<LV>((u32)(w1b >> 40));
g_rootout[W_ORIG(w0b)] = W_A(w0b); pb += 2;
if (pb >= pbe) break;
w0b = nb0; w1b = nb1; yb = (u32)(nb0 >> 40);
} else {
zadd<LV>(W_R(w1a));
g_rootout[W_ORIG(w0a)] = W_A(w0a); pa += 2;
if (pa >= pae) break;
w0a = na0; w1a = na1; ya = (u32)(na0 >> 40);
}
}
a = (int)((pa - S) >> 1); b = (int)((pb - S) >> 1);
}
while (b < r) {
u64 w0b = S[2 * b] + zquery<LV>((u32)(S[2 * b + 1] >> 40));
g_rootout[W_ORIG(w0b)] = W_A(w0b); b++;
}
while (a < m) { u64 w0 = S[2 * a]; g_rootout[W_ORIG(w0)] = W_A(w0); a++; }
}
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, t = l;
if (a < m && b < r) {
const u64 *pa = S + 2 * a, *pb = S + 2 * b; u64 *pd = D + 2 * l;
const u64 *const pae = S + 2 * m, *const pbe = S + 2 * r;
u64 w0a = pa[0], w1a = pa[1]; u32 ya = (u32)(w0a >> 40);
u64 w0b = pb[0], w1b = pb[1]; u32 yb = (u32)(w0b >> 40);
asm volatile("jmp 9f\n\t.space 32\n9:" ::: "memory");
for (;;) {
{ const u64 na0 = pa[2], na1 = pa[3], nb0 = pb[2], nb1 = pb[3];
if (yb <= ya) {
w0b += zquery<LV>((u32)(w1b >> 40));
pd[0] = w0b; pd[1] = w1b; pd += 2; pb += 2;
if (pb >= pbe) break;
w0b = nb0; w1b = nb1; yb = (u32)(nb0 >> 40);
} else {
zadd<LV>(W_R(w1a));
pd[0] = w0a; pd[1] = w1a; pd += 2; pa += 2;
if (pa >= pae) break;
w0a = na0; w1a = na1; ya = (u32)(na0 >> 40);
} }
}
a = (int)((pa - S) >> 1); b = (int)((pb - S) >> 1); t = (int)((pd - D) >> 1);
}
int aIns = a;
while (b < r) {
u64 w0b = S[2 * b], w1b = S[2 * b + 1];
w0b += zquery<LV>((u32)(w1b >> 40));
D[2 * t] = w0b; D[2 * t + 1] = w1b; b++; t++;
}
while (a < m) { D[2 * t] = S[2 * a]; D[2 * t + 1] = S[2 * a + 1]; a++; t++; }
if (aIns - l >= ZBTHR) zclear<LV>();
else if (r - l >= ZCTHR) zclear_cheap<LV>(l, aIns, S);
else for (int k = l; k < aIns; k++) zsub<LV>(W_R(S[2 * k + 1]));
}
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;
{ const u64 *pa = S + 2 * a, *pb = S + 2 * b; u64 *pd = D + 2 * t;
const u64 *const pae = S + 2 * m, *const pbe = S + 2 * r;
while (pa < pae && pb < pbe) {
const u64 *ps = ((*pa >> 40) <= (*pb >> 40)) ? pa : pb;
pd[0] = ps[0]; pd[1] = ps[1]; pd += 2;
if (ps == pa) pa += 2; else pb += 2;
}
a = (int)((pa - S) >> 1); b = (int)((pb - S) >> 1); t = (int)((pd - D) >> 1);
}
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
alignas(32) static const unsigned TAIL4MASK[25][8]={
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0},
{0xffffffffu,0,0,0,0,0,0,0},
{0xffffffffu,0xffffffffu,0,0,0,0,0,0},
{0xffffffffu,0xffffffffu,0xffffffffu,0,0,0,0,0},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0,0,0,0},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0,0,0},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0,0},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu},
{0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu,0xffffffffu}
};
struct alignas(64) LeafScratch {
alignas(32) u32 lex[LSCR + 16]; alignas(32) u32 ley[LSCR + 16]; alignas(32) u32 ler[LSCR + 16];
alignas(32) u64 lkey[LSCR + 16]; alignas(32) u64 ltmp[2 * (LSCR + 16)];
alignas(32) u32 lk[256];
alignas(32) u32 lyk[LSCR + 16]; alignas(32) u32 lxq[LSCR + 16];
alignas(32) u32 lzq[LSCR + 16]; alignas(32) u32 ltq[LSCR + 16]; alignas(32) u32 lst[LSCR + 16];
};
static LeafScratch lsc;
#define lex (lsc.lex)
#define ley (lsc.ley)
#define ler (lsc.ler)
#define lkey (lsc.lkey)
#define ltmp (lsc.ltmp)
#define lk (lsc.lk)
#define lyk (lsc.lyk)
#define lxq (lsc.lxq)
#define lzq (lsc.lzq)
#define ltq (lsc.ltq)
#define lst (lsc.lst)
static inline void bs64(__m256i *r) {
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x66); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x3C); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x5A); }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[2]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
{ __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[4]=Hi; }
{ __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[5]=Hi; }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[4]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[7]=Lo; r[6]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x0F); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x33); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0x55); }
{ __m256i A=r[0], B=r[4]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[4]=Hi; }
{ __m256i A=r[1], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[5]=Hi; }
{ __m256i A=r[2], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[6]=Hi; }
{ __m256i A=r[3], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[3]=Lo; r[7]=Hi; }
{ __m256i A=r[0], B=r[2]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[2]=Hi; }
{ __m256i A=r[1], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[1]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[6]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[6]=Hi; }
{ __m256i A=r[5], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[5]=Lo; r[7]=Hi; }
{ __m256i A=r[0], B=r[1]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[0]=Lo; r[1]=Hi; }
{ __m256i A=r[2], B=r[3]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[2]=Lo; r[3]=Hi; }
{ __m256i A=r[4], B=r[5]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[4]=Lo; r[5]=Hi; }
{ __m256i A=r[6], B=r[7]; __m256i Lo=_mm256_min_epu32(A,B), Hi=_mm256_max_epu32(A,B); r[6]=Lo; r[7]=Hi; }
{ __m256i A=r[0]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[1]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[2]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[3]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[4]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[5]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[6]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[7]; __m256i T=_mm256_permute4x64_epi64(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xF0); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0x4E); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xCC); }
{ __m256i A=r[0]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[0]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[1]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[1]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[2]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[2]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[3]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[3]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[4]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[4]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[5]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[5]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[6]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[6]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
{ __m256i A=r[7]; __m256i T=_mm256_shuffle_epi32(A,0xB1); r[7]=_mm256_blend_epi32(_mm256_min_epu32(A,T),_mm256_max_epu32(A,T),0xAA); }
}
static inline void bm128(u32 *k) {
const __m256i BM_IDX64 = _mm256_setr_epi32(7,6,5,4,3,2,1,0);
{
__m256i t[8];
for (int q = 0; q < 8; q++) t[q] = _mm256_permutevar8x32_epi32(
_mm256_load_si256((const __m256i *)(k + 64 + 8 * (7 - q))), BM_IDX64);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(k + 64 + 8 * q), t[q]);
}
for (int d = 64; d >= 8; d >>= 1) {
for (int base = 0; base < 128; base += 2 * d)
for (int j = 0; j < d; j += 8) {
__m256i a = _mm256_load_si256((const __m256i *)(k + base + j));
__m256i b = _mm256_load_si256((const __m256i *)(k + base + j + d));
_mm256_store_si256((__m256i *)(k + base + j), _mm256_min_epu32(a, b));
_mm256_store_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 < 128; base += 8) {
__m256i a = _mm256_load_si256((const __m256i *)(k + base));
__m256i p = _mm256_permutevar8x32_epi32(a, idx);
__m256i lo = _mm256_min_epu32(a, p), hi = _mm256_max_epu32(a, p);
_mm256_store_si256((__m256i *)(k + base), _mm256_blendv_epi8(lo, hi, bsel));
}
}
}
static inline void bm256(u32 *k) {
const __m256i BM_IDX64 = _mm256_setr_epi32(7,6,5,4,3,2,1,0);
{ __m256i t[16];
for (int q = 0; q < 16; q++) t[q] = _mm256_permutevar8x32_epi32(
_mm256_load_si256((const __m256i *)(k + 128 + 8 * (15 - q))), BM_IDX64);
for (int q = 0; q < 16; q++) _mm256_store_si256((__m256i *)(k + 128 + 8 * q), t[q]);
}
for (int d = 128; d >= 8; d >>= 1) {
for (int base = 0; base < 256; base += 2 * d)
for (int j = 0; j < d; j += 8) {
__m256i a = _mm256_load_si256((const __m256i *)(k + base + j));
__m256i b = _mm256_load_si256((const __m256i *)(k + base + j + d));
_mm256_store_si256((__m256i *)(k + base + j), _mm256_min_epu32(a, b));
_mm256_store_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 < 256; base += 8) {
__m256i a = _mm256_load_si256((const __m256i *)(k + base));
__m256i p = _mm256_permutevar8x32_epi32(a, idx);
__m256i lo = _mm256_min_epu32(a, p), hi = _mm256_max_epu32(a, p);
_mm256_store_si256((__m256i *)(k + base), _mm256_blendv_epi8(lo, hi, bsel));
}
}
}
alignas(32) static u8 byte_lrx[528],byte_lrz[528];
alignas(32) static u8 byte_lxb[320],byte_lzb[320];
alignas(32) static u32 byte_lzk[256];
__attribute__((noinline,noclone)) static void byte_leaf_sort(u32 *a, int sn) {
if(sn<=64){for(int k=sn;k<64;++k)a[k]=0xffffffffu;bs64((__m256i*)a);}
else if(sn<=128){for(int k=sn;k<128;++k)a[k]=0xffffffffu;bs64((__m256i*)a);bs64((__m256i*)(a+64));bm128(a);}
else {for(int k=sn;k<256;++k)a[k]=0xffffffffu;for(int k=0;k<256;k+=64)bs64((__m256i*)(a+k));bm128(a);bm128(a+128);bm256(a);}
}
template<bool RelativeX> __attribute__((always_inline)) static inline void build_leaf_keys(u64 *S,int l,int sn,u32 xbase) {
u32 prevx = 0xFFFFFFFFu; int xr = -1;
const __m256i ID4 = _mm256_setr_epi64x(0,1,2,3);
const __m256i PK = _mm256_setr_epi32(0,2,4,6,0,2,4,6);
const __m256i M20 = _mm256_set1_epi64x(0xFFFFF);
int k4 = 0;
for (; k4 + 4 <= sn; k4 += 4) {
const u64 *P = S + 2 * (l + k4);
__m256i v0 = _mm256_loadu_si256((const __m256i *)(const void *)P);
__m256i v1 = _mm256_loadu_si256((const __m256i *)(const void *)(P + 4));
__m256i t0 = _mm256_permute4x64_epi64(v0, 0xD8);
__m256i t1 = _mm256_permute4x64_epi64(v1, 0xD8);
__m256i w0 = _mm256_permute2x128_si256(t0, t1, 0x20);
__m256i w1 = _mm256_permute2x128_si256(t0, t1, 0x31);
const __m256i high_dwords = _mm256_setr_epi32(1,3,5,7,1,3,5,7);
const __m128i key_mask = _mm_set1_epi32((int)0xffffff00u);
const __m128i kidx = _mm_add_epi32(_mm_setr_epi32(0,1,2,3), _mm_set1_epi32(k4));
const __m128i ykeys = _mm_and_si128(_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(w0, high_dwords)),key_mask);
const __m128i zkeys = _mm_and_si128(_mm256_castsi256_si128(_mm256_permutevar8x32_epi32(w1, high_dwords)),key_mask);
_mm_store_si128((__m128i *)(void *)(lk+k4), _mm_or_si128(ykeys,kidx));
_mm_store_si128((__m128i *)(void *)(byte_lzk+k4), _mm_or_si128(zkeys,kidx));
__m128i x4 = _mm256_castsi256_si128(_mm256_permutevar8x32_epi32(_mm256_and_si256(_mm256_srli_epi64(w1,20), M20), PK));
__m128i rk;
if constexpr(RelativeX) {
rk=_mm_xor_si128(_mm_sub_epi32(x4,_mm_set1_epi32((int)xbase)),_mm_set1_epi32(0x80));
} else {
__m128i sh = _mm_insert_epi32(_mm_slli_si128(x4, 4), (int)prevx, 0);
__m128i neq = _mm_cmpeq_epi32(x4, sh);
__m128i fl = _mm_andnot_si128(neq, _mm_set1_epi32(1));
__m128i ps = _mm_add_epi32(fl, _mm_slli_si128(fl, 4));
ps = _mm_add_epi32(ps, _mm_slli_si128(ps, 8));
rk = _mm_xor_si128(_mm_add_epi32(ps, _mm_set1_epi32(xr)), _mm_set1_epi32(0x80));
xr += _mm_extract_epi32(ps, 3);
prevx = (u32)_mm_extract_epi32(x4, 3);
}
__m128i b8 = _mm_packus_epi16(_mm_packus_epi32(rk, rk), _mm_packus_epi32(rk, rk));
*(u32 *)(void *)(byte_lrx + k4) = (u32)_mm_cvtsi128_si32(b8);
}
for (int k = k4; 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 = W_X(w1);
if constexpr(RelativeX) byte_lrx[k]=(u8)((xv-xbase)^0x80u);
else {if(xv!=prevx){prevx=xv;xr++;}byte_lrx[k]=(u8)((u32)xr^0x80u);}
byte_lzk[k] = (u32)(((w1 >> 40) & 0xFFFFFu) << 8) | (u32)k;
}
}
struct alignas(32) BytePrefixMasks {
u8 row[33][32];
constexpr BytePrefixMasks():row{} { for(int n=0;n<=32;++n)for(int j=0;j<32;++j)row[n][j]=j<n?255:0; }
};
static constexpr BytePrefixMasks byte_prefix_masks{};
static inline __m256i byte_prefix(int n){return _mm256_load_si256((const __m256i*)byte_prefix_masks.row[n]);}
static int byte_rank_leaf(int l, int r, int in) {
u64 *S = RC[in];
u64 *const out_leaf = RC[1-in] + 2*l;
const int sn = r - l;
const u32 xbase=W_X(S[2*l+1]);
if(W_X(S[2*(r-1)+1])-xbase<256u) build_leaf_keys<true>(S,l,sn,xbase);
else build_leaf_keys<false>(S,l,sn,xbase);
byte_leaf_sort(byte_lzk, sn);
{
u32 prevz = byte_lzk[0] >> 8, rk = 1;
byte_lrz[byte_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 *)(byte_lzk + q));
__m256i vp = _mm256_load_si256((const __m256i *)(byte_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;
const __m256i bytes=_mm256_setr_epi8(0,4,8,12,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,
0,4,8,12,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128,-128);
const __m256i p8=_mm256_shuffle_epi8(vc,bytes);
const __m256i b8=_mm256_shuffle_epi8(rv,bytes);
const u64 km0=(u32)_mm256_extract_epi32(p8,0),km1=(u32)_mm256_extract_epi32(p8,4);
const u64 bm0=(u32)_mm256_extract_epi32(b8,0),bm1=(u32)_mm256_extract_epi32(b8,4);
for (int i = 0; i < 4; i++) byte_lrz[(km0 >> (8 * i)) & 255u] = (u8)(bm0 >> (8 * i));
for (int i = 0; i < 4; i++) byte_lrz[(km1 >> (8 * i)) & 255u] = (u8)(bm1 >> (8 * i));
}
if (q > 1) prevz = byte_lzk[q - 1] >> 8;
for (; q < sn; q++) {
const u32 v = byte_lzk[q], zv = v >> 8;
if (zv != prevz) { prevz = zv; rk++; }
byte_lrz[v & 255u] = (u8)((rk - 1u) ^ 0x80u);
}
}
byte_leaf_sort(lk, sn);
for (int q = 0; q < sn; q++) {
const int sr = (int)(lk[q] & 255u);
byte_lxb[q] = byte_lrx[sr]; byte_lzb[q] = byte_lrz[sr];
}
{
const __m256i v7 = _mm256_set1_epi8(0x7F);
for (int k = sn; k < 288; k += 32) {
_mm256_storeu_si256((__m256i *)(byte_lxb + k), v7);
_mm256_storeu_si256((__m256i *)(byte_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;
{const u64 *p=S+2*(l+(lk[0]&255u));_mm_store_si128((__m128i*)out_leaf,_mm_load_si128((const __m128i*)p));}
asm volatile(".p2align 3" ::: "memory");
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)byte_lxb[q+u]);Z[u]=_mm256_set1_epi8((char)byte_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*)(byte_lxb+k)),z=_mm256_load_si256((const __m256i*)(byte_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*)(byte_lxb+k)),z=_mm256_load_si256((const __m256i*)(byte_lzb+k));
#pragma GCC unroll 4
for(int u=0;u<4;u++){
__m256i m=byte_prefix(G[u]-k);
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*)(byte_lxb+t)),z=_mm256_load_si256((const __m256i*)(byte_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*)(byte_lxb+t)),z=_mm256_load_si256((const __m256i*)(byte_lzb+t));__m256i m=byte_prefix(G[u]-t);A[u]=_mm256_sub_epi8(A[u],_mm256_and_si256(m,_mm256_and_si256(_mm256_cmpgt_epi8(X[u],x),_mm256_cmpgt_epi8(Z[u],z))));}
}
}
__m256i 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));
const __m128i z128=_mm_setzero_si128();
const __m256i add01=_mm256_cvtepu32_epi64(_mm_unpacklo_epi32(sums,z128));
const __m256i add23=_mm256_cvtepu32_epi64(_mm_unpackhi_epi32(sums,z128));
u64 *const L0=out_leaf+2*q,*const L1=out_leaf+2*q+4;
const u64 *P0=S+2*(l+(lk[q]&255u)),*P1=S+2*(l+(lk[q+1]&255u));
const u64 *P2=S+2*(l+(lk[q+2]&255u)),*P3=S+2*(l+(lk[q+3]&255u));
__m256i V0=_mm256_inserti128_si256(_mm256_castsi128_si256(_mm_load_si128((const __m128i*)P0)),_mm_load_si128((const __m128i*)P1),1);
__m256i V1=_mm256_inserti128_si256(_mm256_castsi128_si256(_mm_load_si128((const __m128i*)P2)),_mm_load_si128((const __m128i*)P3),1);
V0=_mm256_add_epi64(V0,add01);V1=_mm256_add_epi64(V1,add23);
asm("vmovdqu %1,%0" : "=m"(*(__m256i_u*)L0) : "x"(V0));
asm("vmovdqu %1,%0" : "=m"(*(__m256i_u*)L1) : "x"(V1));
}
for (; q < sn; q++) {
if ((lk[q] >> 8) != (lk[q - 1] >> 8)) g = q;
const __m256i mxj = _mm256_set1_epi8((char)byte_lxb[q]);
const __m256i mzj = _mm256_set1_epi8((char)byte_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 *)(byte_lxb + k))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(byte_lzb + k))));
__m256i c1 = _mm256_and_si256(
_mm256_cmpgt_epi8(mxj, _mm256_load_si256((const __m256i *)(byte_lxb + k + 32))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(byte_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 *)(byte_lxb + k))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(byte_lzb + k))));
vacc = _mm256_sub_epi8(vacc, c);
}
if (k < g) {
const __m256i msk = byte_prefix(g-k);
__m256i c = _mm256_and_si256(
_mm256_cmpgt_epi8(mxj, _mm256_load_si256((const __m256i *)(byte_lxb + k))),
_mm256_cmpgt_epi8(mzj, _mm256_load_si256((const __m256i *)(byte_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));
const u64 *P=S+2*(l+(lk[q]&255u));
_mm_store_si128((__m128i*)(out_leaf+2*q),_mm_add_epi64(_mm_load_si128((const __m128i*)P),_mm_cvtsi64_si128(acc)));
}
}
return 1-in;
}
static int cdq_leaf(int l, int r, int in) {
u64 *S = RC[in];
const int sn = r - l;
for (int k = 0; k < sn; k++) {
u64 w0 = S[2 * (l + k)], w1 = S[2 * (l + k) + 1];
lex[k] = (u32)((w1 >> 20) & 0xFFFFFu);
ley[k] = (u32)(w0 >> 40);
ler[k] = (u32)(w1 & 0xFFFFFu);
}
for (int j = l + 1; j < r; j++) {
const int jl = j - l;
const u32 xj = W_X(S[2 * j + 1]), yj = (u32)(S[2 * j] >> 40), tj = W_T(S[2 * j + 1]);
const __m256i mxj = _mm256_set1_epi32((int)xj);
const __m256i myj = _mm256_set1_epi32((int)yj);
const __m256i mtj = _mm256_set1_epi32((int)tj);
u32 acc = 0;
int k = 0;
for (; k + 8 <= jl; k += 8) {
__m256i c = _mm256_and_si256(_mm256_cmpgt_epi32(mxj, _mm256_loadu_si256((const __m256i *)(lex + k))),
_mm256_and_si256(_mm256_cmpgt_epi32(myj, _mm256_loadu_si256((const __m256i *)(ley + k))),
_mm256_cmpgt_epi32(mtj, _mm256_loadu_si256((const __m256i *)(ler + k)))));
acc += (u32)__builtin_popcount((u32)_mm256_movemask_ps(_mm256_castsi256_ps(c)));
}
for (; k < jl; k++) acc += (u32)((lex[k] < xj) & (ley[k] < yj) & (ler[k] < tj));
S[2 * j] += acc;
}
{
if (sn <= 64) {
for (int k = 0; k < sn; k++) lk[k] = (ley[k] << 7) | (u32)k;
for (int k = sn; k < 64; k++) lk[k] = 0xFFFFFFFFu;
{
__m256i r[8];
for (int q = 0; q < 8; q++) r[q] = _mm256_load_si256((const __m256i *)(lk + 8 * q));
bs64(r);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(lk + 8 * q), r[q]);
}
for (int k = 0; k < sn; k++) {
const int sr = (int)(lk[k] & 127u);
_mm_store_si128((__m128i *)(void *)(ltmp + 2 * k), _mm_load_si128((const __m128i *)(const void *)(S + 2 * (l + sr))));
}
} else if (sn <= 128) {
for (int k = 0; k < sn; k++) lk[k] = (ley[k] << 7) | (u32)k;
for (int k = sn; k < 128; k++) lk[k] = 0xFFFFFFFFu;
{
__m256i r[8];
for (int q = 0; q < 8; q++) r[q] = _mm256_load_si256((const __m256i *)(lk + 8 * q));
bs64(r);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(lk + 8 * q), r[q]);
for (int q = 0; q < 8; q++) r[q] = _mm256_load_si256((const __m256i *)(lk + 64 + 8 * q));
bs64(r);
for (int q = 0; q < 8; q++) _mm256_store_si256((__m256i *)(lk + 64 + 8 * q), r[q]);
}
bm128(lk);
for (int k = 0; k < sn; k++) {
const int sr = (int)(lk[k] & 127u);
_mm_store_si128((__m128i *)(void *)(ltmp + 2 * k), _mm_load_si128((const __m128i *)(const void *)(S + 2 * (l + sr))));
}
} else {
for (int k = 0; k < sn; k++) lkey[k] = ((u64)ley[k] << 20) | (u64)(u32)k;
for (int i = 1; i < sn; i++) {
u64 kv = lkey[i];
int k = i;
while (k > 0 && lkey[k - 1] > kv) { lkey[k] = lkey[k - 1]; k--; }
lkey[k] = kv;
}
for (int k = 0; k < sn; k++) {
const int sr = (int)(u32)(lkey[k] & 0xFFFFFu);
_mm_store_si128((__m128i *)(void *)(ltmp + 2 * k), _mm_load_si128((const __m128i *)(const void *)(S + 2 * (l + sr))));
}
}
for (int k = 0; k < sn; k++) _mm_store_si128((__m128i *)(void *)(S + 2 * (l + k)), _mm_load_si128((const __m128i *)(const void *)(ltmp + 2 * k)));
}
return in;
}
template <int LV, int LF> static int cdq(int l, int r, int in) {
int s = r - l;
if (s <= 1) return in;
if (s <= LF) return (LF == 256) ? byte_rank_leaf(l, r, in) : cdq_leaf(l, r, in);
int m = (l + r) >> 1;
int isroot = (g_root_pending && l == 0 && r == g_nz);
if (isroot) g_root_pending = 0;
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; }
}
}
int b1 = cdq<LV, LF>(l, m, in);
int b2 = cdq<LV, LF>(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 (isroot) { node_fused_root<LV>(l, m, r, b1); return -1; }
node_fused<LV>(l, m, r, b1, out);
return out;
}
if (mode == 2) {
int out = 1 - b1;
merge_run(l, m, r, b1, out);
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);
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; }
g_nz = n;
mktab();
unsigned char *histx=(unsigned char *)(void *)RC[1], *histz=histx+131072;
u32 *hz=(u32 *)(void *)(histx+262144);
u32 *hc=(u32 *)(void *)(histx+786432);
bool narrow=n<131072;
if(narrow){
memset(histx,0,(size_t)n+1);memset(histz,0,(size_t)n+1);
for(int i=0;i<n;i++){histx[x[i]]++;histz[z[i]]++;}
u32 sx=0,sz=0;
{
int v=0;
for(;v+16<=n+1;v+=16){
auto build16 = [&](const unsigned char* h,u32* p,u32& sum) {
__m256i raw=_mm256_cvtepu8_epi16(_mm_loadu_si128((const __m128i*)h));
__m256i val=_mm256_add_epi16(raw,_mm256_slli_si256(raw,2));
val=_mm256_add_epi16(val,_mm256_slli_si256(val,4));
val=_mm256_add_epi16(val,_mm256_slli_si256(val,8));
__m256i low=_mm256_permute2x128_si256(val,val,0x08);
low=_mm256_shuffle_epi8(low,_mm256_set1_epi16(0x0f0e));
val=_mm256_add_epi16(val,low);
__m256i ex=_mm256_sub_epi16(val,raw);
__m256i base=_mm256_set1_epi32((int)sum);
_mm256_storeu_si256((__m256i*)p,_mm256_add_epi32(base,_mm256_cvtepu16_epi32(_mm256_castsi256_si128(ex))));
_mm256_storeu_si256((__m256i*)(p+8),_mm256_add_epi32(base,_mm256_cvtepu16_epi32(_mm256_extracti128_si256(ex,1))));
sum+=(unsigned)_mm256_extract_epi16(val,15);
};
build16(histx+v,hc+v,sx);build16(histz+v,hz+v,sz);
}
for(;v<=n;v++){u32 cx=histx[v],cz=histz[v];hc[v]=sx;hz[v]=sz;sx+=cx;sz+=cz;}
}
narrow=(sx==(u32)n&&sz==(u32)n);
}
if(narrow){
u64 *D=RC[0];
for(int i=0;i<n;i++){
if(i+48<n){__builtin_prefetch(&D[2*hc[x[i+32]]]);__builtin_prefetch(&hz[z[i+32]]);__builtin_prefetch(&hc[x[i+48]]);}
u32 zv=z[i],h=hz[zv],T=h&0x1ffffu,R=T+(h>>17);
hz[zv]=h+(1u<<17);
u32 xv=x[i],t=hc[xv]++;
__m128i rv=_mm_set_epi64x((long long)(((u64)T<<40)|((u64)xv<<20)|R),(long long)(((u64)y[i]<<40)|((u64)i<<20)));
_mm_storeu_si128((__m128i*)(void*)(D+2*t),rv);
}
}else{
memset(H64, 0, (size_t)(n + 1) * 8);
memset(CNT, 0, (size_t)(n + 1) * 4);
for (int i = 0; i < n; i++) {
H64[z[i]]++;
CNT[x[i]]++;
}
{
u32 acc = 0;
for (int v = 0; v <= n; v++) { u32 c = (u32)(H64[v] & 0xFFFFFu); H64[v] = (u64)acc << 20; acc += c; }
}
{
u32 acc = 0;
int v = 0;
for (; v + 8 <= n + 1; v += 8) {
__m256i x = _mm256_loadu_si256((const __m256i *)(CNT + v));
__m256i p = _mm256_add_epi32(x, _mm256_slli_si256(x, 4));
p = _mm256_add_epi32(p, _mm256_slli_si256(p, 8));
__m128i lo = _mm256_castsi256_si128(p);
__m128i hi = _mm256_extracti128_si256(p, 1);
hi = _mm_add_epi32(hi, _mm_shuffle_epi32(lo, 0xFF));
__m256i pi = _mm256_inserti128_si256(_mm256_castsi128_si256(lo), hi, 1);
__m256i ex = _mm256_add_epi32(_mm256_sub_epi32(pi, x), _mm256_set1_epi32((int)acc));
_mm256_storeu_si256((__m256i *)(CNT + v), ex);
acc += (u32)_mm_extract_epi32(hi, 3);
}
for (; v <= n; v++) { u32 c = CNT[v]; CNT[v] = acc; acc += c; }
}
{
u64 *D = RC[0];
for (int i = 0; i < n; i++) {
if (i + 12 < n) { __builtin_prefetch(&D[2 * CNT[x[i + 12]]]); }
u32 zv = z[i];
u64 h = H64[zv];
u32 T = (u32)(h >> 20);
u32 R = T + (u32)(h & 0xFFFFFu);
H64[zv] = h + 1;
u32 xv = x[i];
u32 t = CNT[xv]++;
__m128i _rv = _mm_set_epi64x((long long)(((u64)T << 40) | ((u64)xv << 20) | (u64)R),
(long long)(((u64)y[i] << 40) | ((u64)i << 20)));
_mm_storeu_si128((__m128i *)(void *)(D + 2 * t), _rv);
}
}
}
g_rootout = out; g_root_pending = 1;
int bb = (n <= 262144) ? cdq<3, 256>(0, n, 0) : cdq<4, 64>(0, n, 0);
g_root_pending = 0; g_rootout = 0;
if (bb >= 0) {
const u64 *D = RC[bb];
for (int p = 0; p < n; p++) {
if (p + 128 < n) __builtin_prefetch(&out[W_ORIG(D[2 * (p + 128)])]);
out[W_ORIG(D[2 * p])] = W_A(D[2 * p]);
}
}
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 7.229 ms | 3 MB + 484 KB | Accepted | Score: 100 | 显示更多 |