Description
给出两个(01)序列(A)和(B)
哈明距离定义为两个长度相同的序列中，有多少个对应位置上的数字不一样（如：(00111)和(10101)的距离为2）
现有(Q)次询问，每次给出(p1,p2,len)，求(A[p1...p1+len-1])和(B[p2...p2+len-1])两个子串的哈明距离，编号从(0)开始
数据范围：
(1<=|A|,|B|<=2*10^5,1<=Q<=4*10^5)，(0<=p1<=|A|-len,0<=p2<=|B|-len)
”Solution“
这是一篇假题解qwq只是记录一下这种优秀的压位做法（虽然说。。cf上面好像会被卡Q^Q）
因为没有修改操作之类的东西，串是给定的，所以说我们可以将原串中每一位开始的连续的64位（或者32位压也可以）压成一个unsigned long long（或者long long）
这样我们可以直接对应的一段取出来异或一下，然后再统计一下异或出来的结果中有多少个(1)就可以知道答案了
统计的话我们可以预处理一下(1sim 2^{16}-1)的的每一个数写成二进制之后有多少个(1)（记录在(cnt)数组中）然后将异或出来的结果分成(4)段，每段(16)位这样来直接在(cnt)中查，最后将结果累加一下就能够得到答案了
如果说(64)位(64)位分有剩的话，最后一次查询的时候要强行把末尾多余的位去掉（左移一下就好了），时间复杂度是(O(frac{nQ}{64}))，不过常数比较小
Solution
好的接下来的部分是真题解嗯
考虑分块，块两头暴力比较，块内的预处理一个数组(dis[i][j])表示(A)串中第(i)块整块（长度为(L)）和(B)串中(j)开头的长度为(L)的子串的哈明距离
当然我们可以用上面的那种压位方法来预处理这个(dis)数组，然而很开心T掉了
注意到因为(L)是固定的（块的长度），所以我们可以用FFT优化一下
FFT中的(AB)串对应的数组的赋值都是：如果说这个位上的数字为(1)则赋为(1)，否则赋为(-1)
然后将(A)串对应的那个串反过来，做卷积，那么求出来的值就是“同-异”，而整个块的大小(L=)同+异，我们要求的是异，所以直接(同异同异异frac{同+异-(同-异)}{2}=异)
剩下的是分块的常规操作
mark：计算不同的位置数量的方法记录一下
Code
压位版本
#include<iostream>
#include<cstdio>
#include<cstring>
#define ull unsigned long long
using namespace std;
const int N=2*(1e5)+10,Div=(1<<16)-1;
char A[N],B[N];
ull a[N],b[N],cnt[1<<16];
int n,m,tot,Q,lena,lenb,ans;
void prework(){
for (int i=lena-1;i>=0;--i) a[i]=(a[i+1]>>1)|((ull)(A[i]-'0')<<63);
for (int i=lenb-1;i>=0;--i) b[i]=(b[i+1]>>1)|((ull)(B[i]-'0')<<63);
cnt[0]=0;
for (int i=1;i<1<<16;++i) cnt[i]=cnt[i>>1]+(i&1);
}
ull sum(ull x){return cnt[x&Div]+cnt[x>>16&Div]+cnt[x>>32&Div]+cnt[x>>48&Div];}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
int p1,p2,len;
scanf("%s",A);lena=strlen(A);
scanf("%s",B);lenb=strlen(B);
scanf("%d",&Q);
prework();
for (int i=1;i<=Q;++i){
scanf("%d%d%d",&p1,&p2,&len);
ans=0;
for (;len>=64;p1+=64,p2+=64,len-=64)
ans+=sum(a[p1]^b[p2]);
if (len)
ans+=sum((a[p1]^b[p2])>>(64-len));
printf("%d
",ans);
}
}
分块+FFT版本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define ll long long
using namespace std;
const int N=2e5+10,B=5000,C=N/B+10;
const double pi=acos(-1);
struct cmplx{/*{{{*/
double a,b;
cmplx(){}
cmplx(double a1,double b1){a=a1; b=b1;}
void init(){a=b=0;}
friend cmplx operator + (cmplx x,cmplx y)
{return cmplx(x.a+y.a,x.b+y.b);}
friend cmplx operator - (cmplx x,cmplx y)
{return cmplx(x.a-y.a,x.b-y.b);}
friend cmplx operator * (cmplx x,cmplx y)
{return cmplx(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);}
};/*}}}*/
namespace FFT{/*{{{*/
const int TOP=20,N=(1<<18)+10;
cmplx A[N],B[N];
int rev[N],vis[TOP+1];
int len;
void get_len(int n){
for (int i=0;i<len;++i) A[i].init(),B[i].init();
int bit=0;
for (len=1;len<=n;++bit,len<<=1);
rev[0]=0;
for (int i=1;i<len;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
}
void clr(int op){
for (int i=0;i<len;++i) if (op) B[i].init();else A[i].init();
}
void fft(cmplx *a,int op){
for (int i=0;i<len;++i)
if (rev[i]>i) swap(a[rev[i]],a[i]);
cmplx w,u,v,w_n;
for (int step=2,k=0;step<=len;step<<=1,++k){
w_n=cmplx(cos(2*pi/step),op*sin(2*pi/step));
for (int st=0;st<len;st+=step){
w=cmplx(1,0);
for (int i=0;i<(step>>1);++i){
//w=W[k][i]; w.b*=op;
v=a[st+i+(step>>1)]*w;
u=a[st+i];
a[st+i]=u+v;
a[st+i+(step>>1)]=u-v;
w=w*w_n;
}
}
}
if (op==1) return;
for (int i=0;i<len;++i) a[i].a/=len;
}
}/*}}}*/
char a[N],b[N];
ll dis[C][N];
int n,m,sq,q,numa,numb;
ll get_val(cmplx x){return 1LL*round(x.a);}
int Id(int x){return (x-1)/sq+1;}
int St(int x){return (x-1)*sq+1;}
int Ed(int x){return x*sq;}
void prework(){
sq=B;
int l,r,len;
numa=Id(n);
numb=Id(m);
FFT::get_len(B+m);
for (int i=1;i<=m;++i) FFT::B[i]=cmplx(b[i]=='1'?1:-1,0);
FFT::fft(FFT::B,1);
for (int i=1;i<=numa;++i){
l=St(i); r=min(Ed(i),n);
FFT::clr(0);
for (int j=r;j>=l;--j) FFT::A[r-j+1]=cmplx(a[j]=='1'?1:-1,0);
FFT::fft(FFT::A,1);
for (int j=0;j<FFT::len;++j) FFT::A[j]=FFT::A[j]*FFT::B[j];
FFT::fft(FFT::A,-1);
len=r-l+1;
for (int j=1;j<=m;++j)
dis[i][j]=(len-get_val(FFT::A[j+len]))/2;
}
}
int query(int p1,int p2,int len){
int ret=0;
int num1=Id(p1),num2=Id(p1+len-1);
if (num1==num2){
for (int i=0;i<len;++i)
ret+=a[p1+i]!=b[p2+i];
}
else{
for (int i=p1;i<=Ed(num1);++i)
ret+=a[i]!=b[p2+i-p1];
for (int i=num1+1;i<num2;++i)
ret+=dis[i][p2+St(i)-p1];
for (int i=St(num2);i<=p1+len-1;++i)
ret+=a[i]!=b[p2+i-p1];
}
return ret;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
int p1,p2,len;
scanf("%s",a+1);
scanf("%s",b+1);
n=strlen(a+1); m=strlen(b+1);
prework();
scanf("%d",&q);
for (int i=1;i<=q;++i){
scanf("%d%d%d",&p1,&p2,&len);
++p1; ++p2;
printf("%d
",query(p1,p2,len));
}
}