Codeforces 608B Hamming Distance Sum （前缀和）

题意：给两个01串S和T，求两个串的距离，即与S等长度的T的子串与S不同的位数（说起来有点绕，看样例好理解）

数据范围： |S|， |T| <= 2e5

思路：由数据范围可知不能瞎暴力，容易发现S的第一位可以与T的第一位到第lenT-lenS+1位对应，第i位可以与第lenT-lenS+i位对应，只要做一遍前缀和，逐位求贡献就行了，前缀和还是很骚气好用的技能orz

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

const int mx = 2e5+10;
char a[mx], b[mx];
int sum[mx];

int main(){
    LL ans = 0;
    scanf("%s%s", a+1, b+1);
    int n = strlen(a+1), m = strlen(b+1);
    for (int i = 1; i <= m; i++){
        if (b[i] == '0') sum[i] = sum[i-1]+1;
        else sum[i] = sum[i-1];
    }
    for (int i = 1; i <= n; i++){
        if (a[i] == '1') ans += sum[m-(n-i)]-sum[i-1];
        else ans += (m-(n-i)-sum[m-(n-i)])-(i-1-sum[i-1]);
    }
    printf("%lld
", ans);
    return 0;
}