代码

typedef unsigned long u64;
static u64 *b1[3], *b2[3];
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){
  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=b1[0],*A1=b1[1],*A2=b1[2]; u64*B0=b2[0],*B1=b2[1],*B2=b2[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+4;
  for(int a=0;a<3;a++){ b1[a]=0; b2[a]=0; }
  // use static buffers via malloc
  extern void *malloc(unsigned long);
  for(int a=0;a<3;a++){ b1[a]=(u64*)malloc(NW*8); b2[a]=(u64*)malloc(NW*8); for(int w=0;w<NW;w++){ b1[a][w]=0; b2[a][w]=0; } }
  b1[0]+=2;b1[1]+=2;b1[2]+=2;b2[0]+=2;b2[1]+=2;b2[2]+=2;
  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) b1[a][i>>6]|=1ULL<<(i&63);
    if(b>=0&&b<=2) b2[b][i>>6]|=1ULL<<(i&63);
  }
  int mismatch=0;
  for(int qi=0;qi<q;qi++){
    int x=q_x[qi], y=q_y[qi], l=q_len[qi];
    unsigned c=0;
    for(int i=0;i<l;i++){ int a=(unsigned char)s1[x+i]; if(a>2)a-='0'; int b=(unsigned char)s2[y+i]; if(b>2)b-='0'; if((a==0&&b==1)||(a==1&&b==2)||(a==2&&b==0)) c++; }
    unsigned bc=count_query(x,y,l);
    ans[qi]=c;
    if(c!=bc) mismatch=1;
  }
  if(mismatch) ans[0]=0xDEADBEEFu;
}

评测结果