代码

// ===== REFERENCES =====
// [1] duck.ac 本账号 saffah_cc_v41_agg1，提交 #109230 <https://duck.ac/submission/109230>
//     （139.425574 ms，本题本账号现役最好件 = `problems/wc2017b2/work/w2z_c2.cpp`）。
//     **本文件正文 = 该件正文的逐字节复制**（含它自带的整条引用区，一字未改），
//     唯一改动见「思路」节（尾环重写，两处）。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 #109149 <https://duck.ac/submission/109149>
//     （139.663745 ms，本题实时 T）：[1] 的基底链上端（#109230 = 该件正文 + 本账号的两把刀）。
//     本发从该件未复制任何代码，仅引用其成绩作为分母 T。
// [3] 许可合规：上述两份公开提交的正文均**未附任何许可证声明**；duck.ac 提交正文按站点规则
//     公开可见、可直接取用。本发按 `/home/yjp/duck.ac/RULES.md` 第 3 节署名引用账号与原提交地址。
//     本发未引入任何第三方代码：改动只是把本文件里**已有的** 4 字尾路循环用等价形式重写。
// ===== 思路 =====
// 【本发 = `#109230` 正文 + **尾环重写**（`[TAILALL]`），数学与操作数逐位不变，只改代码形态】
//
// (0) 口径与动机：mine = 139.425574（#109230）· T = 139.663745（#109149，早于我 ⇒ **严支**）
//     ⇒ 严支线 `0.99*T + 1µs = 138.268108`，缺口 **1.157466 ms（0.83%）**。
//     本席用**同二进制多臂探针**（`tools/probe.py` + `work/w2f_pbmk.py`，判题机、逐位同 chk）量出
//     逐相份额（Q=2e5 maxlen，Σl=2.0e10）：查询主环 ~95% · **分组散写 2.8%** · **整平面旋转 1.3%** ·
//     build_all 0.13%。**并用消融臂（NOTAIL：把 4 字尾路整段删掉）量出尾路 = 3.06%**（本发靶区）。
//
// (1) 尾路的两个问题（成因，均已在本文件里定位到行）：
//   (a) **每 4 字做一次 64 位归约**（`vpsadbw` + `vpaddq`）：8 字的活只值一趟归约 —— 但 c8 的
//       每字节 ≤ 8，两条 c8 的**字节和 ≤ 16 < 255**，因此可以把两个 4 字块先在**字节域**相加、
//       再只用**一条** `vpsadbw` 归约（`h` 全域的同一论证在 `[FLUSHB]` 里已经用过，并被判题机证实为正）。
//   (b) **尾路里的内联汇编**（`csa_diff1` 4 操作数版 + 两条 `vpand`/`vpsrlw` 掩码）：那套
//       `"=&x"` 早冲突约束是**为主环的手写调度**才需要的（主环必须钉住寄存器分配）；尾路是
//       4 字一档的小循环，汇编只**限制**了 gcc 的调度自由 ⇒ 改用纯 intrinsic（gcc 会把取数
//       折进 `vpxor` 内存操作数，指令数不变）。
//   等价性：`(z>>4)&0x0F` 与 `((z & 0x0F) ^ z) >> 4` 逐位相同（本文件 `[NIBMASK]` 已用同一恒等式）。
//
// (2) 完整版尾路（本发）：`for (; b + 8 <= bend; b += 8)` 成对处理（2×4 字，字节域合并 + 单次归约），
//     余数 4 字仍走原单块路径。**每 8 字的指令数由 26 降到 23**（−12%），且尾路完全没有内联汇编。
//
// (3) 闸门（全部通过）：`gcc 9.3 -O2 -std=c++17 -m32` exit=0 ✓ · 两个官形状 checksum 与 #109230
//     **逐位相同**（`rand=3752654484591095461` · `maxlen=3223221539191264348`）✓ ·
//     `-DTESTSCALAR`（独立标量路径）同 chk ✓ · `work/w2z_verify.cpp` **12 种规模/形状 × 3623 例
//     暴力对拍 0 失败**（含 n=300000）✓。
//
// (4) 风险与止损：本发只改尾路、不改主环/分组/旋转；若判题机为负，本账号最好件仍是 #109230
//     （排行榜保留每人最好），口径不变。
// ================
#include <cstdlib>
#include <sys/mman.h>
#include <cstring>
#include <immintrin.h>

#define MAXN 300005
#define MAXW (((MAXN + 63) / 64 + 12 + 3) & ~3)   /* multiple of 4 words = 32B rows */

#define AUXSTRIDE (((MAXW + 2 + 20) + 3) & ~3)
static unsigned long long *E0, *E1, *F0, *F1, *R0, *R1;
static inline void bind_arena(void *base) {
  unsigned long long *b = (unsigned long long *)((char *)base + 16384);
  E0 = b + 0 * AUXSTRIDE; E1 = b + 1 * AUXSTRIDE;
  F0 = b + 2 * AUXSTRIDE; F1 = b + 3 * AUXSTRIDE;
  R0 = b + 4 * AUXSTRIDE; R1 = b + 5 * AUXSTRIDE;
}
#define AUXBYTES (6 * AUXSTRIDE * 8 + 16384)
static unsigned long long FALLBACKAR[6 * AUXSTRIDE + 2048];
static inline void *arena_alloc(int huge) {
  void *p = 0;
  if (posix_memalign(&p, 2u << 20, AUXBYTES) == 0 && p) {
    if (huge) madvise(p, AUXBYTES, MADV_HUGEPAGE);
    return p;
  }
  return (void *)FALLBACKAR;   /* allocation fallback: never dereference NULL */
}
// The 256 pre-rotated copies (4 x 64 x 4694 x 8 B = 9388 KB) are replaced by ONE two-array
// scratch: the query loop is group-outer and uses only one rotation per group, so the rotation
// is generated for that group immediately before its inner loop.  9388 KB -> 75 KB.
static int ORD[MAXN];
static __m256i FMASK[256] __attribute__((aligned(64)));
static __m256i LMASK[256] __attribute__((aligned(64)));
static unsigned long long RQ[MAXN];
static int GHEAD[520], GCUR[520];
static int g_nw;
static unsigned long long WMASK[65];

