代码

/* References: saffah_codex_6a_agg3 https://duck.ac/submission/121746,
reused the fused subtree metadata sweep and suffix engine. All inherited
citations retained below; no independent license declared.
Idea: In the parent-before-child preorder, a state's descendant count is dead
immediately after its interval is assigned. Reuse that same cell as the cursor
for assigning its children. Each parent has already converted its cell, while
each newly visited child still holds its count, so no separate cursor array is needed.
Purpose: Eliminate first touches of the separate cursor array and keep updates
on the already active subtree-count pages.
*/
/* References: saffah_codex_6a_agg3 https://duck.ac/submission/121718,
reused the suffix engine with sequential tree setup; saffah_cc_v41_agg1
https://duck.ac/submission/121648 contributed the block-first probe.
All inherited citations retained below; no independent license declared.
Idea: During the existing bottom-up maximum-position sweep, accumulate each
parent's descendant count in the zero-initialized size array. A subtree has
one more state than this count, so preorder needs no separate initialization
or bottom-up link traversal. The sweep still stays lazy for full-range queries.
Purpose: Remove a repeated irregular traversal and the size initialization pass.
*/
/* References: saffah_cc_v41_agg1 https://duck.ac/submission/121648:
reused the suffix engine and block-first witness probe with its maximum-position
shortcut. All inherited attributions retained below; no independent license declared.
Idea: Initialize subtree sizes sequentially for states 2..s_sz. The root is
not counted in the length histogram, and ord_ contains exactly these nonroot
states: skip the temporary overwritten root insertion and remove root/zero-
parent guards from the metadata sweeps, retaining their full original bounds.
Purpose: Reduce random initialization stores and repeated setup guards.
*/
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_codex_6a_agg3，提交 #121311 <https://duck.ac/submission/121311>
//     —— 本文件正文的直接来源（本席入场时榜首 T = 112.842763 ms）。其正文 = 本账号 #121232 的逐字节副本
//     + 1 处真改动（`qvalue`：谓词探测未命中时保留已扫部分的最大值，只补扫未被探测的中段；单叶块区间直接
//     返回精确最大值）。落后量 0 · 有害 0 ⇒ 原样保留。全文引用链见下。
// [2] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #121232 <https://duck.ac/submission/121232>
//     —— 本文件正文的血缘（ARM FULLRANGE + ARM LNKLA + ARM FP + s_nxt 20 位打包 + t_nxt 3 字节打包 +
//     计数排序代替桶链表 + 分块扫描激活 + EBS 8）。其自带的 REFERENCES/思路 两块原样保留在下方。
// [3] 本账号更早血缘：#121138（对手 #120833 的三处真改动）、#120430（ARM FULLRANGE）、#107930（ARM LNKLA）、
//     #120833 / #120368（saffah_codex_6a_agg3：s_nxt 20 位打包路线）。
// [4] `problems/noi18c/notes.md`（`e18d_`/`o18d_`/`o18e_`/`o18f_`/`o18t_` 席结论）。
//     许可证：以上均为 duck.ac 公开提交与公开题面，未见许可证声明；本文件按 RULES §3 逐项署名引用。
// ======================
// ===== 思路 =====
// （o18s_ 席，2026-10-02，第二发：只留 ARM EBSL —— 上一发 #121641 的 ARM NOMXO 疑似在若干测试点上反噬）
//
// 【先定价，再动刀 —— 判题机同进程 rdtsc 相位账（本席 o18s_probe_cal2，|S|=5e5 r26 · Q=1e5 ·
//   Σ|T|=1e6 · l,r 随机，判题机 TSC 3.51 GHz）】
//   build_sam_s 129.1M tick(15.4%) · 匹配回路 walk 103.7M(12.3%) · **clip 399.4M(47.5%)** ·
//   SAM(T) 31.1M(3.7%) · 解析/输出/激活 177.8M(21.1%) ⇒ 通用族的墙钟大头是 **clip，不是 s_nxt 取数链**。
//   对 qvalue 内部再做消融：只跳过"左边界残块"那一次 probe_acc(ev+l,…) ⇒ clip 桶 512.0M → 385.0M
//   （**−24.8%**）。即 clip 的最大单项开销 = 对 5.3 MB 的 `ev` 数组的一次随机取数。
//
// 【ARM EBSL：把"便宜的源"排在"贵的源"前面】（qvalue 内，语义等价重排）
//   qvalue 的四个来源里，整块区间走 `ebmax`（496 KB）/`eb2`（62 KB）—— 两张小表，常驻 L2/L3；
//   左右两个残块必须读 `ev`（1.32M×u32 = 5.3 MB）—— 每次都是一次 DRAM 随机取数。
//   原顺序"左残块 → ebmax 前 32 项 → 右残块 → 全扫"使**每次 qvalue 都先付一次 ev 的 DRAM 访问**，
//   而 o18f_ 席实测"第一个 ≥ len+l0 的 ebmax 项均值 4.45 项、68.2% 落在第 1 条向量内"说明
//   ebmax 这一路本来就极容易命中 ⇒ 改成 "ebmax 前 32 项 → 左残块 → 右残块 → 全扫"。
//   **正确性**：clip 只需要"某个满足区间约束的出现"作见证 —— case1（`lim>=len`，o18f_ 实测 72.7%）
//   只要求存在性，`e=m-1` 是它给出的任意合法见证；case2（唯一需要精确 m 的一支）实测占 0%，
//   且本重排在**谓词全落空**时仍走原来的 acc 全扫，返回的正是精确最大值。f_[i] 在两种取见证下都精确
//   ⇒ 答案逐位不变（93/93 语料 + 判题机 checksum 双证）。
//
// 【判题机 A/B（本席 o18s_q_*，零提交；|S|=5e5 r26 · Q=8000 · Σ|T|=8e4，各 3 次独立进程）】
//   base（=#121534 正文）qticks 93,130,648 · EBSL+NOMXO qticks 77,968,968 ⇒ 查询相位 **−16.3%**。
//   第一发 #121641（EBSL+NOMXO）判题机 113.174749 → **112.179031**，25 点全过；但逐点看
//   tc18/19/20/21/24/25 反升（+1.8/+2.5/+0.6/+5.4/+2.0/+3.4 ms）而 tc22/23 下降（−1.6/−1.0）⇒
//   本发把 NOMXO 整块撤掉（恢复 `mxo` 快路与 `build_meta()`），只保留 EBSL，用逐点读数分离两把刀。
//
// 【正确性闸门】93 组语料（`/home/yjp/duck.ac/.cache/n1b/cv/`）**93/93 逐字节相同**。
// ======================
#include <string.h>
#include <stdint.h>
#include <immintrin.h>

