树状数组维护字符串hash

· · 个人记录

今天做这题，一看题解全是线段树维护哈希，出于对树状数组的热爱（其实是不会线段树），我自己口胡了一种树状数组维护哈希的做法。

正常的树状数组是这样的。（n = 6）：

哈希是把字符串的 1 到 i 位变成一个 base 进制数。

那么我们发现假设一个序列的第 i 位的值是 x，那么它对哈希后的第 j 位数的哈希值会造成 x \times base^{j - i} 的贡献。

树状数组在单点加的时候可以维护。

具体来讲，假设我们现在更新树状数组的 x 位，接下来要更新 x + lowbit(x) ， 那么我们要给树状数组上加的 val 就应该变成 val \times base^{lowbit(x)} 。

代码如下（注意要先改 val ）：

inline void add(int x, u64 y) {
    for(; x <= n; y *= s[x & -x], x += x & -x) c[x] += y;
}

查询的时候有一点要注意：

假设我们查询原数组 s 位的哈希值，统计好树状数组的 s 位后，接下来要统计 s - lowbit(s) 位，这一位上已经统计了原数组 s - lowbit(s) 之前的答案，然而这一位上的答案没有计算对 s 的贡献，就是没有乘上 base^{lowbit(s)} 那么我们乘上这个值之后再统计就好了，再前面的位置也同理。

代码：

inline u64 ask(int x, u64 ret = 0, u64 lazy_base = 1) {
    for(; x; lazy_base *= s[x & -x], x -= x & -x) ret += c[x] * lazy_base;
    return ret;
}

那么对于这题，思路和其他题解一样，用树状数组维护哈希即可。

代码：

/*他说他是乱打的

*/
#include <bits/stdc++.h>
#define u64 unsigned long long
using namespace std;
const u64 base = 3221225477;
int n;
int a[500010];
u64 s[500010];
struct hash_BIT {
    u64 c[500010];
    void clear() {
        memset(c, 0, sizeof(c));
    }
    inline void add(int x, u64 y) {
        for(; x <= n; y *= s[x & -x], x += x & -x)  c[x] += y;
    }
    inline u64 ask(int x, u64 ret = 0, u64 lazy_base = 1) {
        for(; x; lazy_base *= s[x & -x], x -= x & -x) ret += c[x] * lazy_base;
        return ret;
    }
}z, f;
inline bool check(int p) {
    int len = min(p, n - p + 1);
    int q = n - p + 1;
    u64 hashp = z.ask(p - 1) - z.ask(p - len) * s[len - 1];
    u64 hashq = f.ask(q - 1) - f.ask(q - len) * s[len - 1];
    return hashp != hashq;
}
int main() {
    int T;
    cin >> T;
    s[0] = 1;
    for(int i = 1; i <= 500000; i++) s[i] = s[i - 1] * base;
    while(T--) {
        f.clear(), z.clear();
        cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        bool flg = 0;
        for(int i = 1; i <= n; i++) {
            if(check(a[i])) flg = 1;
            z.add(a[i], 1);
            f.add(n - a[i] + 1, 1);
        }
        if(flg) puts("Y");
        else puts("N");

    }



    return 0;
/*
*/
}
/*后记
无
*/