#define SOLVE_ARGS int n, int q, char *s1, char *s2, int *q_x, int *q_y, int *q_len, unsigned *ans

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

// judge's g++-9 with no -march lowers _mm256_loadu_* into vmovdqu+{vinserti128}/{vextracti128}
// (the AVX-256 split-load tax).  This one asm instruction emits the real 32-byte load.
__attribute__((target("avx2"))) static inline __m256i ldu256(const void *p) {
  __m256i r; __asm__("vmovdqu %1, %0" : "=x"(r) : "m"(*(const __m256i *)p)); return r; }

static const signed char LUTA[32] __attribute__((aligned(32))) =
  {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4, 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4};
static const signed char ONES8[32] __attribute__((aligned(32))) =
  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
static const signed char LOW4A[64] __attribute__((aligned(32))) =
  {15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,
   15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15};
#define VLUT (*((const __m256i *)LUTA))
#define VLOW4 (*((const __m256i *)LOW4A))

static inline unsigned pc_avx2_diff(const unsigned long long *A0, const unsigned long long *A1,
                                    const unsigned long long *B0, const unsigned long long *B1,
                                    int from, int to) {
  unsigned acc = 0;
  __m256i accv = _mm256_setzero_si256();
  int w = from;
  for (; w + 4 <= to; w += 4) {
    __m256i z = _mm256_or_si256(
        _mm256_xor_si256(ldu256(A0 + w),
                         ldu256(B0 + w)),
        _mm256_xor_si256(ldu256(A1 + w),
                         ldu256(B1 + w)));
    __m256i c8 = _mm256_add_epi8(
        _mm256_shuffle_epi8(VLUT, _mm256_and_si256(z, VLOW4)),
        _mm256_shuffle_epi8(VLUT, _mm256_and_si256(_mm256_srli_epi16(z, 4), VLOW4)));
    accv = _mm256_add_epi64(accv, _mm256_sad_epu8(c8, _mm256_setzero_si256()));
  }
  __m128i sum = _mm_add_epi32(_mm256_castsi256_si128(accv), _mm256_extracti128_si256(accv, 1));
  sum = _mm_add_epi32(sum, _mm_srli_si128(sum, 8));
  acc = (unsigned)_mm_cvtsi128_si32(sum);
  for (; w < to; w++)
    acc += (unsigned)__builtin_popcountll((A0[w] ^ B0[w]) | (A1[w] ^ B1[w]));
  return acc;
}
#pragma GCC pop_options

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

__attribute__((target("avx2"),always_inline)) static inline __m256i csa_diff1(
    const unsigned long long *a0, const unsigned long long *b0, int k) {
  __m256i r,t;
  __asm__("vmovdqu %2, %0\n\t"
          "vpxor   %3, %0, %0\n\t"
          "vmovdqu %4, %1\n\t"
          "vpxor   %5, %1, %1\n\t"
          "vpor    %1, %0, %0"
          : "=&x"(r),"=&x"(t)
          : "m"(*(const __m256i *)(a0+k)),"m"(*(const __m256i *)(b0+k)),
            "m"(*(const __m256i *)(a0+AUXSTRIDE+k)),"m"(*(const __m256i *)(b0+AUXSTRIDE+k)));
  return r;
}
__attribute__((target("avx2"),always_inline)) static inline void csa_add3(
    __m256i &hi,__m256i &lo,__m256i a,__m256i b,__m256i c) {
  __m256i u=_mm256_xor_si256(a,b);
  hi=_mm256_or_si256(_mm256_and_si256(a,b),_mm256_and_si256(u,c));
  lo=_mm256_xor_si256(u,c);
}
__attribute__((target("avx2"),always_inline)) static inline __m256i csa_count_bytes(__m256i x) {
  return _mm256_add_epi8(
    _mm256_shuffle_epi8(VLUT,_mm256_and_si256(x,VLOW4)),
    _mm256_shuffle_epi8(VLUT,_mm256_and_si256(_mm256_srli_epi16(x,4),VLOW4)));
}
__attribute__((target("avx2"),always_inline)) static inline __m256i csa_count(__m256i x) {
  return _mm256_sad_epu8(csa_count_bytes(x),_mm256_setzero_si256());
}


static inline unsigned mismatch_interval(const unsigned long long *A, const unsigned long long *B,
                                         int l, int r) {
  if (l >= r) return 0;
  int wa=l>>6, wb=(r-1)>>6;
  if (wa==wb) {
    unsigned long long z=(A[wa]^B[wa]) | (A[wa+AUXSTRIDE]^B[wa+AUXSTRIDE]);
    return (unsigned)__builtin_popcountll(z & (~WMASK[l&63]) & WMASK[((r-1)&63)+1]);
  }
  unsigned long long za=(A[wa]^B[wa]) | (A[wa+AUXSTRIDE]^B[wa+AUXSTRIDE]);
  unsigned long long zb=(A[wb]^B[wb]) | (A[wb+AUXSTRIDE]^B[wb+AUXSTRIDE]);
  unsigned count=(unsigned)__builtin_popcountll(za & (~WMASK[l&63]));
  count+=(unsigned)__builtin_popcountll(zb & WMASK[((r-1)&63)+1]);
  if (wb>wa+1) count+=pc_avx2_diff(A,A+AUXSTRIDE,B,B+AUXSTRIDE,wa+1,wb);
  return count;
}

