代码

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

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 2x64-bit lanes, accumulate into acc (2x64-bit lanes)
static inline __m128i popc2(__m128i x, __m128i acc){
  const __m128i m55 = _mm_set1_epi64x(0x5555555555555555ULL);
  const __m128i m33 = _mm_set1_epi64x(0x3333333333333333ULL);
  const __m128i m0f = _mm_set1_epi64x(0x0f0f0f0f0f0f0f0fULL);
  __m128i t = _mm_sub_epi64(x, _mm_and_si128(_mm_srli_epi64(x,1), m55));
  t = _mm_add_epi64(_mm_and_si128(t,m33), _mm_and_si128(_mm_srli_epi64(t,2),m33));
  t = _mm_and_si128(_mm_add_epi64(t, _mm_srli_epi64(t,4)), m0f);
  return _mm_add_epi64(acc, _mm_sad_epu8(t, _mm_setzero_si128()));
}

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<=3){
      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; // inclusive word indices
    int mcount=mid_end-mid_start+1;
    __m128i acc=_mm_setzero_si128();
    int w=mid_start;
    const __m128i *va0=(const __m128i*)(a0+w);
    const __m128i *va1=(const __m128i*)(a1+w);
    const __m128i *va2=(const __m128i*)(a2+w);
    const __m128i *vb0=(const __m128i*)(b0+(size_t)w*8);
    const __m128i *vb1=(const __m128i*)(b1+(size_t)w*8);
    const __m128i *vb2=(const __m128i*)(b2+(size_t)w*8);
    int pairs=mcount>>1;
    for(int p=0;p<pairs;p++){
      __m128i x0=_mm_loadu_si128(va0+p);
      __m128i x1=_mm_loadu_si128(va1+p);
      __m128i x2=_mm_loadu_si128(va2+p);
      __m128i y0=_mm_loadu_si128(vb0+p);
      __m128i y1=_mm_loadu_si128(vb1+p);
      __m128i y2=_mm_loadu_si128(vb2+p);
      __m128i win=_mm_or_si128(_mm_or_si128(_mm_and_si128(x0,y1),_mm_and_si128(x1,y2)),_mm_and_si128(x2,y0));
      acc=popc2(win,acc);
    }
    if(mcount&1){
      int wl=mid_end;
      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 (2x64 lanes)
    {
      u64 lo, hi;
      _mm_storel_epi64((__m128i*)&lo, acc);
      _mm_storel_epi64((__m128i*)&hi, _mm_srli_si128(acc,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;
  }
}

评测结果