代码

// wc2017b2 AVX2 bitset (32-bit safe, uint64_t, precomputed 8 bit-shifts + unaligned load).
#include <stdint.h>
#include <string.h>
#include <immintrin.h>
#pragma GCC target("avx2")

typedef uint64_t u64;

#define NW_MAX 4690
#define PAD_MAX (NW_MAX+32)
#define TOTAL_MAX (3*NW_MAX+64)

static u64 A[3][TOTAL_MAX] __attribute__((aligned(32)));
static u64 P[3][8][TOTAL_MAX] __attribute__((aligned(32)));

static inline unsigned popc32(unsigned x){ unsigned r; __asm__ __volatile__("popcnt %1,%0":"=r"(r):"r"(x)); return r; }
static inline unsigned popc(u64 x){ return popc32((unsigned)x)+popc32((unsigned)(x>>32)); }
static inline u64 loadu64(const void* p){ u64 v; __builtin_memcpy(&v,p,8); return v; }

// popcount of 4x64-bit lanes, accumulate into acc (4x64-bit lanes)
static inline __m256i popc4(__m256i x, __m256i acc){
  const __m256i m55 = _mm256_set1_epi64x(0x5555555555555555ULL);
  const __m256i m33 = _mm256_set1_epi64x(0x3333333333333333ULL);
  const __m256i m0f = _mm256_set1_epi64x(0x0f0f0f0f0f0f0f0fULL);
  __m256i t = _mm256_sub_epi64(x, _mm256_and_si256(_mm256_srli_epi64(x,1), m55));
  t = _mm256_add_epi64(_mm256_and_si256(t,m33), _mm256_and_si256(_mm256_srli_epi64(t,2),m33));
  t = _mm256_and_si256(_mm256_add_epi64(t, _mm256_srli_epi64(t,4)), m0f);
  return _mm256_add_epi64(acc, _mm256_sad_epu8(t, _mm256_setzero_si256()));
}

static int NW, PAD, TOTAL;