static void run_avx2(int n, int q, int *q_x, int *q_y, int *q_len, unsigned *ans) {
  (void)n;
  struct Prior { int stamp,lo,hi; unsigned mismatches; };
  static Prior prior[1200];
  for (int j=0;j<1200;j++) prior[j].stamp=0;
  for (int gi = 0; gi < 512; gi++) {
    int g = (gi >> 2) & 63;
    int ph = gi & 3;                                  /* this sub-pass's phase class */
    if (GHEAD[gi] == GHEAD[gi + 1]) continue;
    const unsigned long long *S0, *S1;
    if ((gi >> 2) < 64) { S0 = F0; S1 = F1; } else { S0 = E0; S1 = E1; }
    int corr = 0;                                     /* B pointer correction (words) */
    if (g) {              /* rotation, built AT THIS PHASE: dst[m] = src_rot[m + ph] */
      unsigned long long sh = 64 - g;
      corr = ph;
      {                                                /* vectorised rotation: 4 words per step */
        __m128i vg = _mm_cvtsi32_si128((long long)g), vsh = _mm_cvtsi32_si128((long long)sh);
        int i = ph, lim = g_nw + 2;
        for (; i + 4 <= lim; i += 4) {
          __m256i a0 = ldu256(S0 + i);
          __m256i b0 = ldu256(S0 + i + 1);
          __m256i a1 = ldu256(S1 + i);
          __m256i b1 = ldu256(S1 + i + 1);
          _mm256_store_si256((__m256i *)(R0 + i - ph), _mm256_or_si256(_mm256_srl_epi64(a0, vg), _mm256_sll_epi64(b0, vsh)));
          _mm256_store_si256((__m256i *)(R1 + i - ph), _mm256_or_si256(_mm256_srl_epi64(a1, vg), _mm256_sll_epi64(b1, vsh)));
        }
        for (; i <= g_nw + 1; i++) {
          R0[i - ph] = (S0[i] >> g) | (S0[i + 1] << sh);
          R1[i - ph] = (S1[i] >> g) | (S1[i + 1] << sh);
        }
      }
      S0 = R0; S1 = R1;
    }
    for (int t = GHEAD[gi]; t < GHEAD[gi + 1]; t++) {
      unsigned long long rq = RQ[t];
      int k = ORD[t];
      int x = (int)(rq & 0x1FFFFFu), y = (int)((rq >> 21) & 0x1FFFFFu), l = (int)(rq >> 42);
      int delta = y - x;
      int dpos = delta >= 0;
      int dw = dpos ? (delta >> 6) : ((-delta) >> 6);
      /* branchless: the query start is min(x,y) and the A side is (E0,E1) when
         y>=x else (F0,F1).  The 50/50 branch here mispredicts on half the queries. */
      int s = dpos ? x : y;
      const unsigned long long *AB = dpos ? E0 : F0, *AC = dpos ? E1 : F1;
      const int lbound=s, rbound=s+l, key=dw>>2;
      Prior *old=&prior[key];
      if (old->stamp==gi+1 && lbound<old->hi && old->lo<rbound) {
        int change=__builtin_abs(lbound-old->lo)+__builtin_abs(rbound-old->hi);
        if (change*2 < l*1) {
          const unsigned long long *BP=S0+dw-corr;
          unsigned miss=old->mismatches;
          if (old->lo<lbound) miss-=mismatch_interval(AB,BP,old->lo,lbound);
          else if (lbound<old->lo) miss+=mismatch_interval(AB,BP,lbound,old->lo);
          if (rbound<old->hi) miss-=mismatch_interval(AB,BP,rbound,old->hi);
          else if (old->hi<rbound) miss+=mismatch_interval(AB,BP,old->hi,rbound);
          ans[k]=(unsigned)l-miss;
          old->lo=lbound; old->hi=rbound; old->mismatches=miss;
          continue;
        }
      }
      int w0, wl, d, lo, hi;
      w0 = s >> 6; wl = (s + l - 1) >> 6; d = wl - w0; lo = s & 63; hi = ((s + l - 1) & 63) + 1;
      int wA = w0 & ~3, wZ = wl & ~3;
      int o = w0 - wA, oL = wl - wZ;
      /* [w2y PTRS] A1/B1 were derived from A0/B0 and then immediately subtracted by the
         same `o`, i.e. the second-half A pointer is exactly pA0 + AUXSTRIDE and the
         second-half B pointer is exactly pB0 + AUXSTRIDE.  The
         -m32 target has only ~6 usable GPRs; carrying 8 pointer values (A0,A1,B0,B1,
         the two p-pointers and their two second-half twins) where 2 suffice spills them
         (slot 236 alone is reloaded 5x in
         the query loop).  AUXSTRIDE*8 = 37920 is a compile-time displacement that folds
         into the load's disp32 -- this is exactly the form the hand-scheduled inner
         assembly already uses (`37920(%[pa])`), applied here to the surrounding chunks.
         Removes pointer-arithmetic and spill-reload uops; adds none. */
      const unsigned long long *pA0 = AB + (w0 - o), *pB0 = S0 + (w0 + dw - corr - o);
      int bend = wZ - wA;
      __m256i accv = _mm256_setzero_si256();
      if (bend == 0) {
        __m256i z = _mm256_or_si256(
            _mm256_xor_si256(_mm256_load_si256((const __m256i *)(const void *)pA0), ldu256(pB0)),
            _mm256_xor_si256(_mm256_load_si256((const __m256i *)(const void *)(pA0 + AUXSTRIDE)), ldu256((pB0 + AUXSTRIDE))));
        z = _mm256_and_si256(z, _mm256_and_si256(FMASK[o * 64 + lo], LMASK[oL * 64 + hi - 1]));
        __m256i c8 = _mm256_add_epi8(
            _mm256_shuffle_epi8(VLUT, _mm256_and_si256(z, VLOW4)),
            _mm256_shuffle_epi8(VLUT, _mm256_and_si256(_mm256_srli_epi16(z, 4), VLOW4)));
        accv = _mm256_add_epi64(accv, _mm256_sad_epu8(c8, _mm256_setzero_si256()));
      } else {
        {
          __m256i z = _mm256_or_si256(
              _mm256_xor_si256(_mm256_load_si256((const __m256i *)(const void *)pA0), ldu256(pB0)),
              _mm256_xor_si256(_mm256_load_si256((const __m256i *)(const void *)(pA0 + AUXSTRIDE)), ldu256((pB0 + AUXSTRIDE))));
          z = _mm256_and_si256(z, FMASK[o * 64 + lo]);
          __m256i c8 = _mm256_add_epi8(
              _mm256_shuffle_epi8(VLUT, _mm256_and_si256(z, VLOW4)),
              _mm256_shuffle_epi8(VLUT, _mm256_and_si256(_mm256_srli_epi16(z, 4), VLOW4)));
          accv = _mm256_add_epi64(accv, _mm256_sad_epu8(c8, _mm256_setzero_si256()));
        }
        int b = 4, nblk = (bend >= 4) ? (bend - 4) / 64 : 0;
        __m256i z = _mm256_setzero_si256(), a1 = z, a2 = z, a4 = z, a8 = z, high16 = z;
        __m256i AC1 = _mm256_setzero_si256(), AC2 = AC1, AC3 = AC1;
        {
          __m256i a8m = _mm256_setzero_si256(), h16m = a8m, cspm = a8m;
          if (nblk > 0) {
            const unsigned long long *pa = pA0 + 4, *pb = pB0 + 4;
            int cnt = nblk;
            __asm__ volatile (
"vpxor %%ymm0, %%ymm0, %%ymm0\n\tvpxor %%ymm1, %%ymm1, %%ymm1\n\tvpxor %%ymm2, %%ymm2, %%ymm2\n\tvmovdqa %%ymm2, %[a8]\n\tvmovdqa %%ymm2, %[h16]\n\t.p2align 5\n\t1:\n\tvmovdqu 128(%[pa]), %%ymm3\n\tvpxor   128(%[pb]), %%ymm3, %%ymm3\n\tvmovdqu 37920(%[pa]), %%ymm5\n\tvpxor   37920(%[pb]), %%ymm5, %%ymm5\n\tvpor    %%ymm5, %%ymm3, %%ymm3\n\tvmovdqu 192(%[pa]), %%ymm4\n\tvpxor   192(%[pb]), %%ymm4, %%ymm4\n\tvmovdqu 37984(%[pa]), %%ymm5\n\tvpxor   37984(%[pb]), %%ymm5, %%ymm5\n\tvpor    %%ymm5, %%ymm4, %%ymm4\n\tvpxor %%ymm3, %%ymm0, %%ymm5\n\tvpand %%ymm3, %%ymm0, %%ymm3\n\tvpxor %%ymm4, %%ymm5, %%ymm0\n\tvpand %%ymm4, %%ymm5, %%ymm5\n\tvpor  %%ymm5, %%ymm3, %%ymm3\n\tvmovdqu 256(%[pa]), %%ymm6\n\tvpxor   256(%[pb]), %%ymm6, %%ymm6\n\tvmovdqu 38048(%[pa]), %%ymm4\n\tvpxor   38048(%[pb]), %%ymm4, %%ymm4\n\tvpor    %%ymm4, %%ymm6, %%ymm6\n\tvmovdqu 320(%[pa]), %%ymm7\n\tvpxor   320(%[pb]), %%ymm7, %%ymm7\n\tvmovdqu 38112(%[pa]), %%ymm4\n\tvpxor   38112(%[pb]), %%ymm4, %%ymm4\n\tvpor    %%ymm4, %%ymm7, %%ymm7\n\tvpxor %%ymm6, %%ymm0, %%ymm4\n\tvpand %%ymm6, %%ymm0, %%ymm6\n\tvpxor %%ymm7, %%ymm4, %%ymm0\n\tvpand %%ymm7, %%ymm4, %%ymm4\n\tvpor  %%ymm4, %%ymm6, %%ymm6\n\tvpxor %%ymm3, %%ymm1, %%ymm5\n\tvpand %%ymm3, %%ymm1, %%ymm3\n\tvpxor %%ymm6, %%ymm5, %%ymm1\n\tvpand %%ymm6, %%ymm5, %%ymm5\n\tvpor  %%ymm5, %%ymm3, %%ymm3\n\tvmovdqu 384(%[pa]), %%ymm7\n\tvpxor   384(%[pb]), %%ymm7, %%ymm7\n\tvmovdqu 38176(%[pa]), %%ymm6\n\tvpxor   38176(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm7, %%ymm7\n\tvmovdqu 448(%[pa]), %%ymm4\n\tvpxor   448(%[pb]), %%ymm4, %%ymm4\n\tvmovdqu 38240(%[pa]), %%ymm6\n\tvpxor   38240(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm4, %%ymm4\n\tvpxor %%ymm7, %%ymm0, %%ymm6\n\tvpand %%ymm7, %%ymm0, %%ymm7\n\tvpxor %%ymm4, %%ymm6, %%ymm0\n\tvpand %%ymm4, %%ymm6, %%ymm6\n\tvpor  %%ymm6, %%ymm7, %%ymm7\n\tvmovdqu 0(%[pa]), %%ymm5\n\tvpxor   0(%[pb]), %%ymm5, %%ymm5\n\tvmovdqu 37792(%[pa]), %%ymm6\n\tvpxor   37792(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm5, %%ymm5\n\tvmovdqu 64(%[pa]), %%ymm4\n\tvpxor   64(%[pb]), %%ymm4, %%ymm4\n\tvmovdqu 37856(%[pa]), %%ymm6\n\tvpxor   37856(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm4, %%ymm4\n\tvpxor %%ymm5, %%ymm0, %%ymm6\n\tvpand %%ymm5, %%ymm0, %%ymm5\n\tvpxor %%ymm4, %%ymm6, %%ymm0\n\tvpand %%ymm4, %%ymm6, %%ymm6\n\tvpor  %%ymm6, %%ymm5, %%ymm5\n\tvpxor %%ymm7, %%ymm1, %%ymm4\n\tvpand %%ymm7, %%ymm1, %%ymm7\n\tvpxor %%ymm5, %%ymm4, %%ymm1\n\tvpand %%ymm5, %%ymm4, %%ymm4\n\tvpor  %%ymm4, %%ymm7, %%ymm7\n\tvpxor %%ymm3, %%ymm2, %%ymm6\n\tvpand %%ymm3, %%ymm2, %%ymm3\n\tvpxor %%ymm7, %%ymm6, %%ymm2\n\tvpand %%ymm7, %%ymm6, %%ymm6\n\tvpor  %%ymm6, %%ymm3, %%ymm3\n\tvmovdqa %%ymm3, %[csp]\n\tvmovdqu 160(%[pa]), %%ymm5\n\tvpxor   160(%[pb]), %%ymm5, %%ymm5\n\tvmovdqu 37952(%[pa]), %%ymm7\n\tvpxor   37952(%[pb]), %%ymm7, %%ymm7\n\tvpor    %%ymm7, %%ymm5, %%ymm5\n\tvmovdqu 224(%[pa]), %%ymm4\n\tvpxor   224(%[pb]), %%ymm4, %%ymm4\n\tvmovdqu 38016(%[pa]), %%ymm7\n\tvpxor   38016(%[pb]), %%ymm7, %%ymm7\n\tvpor    %%ymm7, %%ymm4, %%ymm4\n\tvpxor %%ymm5, %%ymm0, %%ymm7\n\tvpand %%ymm5, %%ymm0, %%ymm5\n\tvpxor %%ymm4, %%ymm7, %%ymm0\n\tvpand %%ymm4, %%ymm7, %%ymm7\n\tvpor  %%ymm7, %%ymm5, %%ymm5\n\tvmovdqu 288(%[pa]), %%ymm6\n\tvpxor   288(%[pb]), %%ymm6, %%ymm6\n\tvmovdqu 38080(%[pa]), %%ymm4\n\tvpxor   38080(%[pb]), %%ymm4, %%ymm4\n\tvpor    %%ymm4, %%ymm6, %%ymm6\n\tvmovdqu 352(%[pa]), %%ymm3\n\tvpxor   352(%[pb]), %%ymm3, %%ymm3\n\tvmovdqu 38144(%[pa]), %%ymm4\n\tvpxor   38144(%[pb]), %%ymm4, %%ymm4\n\tvpor    %%ymm4, %%ymm3, %%ymm3\n\tvpxor %%ymm6, %%ymm0, %%ymm4\n\tvpand %%ymm6, %%ymm0, %%ymm6\n\tvpxor %%ymm3, %%ymm4, %%ymm0\n\tvpand %%ymm3, %%ymm4, %%ymm4\n\tvpor  %%ymm4, %%ymm6, %%ymm6\n\tvpxor %%ymm5, %%ymm1, %%ymm7\n\tvpand %%ymm5, %%ymm1, %%ymm5\n\tvpxor %%ymm6, %%ymm7, %%ymm1\n\tvpand %%ymm6, %%ymm7, %%ymm7\n\tvpor  %%ymm7, %%ymm5, %%ymm5\n\tvmovdqu 416(%[pa]), %%ymm3\n\tvpxor   416(%[pb]), %%ymm3, %%ymm3\n\tvmovdqu 38208(%[pa]), %%ymm6\n\tvpxor   38208(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm3, %%ymm3\n\tvmovdqu 480(%[pa]), %%ymm4\n\tvpxor   480(%[pb]), %%ymm4, %%ymm4\n\tvmovdqu 38272(%[pa]), %%ymm6\n\tvpxor   38272(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm4, %%ymm4\n\tvpxor %%ymm3, %%ymm0, %%ymm6\n\tvpand %%ymm3, %%ymm0, %%ymm3\n\tvpxor %%ymm4, %%ymm6, %%ymm0\n\tvpand %%ymm4, %%ymm6, %%ymm6\n\tvpor  %%ymm6, %%ymm3, %%ymm3\n\tvmovdqu 32(%[pa]), %%ymm7\n\tvpxor   32(%[pb]), %%ymm7, %%ymm7\n\tvmovdqu 37824(%[pa]), %%ymm6\n\tvpxor   37824(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm7, %%ymm7\n\tvmovdqu 96(%[pa]), %%ymm4\n\tvpxor   96(%[pb]), %%ymm4, %%ymm4\n\tvmovdqu 37888(%[pa]), %%ymm6\n\tvpxor   37888(%[pb]), %%ymm6, %%ymm6\n\tvpor    %%ymm6, %%ymm4, %%ymm4\n\tvpxor %%ymm7, %%ymm0, %%ymm6\n\tvpand %%ymm7, %%ymm0, %%ymm7\n\tvpxor %%ymm4, %%ymm6, %%ymm0\n\tvpand %%ymm4, %%ymm6, %%ymm6\n\tvpor  %%ymm6, %%ymm7, %%ymm7\n\tvpxor %%ymm3, %%ymm1, %%ymm4\n\tvpand %%ymm3, %%ymm1, %%ymm3\n\tvpxor %%ymm7, %%ymm4, %%ymm1\n\tvpand %%ymm7, %%ymm4, %%ymm4\n\tvpor  %%ymm4, %%ymm3, %%ymm3\n\tvpxor %%ymm5, %%ymm2, %%ymm6\n\tvpand %%ymm5, %%ymm2, %%ymm5\n\tvpxor %%ymm3, %%ymm6, %%ymm2\n\tvpand %%ymm3, %%ymm6, %%ymm6\n\tvpor  %%ymm6, %%ymm5, %%ymm5\n\tvmovdqa %[csp], %%ymm7\n\tvmovdqa %[a8], %%ymm6\n\tvpxor %%ymm6, %%ymm7, %%ymm4\n\tvpand %%ymm6, %%ymm7, %%ymm7\n\tvpxor %%ymm5, %%ymm4, %%ymm3\n\tvpand %%ymm5, %%ymm4, %%ymm4\n\tvpor  %%ymm4, %%ymm7, %%ymm7\n\tvmovdqa %%ymm3, %[a8]\n\tvmovdqa %[lut], %%ymm6\n\tvpand  %[low4a], %%ymm7, %%ymm4\n\tvpxor  %%ymm4, %%ymm7, %%ymm5\n\tvpsrlw $4, %%ymm5, %%ymm5\n\tvpshufb %%ymm5, %%ymm6, %%ymm5\n\tvpshufb %%ymm4, %%ymm6, %%ymm4\n\tvpaddb %%ymm4, %%ymm5, %%ymm5\n\tvpmaddubsw %[ones], %%ymm5, %%ymm5\n\tvpaddw %[h16], %%ymm5, %%ymm5\n\tvmovdqa %%ymm5, %[h16]\n\tadd $512, %[pa]\n\tadd $512, %[pb]\n\tsub $1, %[cnt]\n\tjnz 1b\n\tvmovdqa %%ymm0, %[o1]\n\tvmovdqa %%ymm1, %[o2]\n\tvmovdqa %%ymm2, %[o3]"
              : [o1]"=m"(AC1), [o2]"=m"(AC2), [o3]"=m"(AC3),
                [a8]"+m"(a8m), [h16]"+m"(h16m), [csp]"+m"(cspm),
                [pa]"+r"(pa), [pb]"+r"(pb), [cnt]"+r"(cnt)
              : [lut]"m"(*(const __m256i *)LUTA),
                [low4a]"m"(*(const __m256i *)LOW4A),
                [low4b]"m"(*(const __m256i *)(LOW4A + 32)),
                [ones]"m"(*(const __m256i *)ONES8)
              : "ymm0","ymm1","ymm2","ymm3","ymm4","ymm5","ymm6","ymm7","cc","memory");
          }
          a1 = AC1; a2 = AC2; a4 = AC3; a8 = a8m; high16 = h16m;
        }
        b = 4 + 64 * nblk;        if (b > 4) {
          __m256i hs=_mm256_madd_epi16(high16,_mm256_set1_epi16(1));
          __m256i h64=_mm256_add_epi64(_mm256_and_si256(hs,_mm256_set1_epi64x(0xffffffffULL)),
                                      _mm256_srli_epi64(hs,32));
          accv=_mm256_add_epi64(accv,_mm256_slli_epi64(h64,4));
          /* [w2y FLUSHB] the four carry planes carry weights 1/2/4/8.  Instead of four
             separate csa_count (= four shuffle-pairs and FOUR vpsadbw, each needing its own
             u64 accumulator live) combine them in the BYTE domain first and reduce once.
             Exact: csa_count_bytes(ai) <= 8 per byte, so 1*c1 + 2*c2 + 4*c4 + 8*c8 <=
             8 + 16 + 32 + 64 = 120 < 255 -- no byte lane can overflow, and every doubling
             is a plain vpaddb (no cross-byte carry).  Arithmetic identical to
             count(a1) + 2*count(a2) + 4*count(a4) + 8*count(a8). */
          {
            __m256i c1=csa_count_bytes(a1), c2=csa_count_bytes(a2),
                    c4=csa_count_bytes(a4), c8=csa_count_bytes(a8);
            __m256i w2=_mm256_add_epi8(c2,c2);
            __m256i w4=_mm256_add_epi8(c4,c4); w4=_mm256_add_epi8(w4,w4);
            __m256i w8=_mm256_add_epi8(c8,c8); w8=_mm256_add_epi8(w8,w8); w8=_mm256_add_epi8(w8,w8);
            __m256i ws=_mm256_add_epi8(_mm256_add_epi8(c1,w2),_mm256_add_epi8(w4,w8));
            accv=_mm256_add_epi64(accv,_mm256_sad_epu8(ws,_mm256_setzero_si256()));
          }
        }
        {
          for (; b + 8 <= bend; b += 8) {
            __m256i z1 = _mm256_or_si256(
                _mm256_xor_si256(ldu256(pA0 + b), ldu256(pB0 + b)),
                _mm256_xor_si256(ldu256(pA0 + AUXSTRIDE + b), ldu256(pB0 + AUXSTRIDE + b)));
            __m256i l1 = _mm256_and_si256(z1, VLOW4);
            __m256i h1 = _mm256_srli_epi16(_mm256_xor_si256(z1, l1), 4);
            __m256i c1 = _mm256_add_epi8(_mm256_shuffle_epi8(VLUT, l1),
                                         _mm256_shuffle_epi8(VLUT, h1));
            __m256i z2 = _mm256_or_si256(
                _mm256_xor_si256(ldu256(pA0 + b + 4), ldu256(pB0 + b + 4)),
                _mm256_xor_si256(ldu256(pA0 + AUXSTRIDE + b + 4), ldu256(pB0 + AUXSTRIDE + b + 4)));
            __m256i l2 = _mm256_and_si256(z2, VLOW4);
            __m256i h2 = _mm256_srli_epi16(_mm256_xor_si256(z2, l2), 4);
            __m256i c2 = _mm256_add_epi8(_mm256_shuffle_epi8(VLUT, l2),
                                         _mm256_shuffle_epi8(VLUT, h2));
            __m256i cs = _mm256_add_epi8(c1, c2);
            accv = _mm256_add_epi64(accv, _mm256_sad_epu8(cs, _mm256_setzero_si256()));
          }
          for (; b < bend; b += 4) {
            __m256i z1 = _mm256_or_si256(
                _mm256_xor_si256(ldu256(pA0 + b), ldu256(pB0 + b)),
                _mm256_xor_si256(ldu256(pA0 + AUXSTRIDE + b), ldu256(pB0 + AUXSTRIDE + b)));
            __m256i l1 = _mm256_and_si256(z1, VLOW4);
            __m256i h1 = _mm256_srli_epi16(_mm256_xor_si256(z1, l1), 4);
            __m256i c1 = _mm256_add_epi8(_mm256_shuffle_epi8(VLUT, l1),
                                         _mm256_shuffle_epi8(VLUT, h1));
            accv = _mm256_add_epi64(accv, _mm256_sad_epu8(c1, _mm256_setzero_si256()));
          }
        }
        {
          __m256i z = _mm256_or_si256(
              _mm256_xor_si256(_mm256_load_si256((const __m256i *)(const void *)(pA0 + bend)), ldu256(pB0 + bend)),
              _mm256_xor_si256(_mm256_load_si256((const __m256i *)(const void *)((pA0 + AUXSTRIDE) + bend)), ldu256((pB0 + AUXSTRIDE) + bend)));
          z = _mm256_and_si256(z, LMASK[oL * 64 + hi - 1]);
          __m256i c8 = _mm256_add_epi8(
              _mm256_shuffle_epi8(VLUT, _mm256_and_si256(z, VLOW4)),
              _mm256_shuffle_epi8(VLUT, _mm256_and_si256(_mm256_srli_epi16(z, 4), VLOW4)));
          accv = _mm256_add_epi64(accv, _mm256_sad_epu8(c8, _mm256_setzero_si256()));
        }
      }
      {
        __m128i sum = _mm_add_epi32(_mm256_castsi256_si128(accv), _mm256_extracti128_si256(accv, 1));
        sum = _mm_add_epi32(sum, _mm_srli_si128(sum, 8));
        ans[k] = (unsigned)l - (unsigned)_mm_cvtsi128_si32(sum);
      }
      old->stamp=gi+1; old->lo=lbound; old->hi=rbound;
      old->mismatches=(unsigned)l-ans[k];
    }
  }
}