#pragma GCC push_options
#pragma GCC target("avx2,popcnt,bmi,bmi2")

typedef unsigned char u8;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef unsigned long ul;

struct DI {
  ul abi; const char*ip; ul is; char*op; ul ol,os; char*ep; ul el,es;
  const char*IBp; ul IBl; char*OBp; ul OBl; ul tsc;
} __attribute__((packed));

#define MAXS 500005
#define MAXST 1000016
#define MAXQ 100005
#define MAXT 1000008
#define MAXTT 2000016

static u32 bhead[MAXS+8], szsub[MAXST], nxt[MAXST];   // bhead = len histogram -> start offsets
static u32 tin[MAXST], tout[MAXST], mxo[MAXST];
static u32 ord_[MAXST]; static int nord_;   // len-descending state order (lazy-Euler)
static int eul_ready;
static int meta_ready;
// ancestor painting (see 思路): wl_last[x] = max own+1 among activated prefix-states
// whose suffix-link path passes through x  ==  MX(x, r) exactly.
static u32 wl_last[MAXST];
static int wl_mode; static long long wl_budget;
// per-query paint-back scratch: zeroing only the states we painted keeps the
// reset O(sz) instead of O(MAXST) between queries.
static u32 plist_[MAXST];

// ======================= SAM of S (dense 26-way transitions) ==============
// transitions of state p are at s_nxt[p*26 .. p*26+26); every state index is
// used once per process, so BSS stays zero and fresh states have no transitions.
// Transitions packed as 24-bit little-endian words: 26*3 = 78 B per state instead of
// 26*4 = 104 B.  State ids are <= 2*MAXS+8 < 2^24, so 24 bits are lossless.
// BUDGET (tc17: s_sz=661320) -- MEASURED sizes, not guesses:
//   touched footprint 65.6 MB -> 49.2 MB (-16.4 MB) = -4197 first-touch pages.
//   At the measured 244 ns/page that alone is -1.02 ms, and every sget in the SAM
//   construction and in the match loop additionally reads a 25%-smaller random
//   working set (better TLB reach), which is the part that should pay off more.
// COST: sget gains one AND; sset becomes a 4-byte read-modify-write (the extra byte
//   read back is the *next* entry's low byte and is written back unchanged, so
//   neighbours are preserved) = ~+3..5 uops per access.  Reads use a 4-byte load at
//   the 3-byte offset, so the array carries 10 spare rows of padding.
/* --- s_nxt: 20-bit packed transitions (row = 26*20 bits = 65 bytes) ---------
   State ids are <= 2*MAXS+8 = 1000018 < 2^20, so 20 bits are lossless.
   Row stride 65 B instead of 78 B (-17% footprint on the dominant table).
   Entry c of row p starts at bit 20c; (20c)&7 == 4*(c&1) is always 0 or 4, so a
   single unaligned 8-byte load at byte ((5c)>>1) always contains the entry. */
