序列哈希

序列哈希可以将一个序列或者字符串以 \(O(len)\) 的时间复杂度压缩成一个 long long（或者 int）。当序列的数量不多的时候（\(\le 10^8\)），一个 hash 值就可以唯一代表一个序列。

我们可以使用序列哈希快速判断回文串，或者搭配哈希表用来 \(O(1)\) 检测序列是否在集合中出现过。

我们提供一种较为稳定的 \(\operatorname{hash}\)：

\[ \operatorname{hash}(a)=\left(\sum_{i=1}^{n}{a_ibase^{i-1}}\right)\bmod p \]

建议 \(p\) 取 \(2^{61}-1\)，\(base\) 取一个略比 \(a\) 值域大的数字。

合并和差分

已知两个序列的 \(\operatorname{hash}\) 和 \(len\)，我们可以 \(O(1)\) 求出它们拼接后的 \(\operatorname{hash}\) 值（当然，需要预处理 \(base^i\)）：

\[ \operatorname{hash}(a+b)=\left(\operatorname{hash}(a)+\operatorname{hash}(b)base^{len(a)}\right)\bmod p \]

由于 \(\operatorname{hash}\) 时序列的每一项较为独立，我们可以通过逆元对 \(\operatorname{hash}\) 值进行差分。因此，我们可以 \(O(1)\) 求得序列区间 \(\operatorname{hash}\) 值，或者树上路径 \(\operatorname{hash}\) 值。

当然，通过移项就不需要求逆元了。

例题

P5537 【XR-3】系统设计

题意

给定一棵 \(n\) 个节点的有根树和一个长度为 \(m\) 的序列 \(a\)。你需要维护两种操作：

• 1 l r x：表示设定起点为节点 \(x\)，接下来依次遍历 \([l,r]\)。当遍历到 \(i\) 时，从当前节点走向它的编号第 \(a_i\)​ 小的儿子。如果某一时刻当前节点的儿子个数小于 \(a_i\)​，或者已经遍历完 \([l,r]\)，则在这个点停住，并输出这个点的编号，同时停止遍历；
• 2 p v：将 \(a_p\) 修改为 \(v\)；

显然，我们可以二分答案找到最长的合法的 \([l,r]\) 的前缀，这样问题就转化为一个判定性问题。

考虑不带修的子问题。如果保证 \(x=rt\)，则可以通过预处理返根链的 \(\operatorname{hash}\) 值 \(h[u]\)，并且使用哈希表维护就可以实现 \(O(\log n)\) 查询。其它情况，我们可以通过差分并移项的方式，去掉 \(1\rightarrow x\) 的贡献。

考虑如何带修，需要哪些数据结构。注意到每次 check() 本质上是查询了序列中一段区间的 \(\operatorname{hash}\) 值。\(\operatorname{hash}\) 值是支持快速合并的，因此可以使用线段树维护。这满足线段树上二分的使用条件。同时线段树上二分支持动态修改，因此可以解决本题。

哈希表的模数不能和 \(base\) 相同

哈希得到的结果仍然很大，可以使用哈希表存储。哈希表需要对哈希值进行取模，注意该模数不能和 \(base\) 相同，否则哈希表会产生大量冲突，导致时间复杂度错误。

代码

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
#define ull unsigned long long
using namespace std;
const int N = 5e5 + 10;
const ll BASE = 1e6 + 3;
const ll MOD2 = (1ll << 61) - 1;
const ll MOD = 1e6 - 3;

namespace io {
    struct fistream {
        char ch;
        template<typename _Tp>
        inline fistream& operator>>(_Tp& x) {
            while(!isdigit(ch = getchar_unlocked()));
            x = ch - 48;
            while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
            return *this;
        }
    } fin;
    struct fostream {
        char buf[60], nb;
        inline fostream() { nb = 0; }
        inline fostream& operator<<(char c) {
            putchar(c);
            return *this;
        }
        template<typename _Tp>
        inline fostream& operator<<(_Tp x) {
            do buf[++nb] = x % 10, x /= 10; while(x);
            while(nb) putchar(buf[nb--] + 48);
            return *this;
        }
    } fout;
}