#pragma GCC pop_options

static void run_scalar(int n, int q, int *q_x, int *q_y, int *q_len, unsigned *ans) {
  (void)n;
  for (int gi = 0; gi < 512; gi++) {
    int g = (gi >> 2) & 63;
    int ph = gi & 3;
    if (GHEAD[gi] == GHEAD[gi + 1]) continue;
    const unsigned long long *S0, *S1;
    if ((gi >> 2) < 64) { S0 = F0; S1 = F1; } else { S0 = E0; S1 = E1; }
    int corr = 0;
    if (g) {                                          /* build THIS sub-pass's rotation in place */
      unsigned long long sh = 64 - g;
      corr = ph;
      for (int i = ph; i <= g_nw + 1; i++) {
        R0[i - ph] = (S0[i] >> g) | (S0[i + 1] << sh);
        R1[i - ph] = (S1[i] >> g) | (S1[i + 1] << sh);
      }
      S0 = R0; S1 = R1;
    }
    for (int t = GHEAD[gi]; t < GHEAD[gi + 1]; t++) {
      unsigned long long rq = RQ[t];
      int k = ORD[t];
      int x = (int)(rq & 0x1FFFFFu), y = (int)((rq >> 21) & 0x1FFFFFu), l = (int)(rq >> 42);
      int delta = y - x;
      int dpos = delta >= 0;
      int dw = dpos ? (delta >> 6) : ((-delta) >> 6);
      /* branchless: the query start is min(x,y) and the A side is (E0,E1) when
         y>=x else (F0,F1).  The 50/50 branch here mispredicts on half the queries. */
      int s = dpos ? x : y;
      const unsigned long long *AB = dpos ? E0 : F0, *AC = dpos ? E1 : F1;
      int w0, wl, d, lo, hi;
      const unsigned long long *A0, *A1, *B0, *B1;
      w0 = s >> 6; wl = (s + l - 1) >> 6; d = wl - w0; lo = s & 63; hi = ((s + l - 1) & 63) + 1;
      A0 = AB + w0; A1 = A0 + AUXSTRIDE; B0 = S0 + w0 + dw - corr; B1 = B0 + AUXSTRIDE;
      unsigned dd = 0;
      for (int w = 0; w <= d; w++) {
        unsigned long long m = (A0[w] ^ B0[w]) | (A1[w] ^ B1[w]);
        if (w == 0) m &= ~WMASK[lo];
        if (w == d) m &= WMASK[hi];
        dd += (unsigned)__builtin_popcountll(m);
      }
      ans[k] = (unsigned)l - dd;
    }
  }
}

