【CF472G】Design Tutorial: Increase the Constraints

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
",ans);
    }
    return 0;
}