代码

#define u32 unsigned
#define u16 unsigned short
#define fo(i,x,y) for(int i = x;i <= y;++i)
u16 b1[300010][3],b2[300010][3],pp[256];
inline char pop(u16 x) {return pp[x >> 8] + pp[x & 255];}
void solve(int n, int q, char *s1, char *s2, int *q_x, int *q_y, int *q_len, u32 *ans)
{
	fo(i,1,255) pp[i] = pp[i >> 1] + (i & 1);
	fo(i,0,n - 1) s1[i] = (s1[i] - 47) % 3,s2[i] -= 48;
	fo(i,0,n - 15) fo(j,0,2) fo(k,0,15) b1[i][j] = b1[i][j] << 1 | (s1[i + k] == j);
	fo(i,0,n - 15) fo(j,0,2) fo(k,0,15) b2[i][j] = b2[i][j] << 1 | (s2[i + k] == j);
	fo(i,0,q - 1)
	{
		int x = q_x[i],y = q_y[i],l = q_len[i];
		ans[i] = 0;
		if(l == 0) continue;
		int J = 0,a1 = 0,a2 = 0,a3 = 0;
		for(int j = 0;j + 17 <= l;j += 16)
		{
			a1 += pop(b1[x + j][0] & b2[y + j][0]);
			a2 += pop(b1[x + j][1] & b2[y + j][1]);
			a3 += pop(b1[x + j][2] & b2[y + j][2]);
			J = j + 16;
		}
		fo(j,J,l - 1) a1 += (s1[x + j] == s2[y + j]);
		ans[i] = a1 + a2 + a3;
	}
}

评测结果