题目大意
给出两个(01)序列(A)和(B)
哈明距离定义为两个长度相同的序列中，有多少个对应位置上的数字不一样
"00111" 和 "10101"的距离为2
(Q)次询问，每次询问给出(p_1,p_2,len)
求(a{p_1},a{p_1+1}...a_{p_1+len-1}) 和 (b_{p_1},b_{p_1+1}...b_{p_1+len-1})两个子串的哈明距离
注意：本题中的序列是从(0)开始编号的：(a_0,a_1,...,a_{n-1})
(1leq |A|.|B|leq 2*10^5,1leq Qleq 4*10^5)
(0 leq p_1 leq |a| - len),(0 leq p_2 leq |b| - len)
分析
哈明距离可以转化成异或后有多少个(1)
考虑如何快速的比较两个字符串
我们先求出每个位置往后(32)位/(64)位的压位后的值
这样之后再暴力的复杂度就变成了(frac {len} {32})
我们再考虑对(A)串分块
每长度(T)分一块
预处理(dif[i][j])表示(A)中第(i)块整个块 和 (B)中(j)开始的长度为(T)的串的哈明距离
(O(frac n T *m *frac T {32})=O(frac {n*m} {32}))
对于询问
左右两边暴力扫(O(T))
中间块内的用预处理直接求(O(frac n T))
算出来(T=sqrt n)最优
同时T要是(32)/(64)的倍数
原题空间256M好像开不到(n*sqrt n)的数组要调调参数
优化
块内的复杂度(O(frac {n*m} {32}))小心脏承受不住
可以用FFT优化
s[i]==1的FFT数组中设为1，否则设为-1
将块中串反过来，卷积一波
求出来的值就是(同-异)
而块的大小为(同+异)
(frac {同+异-(同-异)} 2=异)
这样就可以不用1算一次，0算一次再用总数减常数那么大了
结果越跑越慢
各种调参数到5000左右最快了
组合
如果两个算法合起来就完美了(越写越慢还好意思说)
注意
unsigned满位后左移一位可以看作把最高位扔掉后左移一位
bitset的count()是暴力
正确姿势：预处理1<<16内每个数有多少个1，分段算
FFT有负数用round()取整
solution（分块+压位）
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
typedef unsigned long long ull;
const int S=450;
const int M=200003;
const int N=1<<16;
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
}
char s[M];
char t[M];
int n,m,Q;
int sn,MX;
int cnt[N];
ull aw[M],bw[M];
int dif[S][M];
int loc(int x){
return x/sn+1;
}
int getL(int x){
return (x-1)*sn;
}
int getR(int x){
return x*sn-1;
}
int getP(int x){
int L=getL(loc(x));
return x-L+1;
}
int main(){
int i,j,k,BL,BR,L,R,x,y,z,len;
scanf("%s%s",s,t);
n=strlen(s); m=strlen(t);
sn=448; MX=loc(n);
for(i=0;i<N;i++) cnt[i]=cnt[i>>1]+(i&1);
for(i=0;i+63<n;i++)
for(j=i;j<i+64;j++)
aw[i]=aw[i]<<1|(s[j]=='1');
for(i=0;i+63<m;i++)
for(j=i;j<i+64;j++)
bw[i]=bw[i]<<1|(t[j]=='1');
int ful=N-1;
for(i=1;i<=MX;i++){
L=getL(i);
if(L+sn-1>=n) break;
for(j=0;j+sn-1<m;j++){
x=L,y=j;
for(k=7;k>0;k--){
ull tp=aw[x]^bw[y];
dif[i][j]+=cnt[tp&ful]+cnt[tp>>16&ful]+cnt[tp>>32&ful]+cnt[tp>>48];
x+=64; y+=64;
}
}
}
Q=rd();
int ans;
while(Q--){
ans=0;
x=rd(),z=rd(),len=rd();
y=x+len-1;
BL=loc(x); BR=loc(y);
if(BL+1>=BR){
for(i=x;i<=y;i++) ans+=s[i]!=t[z+i-x];
}
else{
if(getL(BL)!=x) BL++;
if(getR(BR)!=y) BR--;
L=getL(BL); R=getR(BR);
for(i=BL;i<=BR;i++)
ans+=dif[i][z+getL(i)-x];
for(i=x;i<L;i++) ans+=s[i]!=t[z+i-x];
for(i=y;i>R;i--) ans+=s[i]!=t[z+i-x];
}
printf("%d
",ans);
}
return 0;
}
solution（分块+FFT）
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
using namespace std;
typedef double db;
const int N=262144;
const int S=207;
const int M=200003;
const db pi=acos(-1.0);
inline int rd(){
int x=0;bool f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=0;
for(;isdigit(c);c=getchar()) x=x*10+c-48;
return f?x:-x;
}
char s[M];
char t[M];
int rev[N];
int n,m,Q;
int sn,MX;
struct CP{
db x,i;
CP(db xx=0.0,db ii=0.0){x=xx;i=ii;}
}a[N],b[N],c[N];
CP operator +(CP x,CP y){return CP(x.x+y.x,x.i+y.i);}
CP operator -(CP x,CP y){return CP(x.x-y.x,x.i-y.i);}
CP operator *(CP x,CP y){return CP(x.x*y.x-x.i*y.i,x.i*y.x+x.x*y.i);}
void FFT(CP *a,int fl){
int i,j,k;
CP W,Wn,u,v;
for(i=0;i<N;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
for(i=2;i<=N;i<<=1){
Wn=CP(cos(2*pi/i),fl*sin(2*pi/i));
for(j=0;j<N;j+=i){
W=CP(1,0);
for(k=j;k<j+i/2;k++,W=W*Wn){
u=a[k];
v=a[k+i/2]*W;
a[k]=u+v;
a[k+i/2]=u-v;
}
}
}
if(fl==1) return ;
for(i=0;i<N;i++) a[i].x/=N;
}
int dif[S][M];
int loc(int x){
return x/sn+1;
}
int getL(int x){
return max(1,(x-1)*sn);
}
int getR(int x){
return min(n,x*sn-1);
}
int getP(int x){
int L=getL(loc(x));
return x-L+1;
}
int main(){
int i,j,BL,BR,L,R,x,y,z,len;
scanf("%s%s",s+1,t+1);
n=strlen(s+1); m=strlen(t+1);
sn=5000; MX=loc(n);
for(i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(N>>1):0);
for(i=1;i<=m;i++) b[i]=(t[i]=='1')?1:-1;
FFT(b,1);
for(i=1;i<=MX;i++){
L=getL(i);
R=getR(i);
for(j=0;j<N;j++) a[j]=CP();
int tt=0;
for(j=R;j>=L;j--) a[++tt]=(s[j]=='1')?1:-1;
FFT(a,1);
for(j=0;j<N;j++) c[j]=a[j]*b[j];
FFT(c,-1);
int sss=R-L+1;
for(j=1;j<=m;j++) dif[i][j]=(sss-round(c[j+sss].x))/2;
}
Q=rd();
int ans;
while(Q--){
ans=0;
x=rd(),z=rd(),len=rd();
x++;z++;//ÎÒ´Ó 1 ´æ
y=x+len-1;
BL=loc(x);BR=loc(y);
if(BL+1>=BR){
for(i=x;i<=y;i++) ans+=(s[i]!=t[z+i-x]);
}
else{
if(getL(BL)!=x) BL++;
if(getR(BR)!=y) BR--;
L=getL(BL); R=getR(BR);
for(i=x;i<L;i++) ans+=(s[i]!=t[z+i-x]);
for(i=BL;i<=BR;i++)
ans+=dif[i][z+getL(i)-x];
for(i=y;i>R;i--) ans+=(s[i]!=t[z+i-x]);
}
printf("%d
",ans);
}
return 0;
}