代码

// wc2017b2 AVX2 bitset v5: 2 bitsets (complement) + nibble-lookup popcount, no 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 A1[TOTAL_MAX] __attribute__((aligned(32)));
static u64 A2[TOTAL_MAX] __attribute__((aligned(32)));
static u64 P1[8][TOTAL_MAX] __attribute__((aligned(32)));
static u64 P2[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 j=0;j<TOTAL;j++){ A1[j]=0; A2[j]=0; for(int r=0;r<8;r++){ P1[r][j]=0; P2[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==1)A1[PAD+w]|=bit; else if(a==2)A2[PAD+w]|=bit;
    if(b==1)P1[0][PAD+w]|=bit; else if(b==2)P2[0][PAD+w]|=bit;
  }
  for(int r=1;r<8;r++){
    u64 *s=P1[0], *d=P1[r]; int sh=64-r;
    for(int j=-NW; j<=2*NW+1; j++) d[PAD+j]=(s[PAD+j+1]<<sh)|(s[PAD+j]>>r);
    s=P2[0]; d=P2[r];
    for(int j=-NW; j<=2*NW+1; j++) d[PAD+j]=(s[PAD+j+1]<<sh)|(s[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));

  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 *b1=(const char*)&P1[r][0] + (size_t)(PAD+w_start+woff)*8 + qb;
    const char *b2=(const char*)&P2[r][0] + (size_t)(PAD+w_start+woff)*8 + qb;
    u64 *a1=A1+PAD+w_start, *a2=A2+PAD+w_start;

    unsigned cnt=0;
    if(nw<=6){
      for(int w=0;w<nw;w++){
        u64 s1=loadu64(b1+(size_t)w*8), s2=loadu64(b2+(size_t)w*8);
        u64 a12=a1[w]|a2[w], b12=s1|s2;
        u64 win=((~a12)&s1)|(a1[w]&s2)|(a2[w]&(~b12));
        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 s1=loadu64(b1), s2=loadu64(b2);
      u64 a12=a1[0]|a2[0], b12=s1|s2;
      u64 win=((~a12)&s1)|(a1[0]&s2)|(a2[0]&(~b12));
      if(boff) win &= (~0ULL)<<boff;
      cnt=popc(win);
    }
    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 *va1=(const __m256i*)(a1+w);
    const __m256i *va2=(const __m256i*)(a2+w);
    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 x1=_mm256_loadu_si256(va1+p);
      __m256i x2=_mm256_loadu_si256(va2+p);
      __m256i y1=_mm256_loadu_si256(vb1+p);
      __m256i y2=_mm256_loadu_si256(vb2+p);
      __m256i a12=_mm256_or_si256(x1,x2);
      __m256i b12=_mm256_or_si256(y1,y2);
      __m256i win=_mm256_or_si256(_mm256_or_si256(_mm256_andnot_si256(a12,y1),_mm256_and_si256(x1,y2)),_mm256_andnot_si256(b12,x2));
      __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));
      acc=_mm256_add_epi64(acc,_mm256_sad_epu8(pc,_mm256_setzero_si256()));
    }
    int done=quads*4;
    for(int wl=mid_start+done; wl<=mid_end; wl++){
      u64 s1=loadu64(b1+(size_t)wl*8), s2=loadu64(b2+(size_t)wl*8);
      u64 a12=a1[wl]|a2[wl], b12=s1|s2;
      u64 win=((~a12)&s1)|(a1[wl]&s2)|(a2[wl]&(~b12));
      cnt+=popc(win);
    }
    {
      __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 s1=loadu64(b1+(size_t)wl*8), s2=loadu64(b2+(size_t)wl*8);
      u64 a12=a1[wl]|a2[wl], b12=s1|s2;
      u64 win=((~a12)&s1)|(a1[wl]&s2)|(a2[wl]&(~b12));
      if(beoff!=63) win &= (1ULL<<(beoff+1))-1;
      cnt+=popc(win);
    }
    ans[qi]=cnt;
  }
}

评测结果