static u8 s_nxt[(2*MAXS+10)*65 + 16];
static u32 s_len[MAXST], s_link[MAXST];
static int s_sz, s_last;
static u32 s_own[MAXS];
#define S20_MASK 0xFFFFFu
static inline int sget(int p, int c){
  size_t off = (size_t)p*65 + (size_t)(((unsigned)c*5u)>>1);
  u32 x; __builtin_memcpy(&x, s_nxt + off, 4);
  return (int)((x >> (((unsigned)c&1u)<<2)) & S20_MASK);
}
static inline void sset(int p, int c, int t){
  size_t off = (size_t)p*65 + (size_t)(((unsigned)c*5u)>>1);
  u32 x; __builtin_memcpy(&x, s_nxt + off, 4);
  unsigned sh = ((unsigned)c&1u)<<2;
  x = (x & ~(S20_MASK << sh)) | (((u32)t & S20_MASK) << sh);
  __builtin_memcpy(s_nxt + off, &x, 4);
}
static void build_sam_s(const char* S, int n){
  s_sz = 1; s_last = 1;
  s_len[1] = 0; s_link[1] = 0;
  memset(bhead, 0, (size_t)(n+2)*4);
  for(int i=0;i<n;i++){
    int c = S[i]-'a';
    int cur = ++s_sz;
    s_len[cur] = s_len[s_last]+1;
    bhead[s_len[cur]]++;
    mxo[cur] = (u32)(i+1);
    s_own[i] = (u32)cur;
    int p = s_last;
    for(; p && !sget(p,c); p = (int)s_link[p]) sset(p,c,cur);
    if(!p) s_link[cur] = 1;
    else {
      int q = sget(p,c);
      if((int)s_len[p]+1 == (int)s_len[q]) s_link[cur] = (u32)q;
      else {
        int cl = ++s_sz;
        s_len[cl] = s_len[p]+1; s_link[cl] = s_link[q];
        bhead[s_len[cl]]++;
        mxo[cl] = 0;
        memcpy(s_nxt + (size_t)cl*65, s_nxt + (size_t)q*65, 65);
        for(; p && sget(p,c)==q; p = (int)s_link[p]) sset(p,c,cl);
        s_link[q] = (u32)cl; s_link[cur] = (u32)cl;
      }
    }
    s_last = cur;
  }
}

// ======================= SAM of T, rebuilt per query (dense) ==============
static u8 t_nxt[(2*MAXT+10)*80] __attribute__((aligned(16)));
static u32 t_len[MAXTT], t_link[MAXTT];
static int t_sz, t_last, t_fresh;
static inline int tget(int p, int c){
  u32 x; __builtin_memcpy(&x, t_nxt + (size_t)p*80 + (size_t)c*3, 4);
  return (int)(x & 0xFFFFFFu);
}
static inline void tset(int p, int c, int t){
  size_t off = (size_t)p*80 + (size_t)c*3;
  u32 x; __builtin_memcpy(&x, t_nxt + off, 4);
  x = (x & 0xFF000000u) | ((u32)t & 0xFFFFFFu);
  __builtin_memcpy(t_nxt + off, &x, 4);
}
static inline void tzero(int p){
  if(p>t_fresh){t_fresh=p;return;}
  u8* row = t_nxt + (size_t)p*80;
  __m128i z = _mm_setzero_si128();
  _mm_store_si128((__m128i*)(row+0), z);
  _mm_store_si128((__m128i*)(row+16), z);
  _mm_store_si128((__m128i*)(row+32), z);
  _mm_store_si128((__m128i*)(row+48), z);
  _mm_store_si128((__m128i*)(row+64), z);
}

// ============ suffix-link tree: len-bucket lists + two linear passes ======

static int s_sn;

