BZOJ 1014: [JSOI2008]火星人 – [Splay/哈希]


题目传送门(BZOJ)
>原文链接<

题解 :

维护一个数据结构, 支持插入, 修改, 查询从两个点开始的最长公共前缀.

一棵维护区间的Splay能很好的完成这个任务

插入与修改就是Splay的插入和修改, 查询的时候利用二分答案+Splay提出长度为mid的区间, 求哈希验证.

而对于哈希值的维护, 节点p的哈希值代表这个节点所有子区间字符串的哈希,

h[p] = (h[ls]\times Base + val[p])\times Base^{siz[ls]}+h[ls]

一个比较基础的维护哈希的合并的做法.

插入的时候记得累加整颗树的size

代码 :

#include 
#include 
#include 
#define ls ch[p][0]
#define rs ch[p][1]
using namespace std;
#define ull unsigned long long
#define get(x) (ch[f[x]][1]==x)
const int N = 200000;
const ull B = 1313131;
int siz[N], f[N], ch[N][2], val[N], root, sz;
char opt[5], s[N];
ull h[N], mi[N];
int n, m;
inline void up(int p) {
    if(!p) return ;
    siz[p] = siz[ls] + siz[rs] + 1;
    h[p] = (h[ls]*B+val[p])*mi[siz[rs]]+h[rs];
}
void build(int l, int r, int fa, bool flg) {
    if(l > r) return;
    int p = (l+r) >> 1;
    ch[fa][flg] = p;
    val[p] = s[p-1];
    f[p] = fa;
    siz[p] = r-l+1;
    build(l, p-1, p, 0);
    build(p+1, r, p, 1);
    up(p); 
}
inline void rotate(int x) {
    int y = f[x], z = f[y], k = get(x);
    ch[y][k] = ch[x][!k], f[ch[y][k]] = y;
    ch[x][!k] = y, f[y] = x, f[x] = z;
    if(z) ch[z][ch[z][1]==y] = x;
    up(y), up(x);
    if(root == y) root = x;
}
inline void splay(int x, int y) {
    for(int fa; (fa = f[x]) != y; rotate(x)) {
        if(f[fa] != y) rotate(get(x) == get(fa) ? fa : x);
    }
}
inline int find(int x) {
    int p = root;
    while(1) {
        if(x <= siz[ls]) p = ls;
        else {
            x -= siz[ls]+1;
            if(!x) return p;
            p = rs;
        }
    }
}
inline ull getHash(int x, int p) {
    p += 2;
    x = find(x), p = find(p);
    splay(x, 0), splay(p, root);
    return h[ls];
}
inline int solve(int x, int y) {
    int l = 1, r = sz-max(x, y);
    while(l < r) {
        int mid = (l+r) >> 1;
        if(getHash(x, x+mid-1) == getHash(y, y+mid-1)) l = mid+1;
        else r = mid;
    }
    return --l;
}
inline void change(int x, char c) {
    x = find(x+1);
    splay(x, 0);
    val[x] = c;
    up(x);
}
inline void insert(int x, char c) {
    ++ x; int p = x+1;
    x = find(x), p = find(p);
    splay(x, 0);
    splay(p, root);
    ls = ++ sz;
    h[ls] = val[ls] = c;
    siz[ls] = 1;
    f[ls] = p;
    up(p), up(x);
}
int main() {
    scanf("%s%d", s+1, &m);
    n = strlen(s+1);
    mi[0] = 1;
    for(int i = 1; i < N; i ++ ) mi[i] = mi[i-1]*B;
    build(1, n+2, 0, 0);
    sz = n+2;
    root = (n+3) >> 1;
    for(int i = 1, x; i <= m; i ++ ) {
        scanf("%s%d", opt, &x);
        if(opt[0] == 'Q') {
            int y;
            scanf("%d", &y);
            printf("%d\n", solve(x, y));
        }
        else if(opt[0] == 'R') {
            scanf("%s", opt);
            change(x, opt[0]);
        }
        else {
            scanf("%s", opt);
            insert(x, opt[0]);
        }
    }
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注