__attribute__((target("avx2,popcnt"))) static void build_all(int n, const char *s1, const char *s2) {
  int nw = (n + 63) >> 6;
  for (int i = 0; i <= nw + 1; i++) { E0[i] = E1[i] = F0[i] = F1[i] = 0; }
  {
    /* Vectorised plane build.  E0 = (a != '0'), E1 = (a == '2'),
       F0 = (c != '1'), F1 = (c == '0')   -- algebraically identical to the
       branchy version, but with no data-dependent branches at all
       (the scalar form mispredicts ~4x per 3 characters on random input). */
    const __m256i Z0 = _mm256_set1_epi8('0'), Z1 = _mm256_set1_epi8('1'), Z2 = _mm256_set1_epi8('2');
    int i = 0;
    for (; i + 32 <= n; i += 32) {
      int w = i >> 6, b = i & 63;
      __m256i v1 = _mm256_loadu_si256((const __m256i *)(s1 + i));
      __m256i v2 = _mm256_loadu_si256((const __m256i *)(s2 + i));
      unsigned e0 = ~(unsigned)_mm256_movemask_epi8(_mm256_cmpeq_epi8(v1, Z0));
      unsigned e1 = (unsigned)_mm256_movemask_epi8(_mm256_cmpeq_epi8(v1, Z2));
      unsigned f0 = ~(unsigned)_mm256_movemask_epi8(_mm256_cmpeq_epi8(v2, Z1));
      unsigned f1 = (unsigned)_mm256_movemask_epi8(_mm256_cmpeq_epi8(v2, Z0));
      if (b == 0) { E0[w] = e0; E1[w] = e1; F0[w] = f0; F1[w] = f1; }
      else { E0[w] |= (unsigned long long)e0 << 32; E1[w] |= (unsigned long long)e1 << 32;
             F0[w] |= (unsigned long long)f0 << 32; F1[w] |= (unsigned long long)f1 << 32; }
    }
    for (; i < n; i++) {
      int w = i >> 6, b = i & 63;
      int a = s1[i] - '0', c = s2[i] - '0';
      if (a >= 1) E0[w] |= 1ull << b;
      if (a >= 2) E1[w] |= 1ull << b;
      int g = (c + 2) % 3;
      if (g != 0) F0[w] |= 1ull << b;
      if (g >= 2) F1[w] |= 1ull << b;
    }
  }
  g_nw = nw;
  for (int i = 0; i < 64; i++) WMASK[i] = (1ull << i) - 1ull;
  WMASK[64] = ~0ull;
  for (int o = 0; o < 4; o++)
    for (int lo = 0; lo < 64; lo++) {
      unsigned long long *p = (unsigned long long *)&FMASK[o * 64 + lo];
      for (int j = 0; j < 4; j++) p[j] = (j < o) ? 0ull : (j == o ? ~WMASK[lo] : ~0ull);
    }
  for (int o = 0; o < 4; o++)
    for (int hh = 1; hh <= 64; hh++) {
      unsigned long long *p = (unsigned long long *)&LMASK[o * 64 + hh - 1];
      for (int j = 0; j < 4; j++) p[j] = (j < o) ? ~0ull : (j == o ? WMASK[hh] : 0ull);
    }
}