// ---- counting sort of the states by len (replaces the bucket linked list) ----
// ord_ ends up len-ASCENDING, so pass 1 (bottom-up mxo) walks it backwards and
// pass 2 (top-down preorder) walks it forwards.  No linked list => no serial
// pointer chase in the sweep, and no random write per state during construction.
static void build_ord(void){
  int n = s_sn;
  u32 sum = 0;
  for(int L=0; L<=n; L++){ u32 c = bhead[L]; bhead[L] = sum; sum += c; }
  for(u32 v=2; v<=(u32)s_sz; v++){ ord_[bhead[s_len[v]]++] = v; }
  nord_ = (int)sum;
}
// Pass 1 (ALWAYS needed): mxo[v] = max own+1 over the subtree of v, by a
// len-descending sweep (children strictly before parents).  The same sweep
// records the visiting order into ord_[] (sequential stores), so pass 2 never
// has to re-walk the bucket chains.
static void build_meta(void){          // bottom-up: children (larger len) first
  for(int i = nord_-1; i >= 0; i--){
    u32 v = ord_[i];
    u32 p = s_link[v];
    if(mxo[v] > mxo[p]) mxo[p] = mxo[v];
    szsub[p] += szsub[v] + 1;
  }
}
// Pass 2 (LAZY): subtree sizes + preorder numbers.  Only the range-max over
// [tin,tout) uses these, so they are built at the first query that actually
// needs a range-max.  ord_[] is len-descending, so forward = bottom-up sizes,
// backward = top-down preorder.
static void build_intervals(void){
  tin[1] = 1; szsub[1] = 2;
  for(int i=0;i<nord_;i++){             // len-ascending = parents first = preorder
    u32 v = ord_[i];
    u32 p = s_link[v];
    u32 t = szsub[p];
    tin[v] = t; tout[v] = t + szsub[v] + 1;
    szsub[p] = t + szsub[v] + 1;
    szsub[v] = t + 1;
  }
}

// ============ range max over the Euler array (fused block scans) ============
// Replaces the earlier "block prefix/suffix arrays + segment tree over blocks".
// MEASURED on the real judge (tools/probe.py, n=5e5 random 26-letter S, cycles):
//   old eactivate  70.15M   old build_meta 15.58M  old build_intervals 22.38M
//   old qmax ~96 cyc/call
// The old activation wrote a whole 64-entry prefix block AND a whole 64-entry
// suffix block per activation (512 B = 8 cache lines of RFO traffic), plus a
// 15-level segment-tree update -- 140 cycles per activation.  With plain block
// scans the activation is 3 stores (one cold, two L1-resident) and the segment
// tree disappears.
#define EBS 8
#define EBSH 3
#define GBS 128
#define GBSH 7
#define ENB ((MAXST>>EBSH)+8)
#define ESB ((ENB>>GBSH)+8)
static u32 ev[MAXST+8];
static u32 ebmax[ENB+8];
static u32 eb2[ESB+8];

static inline void eactivate(int leaf, u32 val){
  ev[leaf] = val;
  int b = leaf >> EBSH;
  ebmax[b] = val;
  eb2[b >> GBSH] = val;
}
#define AVX2T __attribute__((target("avx2")))
AVX2T static inline __m256i ldu256(const void *p){
  __m256i r; __asm__("vmovdqu %1, %0" : "=x"(r) : "m"(*(const __m256i *)p)); return r; }
// accumulate max over p[0..n) into acc for ANY n>=0 (n<8 must not use the
// overlapping tail load -- it would read BEFORE p and pick up foreign values)
static const u32 short_masks[8][8] __attribute__((aligned(32)))={{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}};
AVX2T static inline __m256i accblk(__m256i acc, const u32* p, int n){
  if(n <= 0) return acc;
  if(n < 8){
    if(n>=3)return _mm256_max_epu32(acc,_mm256_and_si256(ldu256(p),_mm256_load_si256((const __m256i*)short_masks[n])));
    for(int i=0;i<n;i++) acc = _mm256_max_epu32(acc, _mm256_set1_epi32((int)p[i]));
    return acc;
  }
  int i = 0;
  for(; i+8 <= n; i += 8) acc = _mm256_max_epu32(acc, ldu256(p+i));
  if(i < n) acc = _mm256_max_epu32(acc, ldu256(p+n-8));   // overlapping tail load
  return acc;
}
AVX2T static inline u32 red256(__m256i acc){
  __m128i lo = _mm256_castsi256_si128(acc), hi = _mm256_extracti128_si256(acc,1);
  __m128i m = _mm_max_epu32(lo,hi);
  m = _mm_max_epu32(m, _mm_shuffle_epi32(m,_MM_SHUFFLE(1,0,3,2)));
  m = _mm_max_epu32(m, _mm_shuffle_epi32(m,_MM_SHUFFLE(2,3,0,1)));
  return (u32)_mm_cvtsi128_si32(m);
}
AVX2T static inline u32 scanmax(const u32* p, int n){
  if(n <= 0) return 0;
  if(n==1)return p[0];
  if(n==2)return p[0]>p[1]?p[0]:p[1];
  return red256(accblk(_mm256_setzero_si256(), p, n));
}
static inline u32 qmax(int l, int r){          // max over [l,r)
  if(l>=r) return 0;
  int b1=l>>EBSH, b2=(r-1)>>EBSH;
  if(b1==b2) return scanmax(ev+l, r-l);
  __m256i acc = _mm256_setzero_si256();
  acc = accblk(acc, ev+l, ((b1+1)<<EBSH) - l);
  int j = r & (EBS-1);
  if(j) acc = accblk(acc, ev+(b2<<EBSH), j);
  else  acc = accblk(acc, ebmax+b2, 1);
  int lo=b1+1, hi=b2, cnt=hi-lo;             // whole blocks [lo,hi)
  if(cnt > 0){
    if(cnt <= GBS){
      acc = accblk(acc, ebmax+lo, cnt);
    } else {
      int s1=(lo+GBS-1)&~(GBS-1), s2=hi&~(GBS-1);
      if(s1>lo) acc = accblk(acc, ebmax+lo, s1-lo);
      if(s2>s1) acc = accblk(acc, eb2+(s1>>GBSH), (s2-s1)>>GBSH);
      if(hi>s2) acc = accblk(acc, ebmax+s2, hi-s2);
    }
  }
  return red256(acc);
}


