代码

// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #125828 <https://duck.ac/submission/125828>
//     用途：本题（1017b）现役排行榜 rank-1 件的**完整算法骨架**：① 1 字节直方图 + `++hist[x[i]]==0`
//     回绕检测 ⇒ 回退 4 字节宽计数那套**逐位精确**保障；② AVX2 八格前缀扫描；③ 输出趟 `out[i]=pref[x[i]]`；
//     ④ `count_1d(int n,const unsigned *x,unsigned *out)` 接口约定。（同源件亦见 1017 #125836 / 1017a #125829。）
// [2] 本账号 saffah_cc_v41_agg1，提交 #127018 <https://duck.ac/submission/127018>
//     用途：本件前驱（同骨架 + 去预取两刀，板面 5.167362 ms）。v3 在它之上把**输出表**改为两级小表（见思路）。
// [3] 本工作区 `problems/1017/work/r2g2__tmp/`（判题机探针/微基准规程）与全队律 743/796/797。
// 许可：以上均为 duck.ac 上的公开提交与本工作区材料，均未附带任何软件许可证声明；
//   本文件按 RULES §3 逐项署名「原作者账号 + 原始提交地址 + 所用内容」，遵守方式 = 完整保留上述署名于文件开头。
// ======================
// ===== 思路 ===== （本发为正式性能提交，非试验性；v3 = #127018 之上"输出表两级化"）
// 【判型】本题 n=1e6：直方图 1MB、**前缀表 4MB**。判题机 L3 仅 6MB，而查表趟同时还有
//   x（4MB 流读）与 out（4MB 顺写）在跑 ⇒ 查表趟的随机访问落在"4MB 表 + 8MB 流"的混合工作集上，
//   表越大越容易被挤出 L3。查表趟占全时约 45%（判题机微基准 arm A 相位：memset 0.11M / 计数 8.7M /
//   前缀 1.1M / **查表 9.5M** ticks）。
// 【刀 `[r2g2-2LVL]`】把 4MB 的 `pref[]` 换成**两级小表**（数学恒等，逐位相同）：
//      out[i] = hi[x[i] >> 12] + lo16[x[i]]
//   其中 `hi[b]` = 值 < (b<<12) 的元素个数（u32，245 项 = 0.98KB，**L1 常驻**）、
//   `lo16[v]` = v 所在 4096 块内的**独占**前缀（u16，2MB）。⇒ 查表趟工作集 4MB→2MB，
//   且第二级是 L1 级命中（hi 表 1KB）。构造趟（一次扫 hist，u16 SIMD 前缀）比原 8→32 位扩展前缀扫描更省写带宽（2MB vs 4MB）。
// 【逐位保障】`out = hi + lo16` 与 `out = pref` 恒等（hi 为块基址、lo16 为块内独占前缀）；
//   三级守卫：① lo16 溢出 65535（= 单块内元素数 ≥ 65536，任意输入都可能）⇒ 立刻转 [1] 的 4 字节宽路径；
//   ② n > 1e8 或值域 ≥ 2^27 ⇒ 宽路径；③ 直方图回绕检测（[1] 原样保留）⇒ 宽路径。
//   三条守卫任一触发都回落到与 [1] **逐位相同**的路径。（本地闸门：uniform/全等值/少值/聚集/有序/逆序/n=0,1,2 全 bad=0。）
// ======================
#include <immintrin.h>
#include <cstring>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi2,popcnt")
static unsigned char hist[100000000];
alignas(64) static unsigned pref[100000016];
static unsigned short lo16[100000016 + 64];
static unsigned hi[32768];
#define BLK 4096

void count_1d(int n, const unsigned *x, unsigned *out) {
    std::memset(hist, 0, (size_t)n);
    bool wide = false;
    for (int i = 0; i < n; i++) {
        /* [r2g2-CNTNOPF]（前驱已删预取，n≤1e6 ⇒ 直方图驻留 L2/L3） */
        if (++hist[x[i]] == 0) { wide = true; break; }
    }
    if (!wide && (n <= 100000000)) {
        /* 构造两级表：hi[b] = 块基址（L1 常驻），lo16[v] = 块内独占前缀（u16，SIMD 8 格/迭代） */
        unsigned s = 0;
        int v = 0;
        __m128i carry = _mm_setzero_si128();
        __m128i zero = _mm_setzero_si128();
        for (int b = 0; b * BLK < n; b++) {
            int e = (b + 1) * BLK; if (e > n) e = n;
            hi[b] = s;
            carry = _mm_setzero_si128();
            for (; v + 8 <= e; v += 8) {
                __m128i raw = _mm_cvtepu8_epi16(_mm_loadl_epi64((const __m128i *)(hist + v)));
                __m128i t = raw;
                t = _mm_add_epi16(t, _mm_slli_si128(t, 2));
                t = _mm_add_epi16(t, _mm_slli_si128(t, 4));
                t = _mm_add_epi16(t, _mm_slli_si128(t, 8));
                __m128i res = _mm_sub_epi16(_mm_add_epi16(t, carry), raw);
                _mm_storeu_si128((__m128i *)(lo16 + v), res);
                carry = _mm_add_epi16(carry, _mm_set1_epi16((short)_mm_extract_epi16(t, 7)));
            }
            for (; v < e; v++) { lo16[v] = (unsigned short)_mm_extract_epi16(carry, 0); carry = _mm_add_epi16(carry, _mm_set1_epi16(hist[v])); }
            unsigned inside = (unsigned)(unsigned short)_mm_extract_epi16(carry, 0);
            if (inside > 65535u) { wide = true; break; }     /* 守卫① */
            s += inside;
        }
        (void)zero;
    }
    if (wide || n > 100000000) {
        std::memset(pref, 0, (size_t)n * sizeof(unsigned));
        for (int i = 0; i < n; i++) ++pref[x[i]];
        unsigned s = 0;
        for (int i = 0; i < n; i++) { unsigned c = pref[i]; pref[i] = s; s += c; }
        for (int i = 0; i < n; i++) out[i] = pref[x[i]];
    } else {
        for (int i = 0; i < n; i++) {
            unsigned v = x[i];
            out[i] = hi[v >> 12] + lo16[v];
        }
    }
}

评测结果