static inline int have_avx2(void) {
  unsigned a, b, c, d;
  __asm__ volatile("cpuid" : "=a"(a), "=b"(b), "=c"(c), "=d"(d) : "a"(1), "c"(0));
  int osxsave = (int)((c >> 27) & 1u), avx = (int)((c >> 28) & 1u);
  if (!(osxsave && avx)) return 0;
  unsigned lo, hi;
  __asm__ volatile("xgetbv" : "=a"(lo), "=d"(hi) : "c"(0));
  if ((lo & 6u) != 6u) return 0;
  __asm__ volatile("cpuid" : "=a"(a), "=b"(b), "=c"(c), "=d"(d) : "a"(7), "c"(0));
  return (int)((b >> 5) & 1u);
}

void solve(SOLVE_ARGS) {
  static void *ar = 0;
  if (!ar) { ar = arena_alloc(0); bind_arena(ar); }
  build_all(n, s1, s2);
  // group queries by the relative bit offset (sign aware), counting sort
  for (int i = 0; i <= 512; i++) GHEAD[i] = 0;
  for (int k = 0; k < q; k++) {
    int d = q_y[k] - q_x[k];
    int ad = (d >= 0 ? d : -d);
    int g = ((d >= 0) ? 0 : 64) + (ad & 63);
    GHEAD[g * 4 + ((ad >> 6) & 3) + 1]++;
  }
  for (int i = 0; i < 512; i++) GHEAD[i + 1] += GHEAD[i];
  for (int i = 0; i < 512; i++) GCUR[i] = GHEAD[i];
  for (int k = 0; k < q; k++) {
    int x = q_x[k], y = q_y[k], l = q_len[k];
    int d = y - x;
    int ad = (d >= 0 ? d : -d);
    int g = ((d >= 0) ? 0 : 64) + (ad & 63);
    int p = GCUR[g * 4 + ((ad >> 6) & 3)]++;
    ORD[p] = k;
    RQ[p] = (unsigned long long)(unsigned)x | ((unsigned long long)(unsigned)y << 21)
          | ((unsigned long long)(unsigned)l << 42);
  }

#ifdef TESTSCALAR
  run_scalar(n, q, q_x, q_y, q_len, ans);
#else
  if (have_avx2()) run_avx2(n, q, q_x, q_y, q_len, ans);
  else run_scalar(n, q, q_x, q_y, q_len, ans);
#endif
}

评测结果