Description
给出两个01序列\(A\)和\(B\)
要求回答\(q\)个询问每次询问\(A\)和\(B\)中两个长度为\(len\)的子串的哈明距离
哈明距离的值即有多少个位置不相等
\(1 \le |A|,|B| \le 2*10^5\)
\(1 \le q \le 4*10^5\)
保证输入合法，序列下标从0开始
Solution
大暴力分块，记录一下思想
题解做法比较繁琐
先求出每一个位置开始长度为32的序列状态，压进一个unsigned int
每\(T\)位分一块，处理出\(A\)中第\(i\)块整块构成的字符串和\(B\)中从\(j\)开始长度为\(T\)的子串的哈明距离\(f_{i,j}\)
询问时两边暴力计算，中间用\(f\)计算
时间复杂度\(O(\frac {nm}{32})\)，常数非常不优秀
下面是常数小的做法
求出每一个位置开始长度为64的序列状态，压进一个unsigned long long
询问？直接扫！单次询问复杂度\(O(\frac {len}{64})\)，实测常数非常优秀，大约1.5s出解
Code
#include <cstdio>
#include <cstring>
using namespace std;
typedef unsigned long long ull;
const int N=200005;
int len;
char str[N];
ull a[N],b[N];
int cnt[65536];
inline int sum(ull x){return cnt[x&65535]+cnt[(x>>16)&65535]+cnt[(x>>32)&65535]+cnt[(x>>48)&65535];}
int main(){
scanf("%s",str); len=strlen(str);
for(int i=len-1;i>=0;i--)
a[i]=(a[i+1]>>1)|((ull)(str[i]=='1')<<63);
scanf("%s",str); len=strlen(str);
for(int i=len-1;i>=0;i--)
b[i]=(b[i+1]>>1)|((ull)(str[i]=='1')<<63);
for(int i=0;i<65536;i++) cnt[i]=cnt[i>>1]+(i&1);
int q,x,y,z,ans,up;
scanf("%d",&q);
while(q--){
scanf("%d%d%d",&x,&y,&z);
ans=0;
for(;z>=64;x+=64,y+=64,z-=64)
ans+=sum(a[x]^b[y]);
if(z)
ans+=sum((a[x]^b[y])&((ull)(-1)-(((ull)1<<(64-z))-1)));
printf("%d\n",ans);
}
return 0;
}