代码

#include <stdint.h>
#include <stdarg.h>
#include <sys/auxv.h>
typedef unsigned long u64;
struct DuckInfo { u64 abi_version; const char *stdin_ptr; u64 stdin_size; char *stdout_ptr; u64 stdout_limit; u64 stdout_size; char *stderr_ptr; u64 stderr_limit; u64 stderr_size; const char *IB_ptr; u64 IB_limit; char *OB_ptr; u64 OB_limit; u64 tsc_frequency; } __attribute__((packed));

static const char *IN, *INE; static int inited = 0;
static void initio(void){ struct DuckInfo *d = (struct DuckInfo*)getauxval(0x6b637564ULL); if(d){ IN=d->stdin_ptr; INE=IN+d->stdin_size; } inited=1; }
static inline void skipws(void){ while(IN<INE && (unsigned char)*IN<=0x20) IN++; }
static inline int rdint(void){ skipws(); int neg=0; if(IN<INE && *IN=='-'){neg=1;IN++;} int x=0; while(IN<INE && *IN>='0'&&*IN<='9'){ x=x*10+(*IN-'0'); IN++; } return neg?-x:x; }

static int v_scan(const char*fmt, va_list ap){
  if(!inited) initio();
  int c=0;
  for(const char*f=fmt; *f; f++){
    if(*f=='%'){ f++;
      int suppress=0; if(*f=='*'){suppress=1;f++;}
      while(*f=='l'||*f=='h'||*f=='L'||*f=='z'||*f=='j'||*f=='t'||(*f>='0'&&*f<='9')) f++;
      if(*f=='d'||*f=='i'){ int x=rdint(); if(!suppress){ int*p=va_arg(ap,int*); *p=x; } c++; }
      else if(*f=='u'||*f=='o'||*f=='x'||*f=='X'){ int x=rdint(); if(!suppress){ unsigned*p=va_arg(ap,unsigned*); *p=(unsigned)x; } c++; }
      else if(*f=='s'){ skipws(); const char*st=IN; while(IN<INE && (unsigned char)*IN>0x20) IN++; unsigned len=IN-st; if(!suppress){ char*p=va_arg(ap,char*); __builtin_memcpy(p,st,len); p[len]=0; } c++; }
      else if(*f=='c'){ skipws(); if(!suppress){ char*p=va_arg(ap,char*); if(IN<INE)*p=*IN++; } c++; }
      else if(*f==0) break;
    }
  }
  return c;
}
int scanf(const char*fmt,...){ va_list ap; va_start(ap,fmt); int r=v_scan(fmt,ap); va_end(ap); return r; }
int __isoc99_scanf(const char*fmt,...){ va_list ap; va_start(ap,fmt); int r=v_scan(fmt,ap); va_end(ap); return r; }
int fscanf(void*st,const char*fmt,...){ va_list ap; va_start(ap,fmt); int r=v_scan(fmt,ap); va_end(ap); return r; }
int __isoc99_fscanf(void*st,const char*fmt,...){ va_list ap; va_start(ap,fmt); int r=v_scan(fmt,ap); va_end(ap); return r; }

// ---- bitset ----
static u64 b1[3][4700];
static u64 b2[3][4700];

static inline int popc(u64 x){ return __builtin_popcountll(x); }

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 + 2;
  for(int a=0;a<3;a++){ __builtin_memset(b1[a],0,NW*8); __builtin_memset(b2[a],0,NW*8); }
  for(int i=0;i<n;i++){ int v1=s1[i]-'0', v2=s2[i]-'0'; b1[v1][i>>6]|=1ULL<<(i&63); b2[v2][i>>6]|=1ULL<<(i&63); }
  for(int qi=0; qi<q; qi++) ans[qi] = count_query(q_x[qi], q_y[qi], q_len[qi]);
}

评测结果