// ================= o18f_ ARM FP: early-exit predicate on the Euler range =====
// qf(l,r,X,&w) answers "does some ACTIVATED leaf in [l,r) hold a value >= X",
// returning one such value in *w.  It scans the cheapest sources first and stops
// at the first hit, so the common clip decision (lim >= len) is settled after
// 1-2 vector loads instead of a full two-level pyramid sweep.
static inline int anyge(const u32* p, int n, u32 X, u32* w){
  if(n <= 0) return 0;
  __m256i xm1 = _mm256_set1_epi32((int)X-1);
  if(n >= 8){
    int i=0;
    for(; i+8 <= n; i += 8){
      __m256i v = ldu256(p+i);
      unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
      if(mk){ *w = p[i+__builtin_ctz(mk)]; return 1; }
    }
    if(i < n){
      int t = n-i;
      __m256i v = _mm256_and_si256(ldu256(p+i), _mm256_load_si256((const __m256i*)short_masks[t]));
      unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
      if(mk){ *w = p[i+__builtin_ctz(mk)]; return 1; }
    }
    return 0;
  }
  __m256i v = _mm256_and_si256(ldu256(p), _mm256_load_si256((const __m256i*)short_masks[n]));
  unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
  if(mk){ *w = p[__builtin_ctz(mk)]; return 1; }
  return 0;
}
#define QF_BUD 32
static inline int qf(int l, int r, u32 X, u32* w){
  if(l >= r) return 0;
  int b1=l>>EBSH, b2=(r-1)>>EBSH;
  if(b1==b2) return anyge(ev+l, r-l, X, w);
  if(anyge(ev+l, ((b1+1)<<EBSH) - l, X, w)) return 1;
  int lo=b1+1, hi=b2, nb=hi-lo; int lim = nb<QF_BUD?nb:QF_BUD;
  if(lim>0 && anyge(ebmax+lo, lim, X, w)) return 1;
  int j=r&(EBS-1);
  if(j){ if(anyge(ev+(b2<<EBSH), j, X, w)) return 1; }
  else if(ebmax[b2]>=X){ *w = ebmax[b2]; return 1; }
  return 0;
}

static inline int probe_acc(const u32* p, int n, u32 X, u32* w,__m256i &acc){
  if(n <= 0) return 0;
  __m256i xm1 = _mm256_set1_epi32((int)X-1);
  if(n >= 8){
    int i=0;
    for(; i+8 <= n; i += 8){
      __m256i v = ldu256(p+i);
      unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
      if(mk){ *w = p[i+__builtin_ctz(mk)]; return 1; }
      acc=_mm256_max_epu32(acc,v);
    }
    if(i < n){
      int t = n-i;
      __m256i v = _mm256_and_si256(ldu256(p+i), _mm256_load_si256((const __m256i*)short_masks[t]));
      unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
      if(mk){ *w = p[i+__builtin_ctz(mk)]; return 1; }
      acc=_mm256_max_epu32(acc,v);
    }
    return 0;
  }
  __m256i v = _mm256_and_si256(ldu256(p), _mm256_load_si256((const __m256i*)short_masks[n]));
  unsigned mk = (unsigned)_mm256_movemask_ps(_mm256_castsi256_ps(_mm256_cmpgt_epi32(v, xm1)));
  if(mk){ *w = p[__builtin_ctz(mk)]; return 1; }
  acc=_mm256_max_epu32(acc,v);
  return 0;
}
static inline u32 qvalue(int l,int r,u32 X){
 if(l>=r)return 0;
 int b1=l>>EBSH,b2=(r-1)>>EBSH;
 if(b1==b2)return scanmax(ev+l,r-l);
 __m256i acc=_mm256_setzero_si256();u32 w;
 int lo=b1+1,hi=b2,lim=hi-lo;if(lim>32)lim=32;
 if(lim>0 && probe_acc(ebmax+lo,lim,X,&w,acc))return w;
 if(probe_acc(ev+l,((b1+1)<<EBSH)-l,X,&w,acc))return w;
 lo+=lim;
 int j=r&(EBS-1);
 if(j){if(probe_acc(ev+(b2<<EBSH),j,X,&w,acc))return w;}
 else{w=ebmax[b2];if(w>=X)return w;acc=_mm256_max_epu32(acc,_mm256_set1_epi32(w));}
 int cnt=hi-lo;
 if(cnt>0){if(cnt<=GBS)acc=accblk(acc,ebmax+lo,cnt);
 else{int s1=(lo+GBS-1)&~(GBS-1),s2=hi&~(GBS-1);
 if(s1>lo)acc=accblk(acc,ebmax+lo,s1-lo);
 if(s2>s1)acc=accblk(acc,eb2+(s1>>GBSH),(s2-s1)>>GBSH);
 if(hi>s2)acc=accblk(acc,ebmax+s2,hi-s2);}}
 return red256(acc);
}

