代码

typedef unsigned long u64;
static u64 bbuf[6][4700];
static inline int popc(u64 x){ x=x-((x>>1)&0x5555555555555555ULL); x=(x&0x3333333333333333ULL)+((x>>2)&0x3333333333333333ULL); x=(x+(x>>4))&0x0f0f0f0f0f0f0f0fULL; return (int)((x*0x0101010101010101ULL)>>56); }
static unsigned count_query(int x,int y,int l, u64*B0, u64*B1, u64*B2){
  long long d=(long long)y-x; int off=(int)(d&63); int woff=(int)(d>>6);
  unsigned ans=0; int w_start=x>>6,boff=x&63; int end=x+l; int w_end=(end-1)>>6,beoff=(end-1)&63;
  u64*A0=bbuf[0]+2,*A1=bbuf[1]+2,*A2=bbuf[2]+2;
  for(int w=w_start;w<=w_end;w++){ int wb=w+woff; u64 a0=A0[w],a1=A1[w],a2=A2[w]; u64 sb0,sb1,sb2;
    if(off){ sb0=(B0[wb+1]<<(64-off))|(B0[wb]>>off); sb1=(B1[wb+1]<<(64-off))|(B1[wb]>>off); sb2=(B2[wb+1]<<(64-off))|(B2[wb]>>off); }
    else { sb0=B0[wb]; sb1=B1[wb]; sb2=B2[wb]; }
    u64 win=(a0&sb1)|(a1&sb2)|(a2&sb0);
    if(w==w_start) win&=(~0ULL)<<boff;
    if(w==w_end&&beoff!=63) win&=((1ULL<<(beoff+1))-1);
    ans+=popc(win);
  }
  return ans;
}
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)/64+2;
  for(int a=0;a<6;a++){ for(int w=0;w<NW;w++) bbuf[a][w]=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';
    if(a>=0&&a<=2) bbuf[a][(i>>6)+2]|=1ULL<<(i&63);
    if(b>=0&&b<=2) bbuf[3+b][(i>>6)+2]|=1ULL<<(i&63);
  }
  u64*B0=bbuf[3]+2, *B1=bbuf[4]+2, *B2=bbuf[5]+2;
  for(int qi=0;qi<q;qi++) ans[qi]=count_query(q_x[qi],q_y[qi],q_len[qi],B0,B1,B2);
}

评测结果