using io::fin;
using io::fout;

vector<int> adj[N];

void addEdge(int u, int v) {
    adj[u].push_back(v);
}

ull pw[N];
struct hv {
    int len;
    ull hs;
    inline hv() { len = hs = 0; }
    inline hv(int x) { len = 1; hs = x; }
    inline hv operator+(const hv& b) const {
        hv res;
        res.len = len + b.len;
        res.hs = ((__int128)hs * pw[b.len] + b.hs) % MOD2;
        return res;
    }
    inline bool operator==(const hv& b) const {
        return len == b.len && hs == b.hs;
    }
};

struct map {
    struct Node {
        ull key;
        int val, next;
    } pool[MOD];
    int nn, head[MOD];
    inline void insert(ull key, int val) {
        pool[++nn] = {key, val, head[key % MOD]};
        head[key % MOD] = nn;
    }
    inline void insert(const hv& key, int val) {
        insert(key.hs, val);
    }
    inline bool count(const hv& key) const {
        for(int i = head[key.hs % MOD]; i; i = pool[i].next) {
            if(key.hs == pool[i].key) return true;
        }
        return false;
    }
    inline int& operator[](const hv& key) {
        for(int i = head[key.hs % MOD]; i; i = pool[i].next) {
            if(key.hs == pool[i].key) return pool[i].val;
        }
        insert(key, 0);
        return pool[nn].val;
    }
} mp;

hv h[N];

int n, m, q, rt;
int a[N];

namespace SegT {
    hv sum[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    inline void push_up(int p) {
        sum[p] = sum[lc(p)] + sum[rc(p)];
    }
    void build(int p, int l, int r) {
        if(l == r) {
            sum[p] = (hv)a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void modify(int p, int l, int r, int q, int v) {
        if(l == r) {
            sum[p] = (hv)v;
            return;
        }
        int mid = (l + r) >> 1;
        if(q <= mid) modify(lc(p), l, mid, q, v);
        else modify(rc(p), mid + 1, r, q, v);
        push_up(p);
    }
    bool query(int p, int l, int r, int ql, int qr, hv &v) {
        if(l > qr || r < ql) return false;
        if(ql <= l && r <= qr && mp.count(v + sum[p])) {
            v = v + sum[p];
            return false;
        }
        if(l == r) return true;
        int mid = (l + r) >> 1;
        if(query(lc(p), l, mid, ql, qr, v)) return true;
        return query(rc(p), mid + 1, r, ql, qr, v);
    }
}

void dfs(int u, hv cur) {
    mp[cur] = u;
    h[u] = cur;
    for(int i = 0; i < adj[u].size(); i++) {
        int v = adj[u][i];
        dfs(v, cur + (hv)(i + 1));
    }
}

int main() {

    fin >> n >> m >> q;
    for(int i = 1; i <= n; i++) {
        int x;
        fin >> x;
        if(x == 0) {
            rt = i;
        } else {
            addEdge(x, i);
        }
    }

    for(int i = 1; i <= m; i++) fin >> a[i];

    pw[0] = 1;
    for(int i = 1; i <= n; i++) pw[i] = (__int128)pw[i - 1] * BASE % MOD2;

    for(int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end());
    }

    dfs(rt, {});

    SegT::build(1, 1, m);

    while(q--) {
        int op;
        fin >> op;
        if(op == 1) {
            int x, l, r;
            fin >> x >> l >> r;
            hv res = h[x];
            SegT::query(1, 1, m, l, r, res);
            fout << mp[res] << '\n';
        } else {
            int p, v;
            fin >> p >> v;
            a[p] = v;
            SegT::modify(1, 1, m, p, v);
        }
    }

    return 0;
}