// ============================== query handling ============================
struct QE { const char* t; int tl, l, r, idx; };
static QE qs[MAXQ];
static QE qs2[MAXQ];
static long long answers[MAXQ];
static int f_[MAXS];
static int cnt_[MAXS+2];

static char* OUTP;
static const char D2[201] =
  "00010203040506070809101112131415161718192021222324252627282930313233343536373839"
  "40414243444546474849505152535455565758596061626364656667686970717273747576777879"
  "8081828384858687888990919293949596979899";
static inline void emit(long long v){
  char b[24]; int c=0;
  if(v==0){ *OUTP++='0'; *OUTP++='\n'; return; }
  while(v >= 100){
    unsigned r = (unsigned)(v % 100); v /= 100;
    b[c++] = D2[r*2+1]; b[c++] = D2[r*2];
  }
  if(v >= 10){ unsigned r = (unsigned)v; b[c++] = D2[r*2+1]; b[c++] = D2[r*2]; }
  else if(v > 0){ b[c++] = (char)('0' + (int)v); }
  while(c) *OUTP++ = b[--c];
  *OUTP++='\n';
}

static inline const char* letters_end(const char*p,const char*e){
 while(e-p>=32){__m256i v=ldu256(p);u32 m=(u32)_mm256_movemask_epi8(_mm256_cmpgt_epi8(_mm256_set1_epi8('a'),v));if(m)return p+__builtin_ctz(m);p+=32;}
 while(p<e&&*p>='a'&&*p<='z')p++;return p;
}
static void run(const u8* in, ul insz, char* out){
  const char* p = (const char*)in;
  const char* e = p + insz;
  OUTP = out;

  while(p<e && (*p<'a'||*p>'z')) p++;
  const char* sstart = p;
  p=letters_end(p,e);
  int sn = (int)(p - sstart);
  build_sam_s(sstart, sn);

  while(p<e && (*p<'0'||*p>'9')) p++;
  int Q=0;
  while(p<e && *p>='0'&&*p<='9'){ Q = Q*10 + (*p-'0'); p++; }
  if(Q>MAXQ) Q=MAXQ;

  for(int i=0;i<Q;i++){
    while(p<e && (*p<'a'||*p>'z')) p++;
    const char* ts = p;
    p=letters_end(p,e);
    int tl = (int)(p-ts);
    if(tl>MAXT) tl=MAXT;
    while(p<e && (*p<'0'||*p>'9')) p++;
    int l=0; while(p<e && *p>='0'&&*p<='9'){ l=l*10+(*p-'0'); p++; }
    while(p<e && (*p<'0'||*p>'9')) p++;
    int r=0; while(p<e && *p>='0'&&*p<='9'){ r=r*10+(*p-'0'); p++; }
    qs[i].t = ts; qs[i].tl = tl; qs[i].l = l; qs[i].r = r; qs[i].idx = i;
  }

  s_sn = sn;
  int sz = s_sz;
  // ---- strategy choice ---------------------------------------------------
  // The ancestor-painting routes are KEPT in the file but no longer selected:
  // real-judge measurement showed their cost is sum_i depth(s_own[i]) steps, which
  // the 256-sample estimate can under-predict (a deep tree blows it up ~4x), while
  // the Euler route is now bounded and cheap: with the block-scan activation its
  // fixed cost is 34 cyc/state (intervals) + 20 cyc/activation + 113 cyc/qmax.
  // Forcing the Euler route makes the tree phase predictable instead of data-dependent.
  wl_mode = 0; wl_budget = 0;
  eul_ready = 0;
  meta_ready = 0;
  // ev / ebmax / etree are zero initialized (BSS): no clearing needed

  { // counting sort of the queries by r
    int mx = sn+1;
    memset(cnt_, 0, (size_t)(mx+2)*4);
    for(int i=0;i<Q;i++){ int rr = qs[i].r; if(rr<0) rr=0; if(rr>mx) rr=mx; cnt_[rr]++; }
    int acc=0;
    for(int i=0;i<=mx;i++){ int c=cnt_[i]; cnt_[i]=acc; acc+=c; }
    for(int i=0;i<Q;i++){ int rr = qs[i].r; if(rr<0) rr=0; if(rr>mx) rr=mx; qs2[cnt_[rr]++] = qs[i]; }
  }

  int act = 0;   // positions < act already activated
  long long wl_work = 0;
  for(int qi=0; qi<Q; qi++){
    const QE& q = qs2[qi];
    int need = q.r;                 // activate positions 0..r-1
    if(need > sn) need = sn;
    if(need < 0) need = 0;
    int npaint = 0;
    if(wl_mode == 2){
      // downward sweep, stop at the first state already painted this query:
      // the first state painted gets the largest own+1, which is exactly MX(x, need)
      for(int i=need-1;i>=0;i--){
        int a = (int)s_own[i]; u32 val = (u32)(i+1);
        while(a != 1 && !wl_last[a]){ wl_last[a] = val; plist_[npaint++] = (u32)a; a = (int)s_link[a]; }
      }
    } else if(wl_mode){
      for(; act<need; act++){
        int a = (int)s_own[act]; u32 val = (u32)(act+1);
        wl_last[a] = val; wl_work++;
        while(a != 1){ a = (int)s_link[a]; wl_last[a] = val; wl_work++; }
        if(wl_work > wl_budget){ wl_mode = 0; break; }   // blew the budget
      }
      if(!wl_mode){                 // fell back mid-activation: replay into the Euler struct
        build_meta(); build_intervals(); eul_ready = 1;
        for(int i=0;i<act;i++){ int v = (int)s_own[i]; eactivate((int)tin[v], (u32)(i+1)); }
        for(; act<need; act++){ int v = (int)s_own[act]; eactivate((int)tin[v], (u32)(act+1)); }
      }
    } else if(eul_ready){
      for(; act<need; act++){
        int v = (int)s_own[act];
        eactivate((int)tin[v], (u32)(act+1));
      }
    } else if(need > act) act = need;
    const char* T = q.t;
    int tl = q.tl;
    int l0 = q.l - 1;
    int r1 = q.r - 1;
    int maxlen = q.r - q.l + 1;
    if(maxlen < 0) maxlen = 0;
    int v = 1, len = 0, e = -1;   // e = witness end position of the current match
    // ARM FULLRANGE (this seat).  For a FULL-RANGE query (l == 1 && r >= |S|) the interval
    // clip can never shorten the match: mxo[v] >= s_len[v] >= len holds for every state, so
    // the clip's `lim >= len` test fires on its very first iteration and leaves len alone,
    // and maxlen = q.r - q.l + 1 >= |S| >= len makes the `len > maxlen` branch unreachable.
    // The clip therefore degenerates to "record the witness e", and the witness feeds only
    // the fast path -- which is itself a pure shortcut: whenever it fires, sget(v,c) != 0
    // (the match extending at the witness is an occurrence of match+c in S), so the generic
    // walk below exits on its FIRST test with exactly the same (v,len).  Both are dead
    // weight on this shape, and dropping them removes one mxo[] load per character plus the
    // sstart[]/e bookkeeping from the loop that is 61% of tc17's runtime.
    // Measured on this exact shape (|S|=5e5, |T|=1e6, l=1, r=|S|): the fast path fires
    // 38,424 / 1,000,000 characters = 3.8%, and the clip runs 1.000 iterations per
    // slow-path character => ~1.9 random loads/char are being paid for a 3.8% shortcut.
    const int full_range = (l0 == 0 && q.r >= sn);
    // ARM METASKIP: build_ord()/build_meta() produce only ord_/mxo, and mxo is read in exactly
    // one place -- the clip's `if(mxo[v] <= q.r) m = mxo[v];` fast path.  A full-range query
    // never reaches the clip (ARM FULLRANGE), so a test whose queries are all full-range pays
    // for both passes and reads none of it.  Deferred to the first query that actually needs
    // the clip, which leaves the general family's hot path byte-identical to the parent.
    if(!meta_ready && !full_range){ build_ord(); build_meta(); meta_ready = 1; }
    for(int i=0;i<tl;i++){
      int c = T[i]-'a';
      int nx=sget(v,c);
      int vn=(int)s_link[v];
      if(__builtin_expect(full_range,1)){
        int ov = v;
        while(v!=1 && !nx) { v = vn; vn = (int)s_link[v]; nx=sget(v,c); }
        if(v != ov) len = (int)s_len[v];
        if(nx){ v = nx; len++; } else { v = 1; len = 0; }
        f_[i] = len;
        continue;
      }
      // fast path: the match extends in place at the witness (f[i] <= f[i-1]+1, so len+1 is optimal)
      if(len > 0 && e < r1 && sstart[e+1]-'a' == c){
        v = nx; len++; e++;
        f_[i] = len;
        continue;
      }
      // Only the FINAL rung of this walk matters: `len` is rewritten on every step
      // but read only after the loop, and once at least one step ran len == s_len[v].
      // Reading s_len[] inside the loop therefore costs one extra random load per rung
      // into a *separate* 2.4 MB array (one more TLB entry + one more miss) for
      // nothing.  The sget below is the very address the walk just tested => L1 hit.
      {
        int ov = v;
        // ARM LNKLA: software-pipeline the suffix-link chase.  The old form loaded
        // s_link[v] only after the sget test failed, so each rung's link load sat on the
        // critical path behind the previous rung.  Fetching the next link up front makes
        // the two loads of a rung independent, which is exactly the shape the current
        // board leader uses (ref2/rival_107908.cpp, `int vn = (int)s_link[v];` hoisted
        // above the test).  `len` handling is unchanged: read once, at the rung we stop on.
        while(v!=1 && !nx) { v = vn; vn = (int)s_link[v]; nx=sget(v,c); }
        if(v != ov) len = (int)s_len[v];
      }
      if(nx){ v = nx; len++; } else { v = 1; len = 0; }
      e = -1;
      // clip the match to S[l..r]: longest suffix whose endpos hits [l+len-1, r-1]
      while(len>0){
        if(len > maxlen){
          len = maxlen;
          while(v != 1 && len <= (int)s_len[s_link[v]]) v = (int)s_link[v];
          if(len == 0) break;
        }
        u32 m;
        if(mxo[v] <= (u32)q.r) m = mxo[v];
        else {
          if(!eul_ready){
            build_intervals();
            for(int i2=0;i2<act;i2++){ int vv=(int)s_own[i2]; eactivate((int)tin[vv], (u32)(i2+1)); }
            eul_ready = 1;
          }
          u32 _w;
          m=qvalue((int)tin[v],(int)tout[v],(u32)(len+l0));
        }
        // lengths in this state's class that can still satisfy the test
        int lim = (int)m - l0;
        if(lim >= len){ e = (int)m - 1; break; }
        int pl = (int)s_len[s_link[v]];
        if(lim > pl){ len = lim; e = (int)m - 1; break; }
        len = pl;
        if(len == 0) break;
        v = (int)s_link[v];
      }
      f_[i] = len;
    }
    if(wl_mode == 2){ for(int k=0;k<npaint;k++) wl_last[plist_[k]] = 0; }
    // SAM(T) -> g[], accumulate
    t_sz=1; t_last=1;
    t_len[1]=0; t_link[1]=0;
    tzero(1);
    long long ans=0;
    for(int i=0;i<tl;i++){
      int c = T[i]-'a';
      int cur = ++t_sz;
      t_len[cur] = t_len[t_last]+1; t_link[cur]=0;
      tzero(cur);
      int pp = t_last;
      for(; pp && !tget(pp,c); pp = (int)t_link[pp]) tset(pp,c,cur);
      int lk;
      if(!pp) lk = 1;
      else {
        int qq = tget(pp,c);
        if((int)t_len[pp]+1 == (int)t_len[qq]) lk = qq;
        else {
          int cl = ++t_sz;
          if(cl>t_fresh)t_fresh=cl;
          t_len[cl] = t_len[pp]+1; t_link[cl] = t_link[qq];
          memcpy(t_nxt + (size_t)cl*80, t_nxt + (size_t)qq*80, 80);
          for(; pp && tget(pp,c)==qq; pp = (int)t_link[pp]) tset(pp,c,cl);
          t_link[qq] = (u32)cl; lk = cl;
        }
      }
      t_link[cur] = (u32)lk;
      t_last = cur;
      int g = (int)t_len[lk];
      int m = g > f_[i] ? g : f_[i];
      ans += (long long)(i+1) - m;
    }
    answers[q.idx] = ans;
  }
  for(int i=0;i<Q;i++) emit(answers[i]);
}

#pragma GCC pop_options

#ifndef LOCAL
int main(){ return 0; }
extern "C" void __libc_start_main(void*mm,int argc,char**argv){
  ul *p=(ul*)(argv+argc+1);
  while(*p) p++; p++;
  DI *d=0; for(; p[0]; p+=2) if(p[0]==0x6b637564UL){ d=(DI*)p[1]; break; }
  if(d){
    const u8* in=(const u8*)d->IBp; ul insz=d->IBl;
    if(!insz && d->is){ in=(const u8*)d->ip; insz=d->is; }
    run(in,insz,d->op);
    d->os=(ul)(OUTP-d->op);
  }
  __asm__ volatile("syscall"::"a"(60),"D"(0):"rcx","r11","memory");
  for(;;);
}
#endif

评测结果