Description
维护一个字符串, 支持插入字符, 修改字符, 以及求两个后缀的 \(lcp\).
Solution
建立一棵 \(Splay\) 来维护整个串, 每个节点维护整个子树的哈希值. 对于插入, 直接在对应的位置插入; 修改也直接修改就好; 然后一路 \(update\). 对于查询, 考虑二分, 然后每次查询对应区间的哈希值,\(O(1)\) 判断即可.
查询某个区间的哈希值, 用 \(Splay\) 写的话比较方便, 对于区间 \([l,r]\), 直接把 \(l-1\) 旋转到根, 把 \(r+1\) 旋转到根节点的右儿子, 那么根节点的右儿子的左儿子的哈希值就是区间 \([l,r]\) 的哈希值.
- Code
- #include <bits/stdc++.h>
- using namespace std;
- typedef unsigned long long ull;
- const int _ = 1e5 + 10;
- const int __ = 3e5 + 10;
- const int base = 233;
- char s[_];
- int N, M;
- ull p[__];
- struct Splay {
- int fa[__], son[__][2], val[_], siz[_];
- ull h[_];
- int tot, root;
- int alloc(int v, int f) {
- fa[++tot] = f, siz[tot] = 1;
- son[tot][0] = son[tot][1] = 0;
- val[tot] = h[tot] = v;
- return tot;
- }
- void update(int x) {
- siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1;
- h[x] = h[son[x][1]] + val[x] * p[siz[son[x][1]]] +
- h[son[x][0]] * p[siz[son[x][1]] + 1];
- }
- int ident(int x) { return son[fa[x]][1] == x; }
- void connect(int x, int f, int k) { fa[x] = f, son[f][k] = x; }
- void rotate(int x) {
- int y = fa[x], z = fa[y];
- if (y == root) root = x;
- int yson = ident(x), zson = ident(y);
- int k = son[x][yson ^ 1];
- connect(k, y, yson);
- connect(y, x, yson ^ 1);
- connect(x, z, zson);
- update(y), update(x);
- }
- void splay(int x, int to) {
- while (fa[x] != to) {
- int y = fa[x], z = fa[y];
- if (z != to) (ident(x)) ^ (ident(y)) ? rotate(x) : rotate(y);
- rotate(x);
- }
- if (!to) root = x;
- }
- int find(int x) {
- int u = root;
- while (1) {
- if (x == siz[son[u][0]] + 1) return u;
- if (x <= siz[son[u][0]])
- u = son[u][0];
- else
- x -= siz[son[u][0]] + 1, u = son[u][1];
- }
- }
- void insert(int x, int v) {
- if (!root) {
- root = alloc(v, 0);
- return;
- }
- int u = find(x);
- splay(u, 0);
- if (!son[u][1]) {
- son[u][1] = alloc(v, u);
- update(u);
- return;
- } else {
- u = find(x + 1);
- splay(u, root);
- son[u][0] = alloc(v, u);
- update(u), update(root);
- return;
- }
- }
- void modify(int x, int v) {
- int u = find(x);
- splay(u, 0);
- val[u] = v;
- update(u);
- }
- ull query(int l, int r) {
- int u = find(l);
- splay(u, 0);
- if (l == r) return val[u];
- u = find(r);
- splay(u, root);
- return h[son[u][0]] * p[1] + val[u] + val[root] * p[siz[son[u][0]] + 1];
- }
- } tr;
- inline void init(const int lim = 3e5) {
- p[0] = 1;
- for (int i = 1; i <= lim; ++i) p[i] = p[i - 1] * base;
- for (int i = 1; i <= N; ++i) tr.insert(i - 1, s[i] - 'a' + 1);
- }
- inline bool check(int x, int y, int len) {
- return tr.query(x, x + len - 1) == tr.query(y, y + len - 1);
- }
- int calc(int x, int y) {
- int l = 0, r = min(N - x, N - y) + 1;
- while (l <r) {
- int mid = (l + r + 1)>> 1;
- if (check(x, y, mid))
- l = mid;
- else
- r = mid - 1;
- }
- return l;
- }
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("martian.in", "r", stdin);
- freopen("martian.out", "w", stdout);
- #endif
- scanf("%s%d", s + 1, &M);
- N = strlen(s + 1);
- init();
- char op[3], v[3];
- int x, y;
- while (M--) {
- scanf("%s%d", op, &x);
- if (op[0] == 'Q') {
- scanf("%d", &y);
- printf("%d\n", calc(x, y));
- } else if (op[0] == 'R') {
- scanf("%s", v);
- char c = v[0];
- tr.modify(x, c - 'a' + 1);
- } else if (op[0] == 'I') {
- scanf("%s", v);
- char c = v[0];
- tr.insert(x, c - 'a' + 1);
- ++N;
- }
- }
- return 0;
- }
[JSOI2008] 火星人 - Splay + 哈希
来源: http://www.bubuko.com/infodetail-3362648.html