代码

// wc2017b2 correct 32-bit-safe bitset (uint64_t + inline popcnt + full padding).
#include <stdint.h>
#include <stdlib.h>

typedef uint64_t u64;

static u64 *B;
static u64 *A0,*A1,*A2,*B0,*B1,*B2;

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

void solve(int n,int q,char*s1,char*s2,int*q_x,int*q_y,int*q_len,unsigned*ans){
  int NW = (n+63)>>6;
  int PAD = NW + 8;
  int TOTAL = NW + 2*PAD + 16;
  B = (u64*)calloc((size_t)TOTAL * 6, 8);
  A0 = B + PAD;
  A1 = B + TOTAL + PAD;
  A2 = B + 2*TOTAL + PAD;
  B0 = B + 3*TOTAL + PAD;
  B1 = B + 4*TOTAL + PAD;
  B2 = B + 5*TOTAL + PAD;
  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)A0[w]|=bit; else if(a==1)A1[w]|=bit; else if(a==2)A2[w]|=bit;
    if(b==0)B0[w]|=bit; else if(b==1)B1[w]|=bit; else if(b==2)B2[w]|=bit;
  }
  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 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;
    unsigned cnt=0;
    u64 *pA0=A0+w_start, *pA1=A1+w_start, *pA2=A2+w_start;
    u64 *pB0=B0+w_start+woff, *pB1=B1+w_start+woff, *pB2=B2+w_start+woff;
    if(off==0){
      if(nw==1){
        u64 win=(pA0[0]&pB1[0])|(pA1[0]&pB2[0])|(pA2[0]&pB0[0]);
        if(boff) win &= (~0ULL)<<boff;
        if(beoff!=63) win &= (1ULL<<(beoff+1))-1;
        cnt=popc(win);
      } else {
        u64 w0=(pA0[0]&pB1[0])|(pA1[0]&pB2[0])|(pA2[0]&pB0[0]);
        if(boff) w0 &= (~0ULL)<<boff;
        cnt=popc(w0);
        for(int w=1;w<nw-1;w++){
          u64 win=(pA0[w]&pB1[w])|(pA1[w]&pB2[w])|(pA2[w]&pB0[w]);
          cnt+=popc(win);
        }
        int lw=nw-1;
        u64 wl=(pA0[lw]&pB1[lw])|(pA1[lw]&pB2[lw])|(pA2[lw]&pB0[lw]);
        if(beoff!=63) wl &= (1ULL<<(beoff+1))-1;
        cnt+=popc(wl);
      }
    } else {
      int sh=64-off;
      if(nw==1){
        u64 sb0=(pB0[1]<<sh)|(pB0[0]>>off);
        u64 sb1=(pB1[1]<<sh)|(pB1[0]>>off);
        u64 sb2=(pB2[1]<<sh)|(pB2[0]>>off);
        u64 win=(pA0[0]&sb1)|(pA1[0]&sb2)|(pA2[0]&sb0);
        if(boff) win &= (~0ULL)<<boff;
        if(beoff!=63) win &= (1ULL<<(beoff+1))-1;
        cnt=popc(win);
      } else {
        u64 sb0=(pB0[1]<<sh)|(pB0[0]>>off);
        u64 sb1=(pB1[1]<<sh)|(pB1[0]>>off);
        u64 sb2=(pB2[1]<<sh)|(pB2[0]>>off);
        u64 w0=(pA0[0]&sb1)|(pA1[0]&sb2)|(pA2[0]&sb0);
        if(boff) w0 &= (~0ULL)<<boff;
        cnt=popc(w0);
        for(int w=1;w<nw-1;w++){
          u64 s0=(pB0[w+1]<<sh)|(pB0[w]>>off);
          u64 s1=(pB1[w+1]<<sh)|(pB1[w]>>off);
          u64 s2=(pB2[w+1]<<sh)|(pB2[w]>>off);
          u64 win=(pA0[w]&s1)|(pA1[w]&s2)|(pA2[w]&s0);
          cnt+=popc(win);
        }
        int lw=nw-1;
        u64 l0=(pB0[lw+1]<<sh)|(pB0[lw]>>off);
        u64 l1=(pB1[lw+1]<<sh)|(pB1[lw]>>off);
        u64 l2=(pB2[lw+1]<<sh)|(pB2[lw]>>off);
        u64 wl=(pA0[lw]&l1)|(pA1[lw]&l2)|(pA2[lw]&l0);
        if(beoff!=63) wl &= (1ULL<<(beoff+1))-1;
        cnt+=popc(wl);
      }
    }
    ans[qi]=cnt;
  }
}

评测结果