代码

// wc2017b2 AVX2 bitset v2: nibble-lookup popcount + 2x unroll.
#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; }

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);
      }
    }
  }

  const __m256i m0f = _mm256_set1_epi8(0x0f);
  const __m256i tab = _mm256_broadcastsi128_si256(_mm_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4));
  const __m256i zero = _mm256_setzero_si256();

  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;
    }
    {
      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);
    }
    int mid_start=1, mid_end=nw-2;
    int mcount=mid_end-mid_start+1;
    __m256i acc0=_mm256_setzero_si256();
    __m256i acc1=_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;
    int p=0;
    for(; p+1<quads; p+=2){
      __m256i x0a=_mm256_loadu_si256(va0+p);
      __m256i x1a=_mm256_loadu_si256(va1+p);
      __m256i x2a=_mm256_loadu_si256(va2+p);
      __m256i y0a=_mm256_loadu_si256(vb0+p);
      __m256i y1a=_mm256_loadu_si256(vb1+p);
      __m256i y2a=_mm256_loadu_si256(vb2+p);
      __m256i wa=_mm256_or_si256(_mm256_or_si256(_mm256_and_si256(x0a,y1a),_mm256_and_si256(x1a,y2a)),_mm256_and_si256(x2a,y0a));

      __m256i x0b=_mm256_loadu_si256(va0+p+1);
      __m256i x1b=_mm256_loadu_si256(va1+p+1);
      __m256i x2b=_mm256_loadu_si256(va2+p+1);
      __m256i y0b=_mm256_loadu_si256(vb0+p+1);
      __m256i y1b=_mm256_loadu_si256(vb1+p+1);
      __m256i y2b=_mm256_loadu_si256(vb2+p+1);
      __m256i wb=_mm256_or_si256(_mm256_or_si256(_mm256_and_si256(x0b,y1b),_mm256_and_si256(x1b,y2b)),_mm256_and_si256(x2b,y0b));

      __m256i la=_mm256_and_si256(wa,m0f);
      __m256i ha=_mm256_and_si256(_mm256_srli_epi16(wa,4),m0f);
      __m256i pca=_mm256_add_epi8(_mm256_shuffle_epi8(tab,la),_mm256_shuffle_epi8(tab,ha));
      acc0=_mm256_add_epi64(acc0,_mm256_sad_epu8(pca,zero));

      __m256i lb=_mm256_and_si256(wb,m0f);
      __m256i hb=_mm256_and_si256(_mm256_srli_epi16(wb,4),m0f);
      __m256i pcb=_mm256_add_epi8(_mm256_shuffle_epi8(tab,lb),_mm256_shuffle_epi8(tab,hb));
      acc1=_mm256_add_epi64(acc1,_mm256_sad_epu8(pcb,zero));
    }
    for(; 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));
      __m256i lo=_mm256_and_si256(win,m0f);
      __m256i hi=_mm256_and_si256(_mm256_srli_epi16(win,4),m0f);
      __m256i pc=_mm256_add_epi8(_mm256_shuffle_epi8(tab,lo),_mm256_shuffle_epi8(tab,hi));
      acc0=_mm256_add_epi64(acc0,_mm256_sad_epu8(pc,zero));
    }
    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);
    }
    {
      __m256i acc=_mm256_add_epi64(acc0,acc1);
      __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);
    }
    {
      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;
  }
}

评测结果