代码

#include <stdint.h>
#include <string.h>
typedef unsigned long u64;
#define MAXN 300000
#define NWMAX ((MAXN+63)/64 + 8)
#define PAD 4
static u64 b1buf[3][NWMAX];
static u64 b2buf[3][NWMAX];
static u64 *b1[3], *b2[3];
static unsigned char mp[256];

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){
  // build byte->value mapping from distinct bytes in s1 and s2
  for(int i=0;i<256;i++) mp[i]=0;
  // collect distinct bytes
  unsigned char seen[256]; memset(seen,0,256);
  int vals[3], nv=0;
  for(int i=0;i<n;i++){ unsigned char c=(unsigned char)s1[i]; if(!seen[c]){ seen[c]=1; if(nv<3){ vals[nv++]=c; } } }
  for(int i=0;i<n;i++){ unsigned char c=(unsigned char)s2[i]; if(!seen[c]){ seen[c]=1; if(nv<3){ vals[nv++]=c; } } }
  // sort vals ascending
  for(int a=0;a<nv-1;a++) for(int b=a+1;b<nv;b++) if(vals[b]<vals[a]){ int t=vals[a];vals[a]=vals[b];vals[b]=t; }
  for(int k=0;k<nv && k<3;k++) mp[vals[k]] = k;

  int NW = (n+63)/64 + 2;
  for(int a=0;a<3;a++){ b1[a]=b1buf[a]+PAD; b2[a]=b2buf[a]+PAD; memset(b1buf[a],0,NWMAX*8); memset(b2buf[a],0,NWMAX*8); }
  for(int i=0;i<n;i++){ int v1=mp[(unsigned char)s1[i]], v2=mp[(unsigned char)s2[i]]; 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]);
}

评测结果