void solve(int n,int q,char*s1,char*s2,int*q_x,int*q_y,int*q_len,unsigned*ans){
  NW = (n+63)>>6;
  PAD = NW+32;
  TOTAL = 3*NW+64;
  for(int c=0;c<3;c++){
    for(int j=0;j<TOTAL;j++){ A[c][j]=0; for(int r=0;r<8;r++) P[c][r][j]=0; }
  }
  for(int i=0;i<n;i++){
    int a=(unsigned char)s1[i]; if(a>2)a-='0';
    int b=(unsigned char)s2[i]; if(b>2)b-='0';
    int w=i>>6; u64 bit=1ULL<<(i&63);
    if(a==0)A[0][PAD+w]|=bit; else if(a==1)A[1][PAD+w]|=bit; else if(a==2)A[2][PAD+w]|=bit;
    if(b==0)P[0][0][PAD+w]|=bit; else if(b==1)P[1][0][PAD+w]|=bit; else if(b==2)P[2][0][PAD+w]|=bit;
  }
  for(int c=0;c<3;c++){
    for(int r=1;r<8;r++){
      u64 *src=P[c][0];
      u64 *dst=P[c][r];
      int sh=64-r;
      for(int j=-NW; j<=2*NW+1; j++){
        dst[PAD+j] = (src[PAD+j+1] << sh) | (src[PAD+j] >> r);
      }
    }
  }

  for(int qi=0;qi<q;qi++){
    int x=q_x[qi], y=q_y[qi], l=q_len[qi];
    long long d=(long long)y-x;
    int off=(int)(d&63), woff=(int)(d>>6);
    int r=off&7, qb=off>>3;
    int w_start=x>>6, boff=x&63;
    int w_end=(x+l-1)>>6, beoff=(x+l-1)&63;
    int nw=w_end-w_start+1;
    const char *b0=(const char*)&P[0][r][0] + (size_t)(PAD+w_start+woff)*8 + qb;
    const char *b1=(const char*)&P[1][r][0] + (size_t)(PAD+w_start+woff)*8 + qb;
    const char *b2=(const char*)&P[2][r][0] + (size_t)(PAD+w_start+woff)*8 + qb;
    u64 *a0=A[0]+PAD+w_start, *a1=A[1]+PAD+w_start, *a2=A[2]+PAD+w_start;

    unsigned cnt=0;
    if(nw<=6){
      for(int w=0;w<nw;w++){
        u64 s0=loadu64(b0+(size_t)w*8), s1=loadu64(b1+(size_t)w*8), s2=loadu64(b2+(size_t)w*8);
        u64 win=(a0[w]&s1)|(a1[w]&s2)|(a2[w]&s0);
        if(w==0 && boff) win &= (~0ULL)<<boff;
        if(w==nw-1 && beoff!=63) win &= (1ULL<<(beoff+1))-1;
        cnt+=popc(win);
      }
      ans[qi]=cnt;
      continue;
    }
    // word 0 (mask low)
    {
      u64 s0=loadu64(b0), s1=loadu64(b1), s2=loadu64(b2);
      u64 win=(a0[0]&s1)|(a1[0]&s2)|(a2[0]&s0);
      if(boff) win &= (~0ULL)<<boff;
      cnt=popc(win);
    }
    // middle SIMD: words 1 .. nw-2
    int mid_start=1, mid_end=nw-2;
    int mcount=mid_end-mid_start+1;
    __m256i acc=_mm256_setzero_si256();
    int w=mid_start;
    const __m256i *va0=(const __m256i*)(a0+w);
    const __m256i *va1=(const __m256i*)(a1+w);
    const __m256i *va2=(const __m256i*)(a2+w);
    const __m256i *vb0=(const __m256i*)(b0+(size_t)w*8);
    const __m256i *vb1=(const __m256i*)(b1+(size_t)w*8);
    const __m256i *vb2=(const __m256i*)(b2+(size_t)w*8);
    int quads=mcount>>2;
    for(int p=0;p<quads;p++){
      __m256i x0=_mm256_loadu_si256(va0+p);
      __m256i x1=_mm256_loadu_si256(va1+p);
      __m256i x2=_mm256_loadu_si256(va2+p);
      __m256i y0=_mm256_loadu_si256(vb0+p);
      __m256i y1=_mm256_loadu_si256(vb1+p);
      __m256i y2=_mm256_loadu_si256(vb2+p);
      __m256i win=_mm256_or_si256(_mm256_or_si256(_mm256_and_si256(x0,y1),_mm256_and_si256(x1,y2)),_mm256_and_si256(x2,y0));
      acc=popc4(win,acc);
    }
    int done=quads*4;
    for(int wl=mid_start+done; wl<=mid_end; wl++){
      u64 s0=loadu64(b0+(size_t)wl*8), s1=loadu64(b1+(size_t)wl*8), s2=loadu64(b2+(size_t)wl*8);
      u64 win=(a0[wl]&s1)|(a1[wl]&s2)|(a2[wl]&s0);
      cnt+=popc(win);
    }
    // extract acc (4x64 lanes)
    {
      __m128i lo128=_mm256_castsi256_si128(acc);
      __m128i hi128=_mm256_extracti128_si256(acc,1);
      u64 lo, hi;
      _mm_storel_epi64((__m128i*)&lo, lo128);
      _mm_storel_epi64((__m128i*)&hi, _mm_srli_si128(lo128,8));
      cnt += (unsigned)(lo+hi);
      _mm_storel_epi64((__m128i*)&lo, hi128);
      _mm_storel_epi64((__m128i*)&hi, _mm_srli_si128(hi128,8));
      cnt += (unsigned)(lo+hi);
    }
    // last word
    {
      int wl=nw-1;
      u64 s0=loadu64(b0+(size_t)wl*8), s1=loadu64(b1+(size_t)wl*8), s2=loadu64(b2+(size_t)wl*8);
      u64 win=(a0[wl]&s1)|(a1[wl]&s2)|(a2[wl]&s0);
      if(beoff!=63) win &= (1ULL<<(beoff+1))-1;
      cnt+=popc(win);
    }
    ans[qi]=cnt;
  }
}

评测结果