题解 P4036 【[JSOI2008]火星人】

· · 题解

做法：平衡树（Splay）维护哈希值

这篇题解会具体讲讲 Splay 的过程，供新手参考。

观察插入操作，插入的实际上是一个下标，比如在下标 2 和 3 之间插入一个字母 a，相当于插入了一个位于 2.5 的 a （脑补即可）。对于此类问题，平衡树上的关键字设为下标，而它的值则为它表示的字母。对于一个节点，它的左子树上的节点都是在下标比它小的字符，右子树上的节点都是下标比它大的字符。

先说查询操作。
二分求 Hash 值的做法比较明显，这里主要讲区间查询 Hash。当我们查询区间 [l,r] 的 Hash 值，我们可以这样把它转换为树的 Hash 值：

那么，A 中所有元素都是下标大于 l-1 且小于 r+1 的数，实际就是区间 [l,r]。

维护 Hash ：s[x].hs=s[s[x].son[0]].hs+(ull)s[x].val*p[s[s[x].son[0]].sz] + s[s[x].son[1]].hs*p[s[s[x].son[0]].sz+1];

其中，p(i) 表示进制的 i 次方。

修改操作

这个比较简单，把待修改的节点旋转至根节点后直接修改即可。

插入操作

比如我们需要插入下标为 2.5 的字符，那么我们可以插在这里：

虽然不能真的插入 2.5 但我们只要把节点插在这个位置上无论如何旋转它都能维持下标为 2.5 的性质。

提供代码，仅供参考：

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
int read() {
    int x=0, f=1; char ch=' ';
    while(!isdigit(ch)) {ch=getchar(); if(ch=='-') f=-1;}
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return x*f;
}
int n, root, size;
ull p[1000005];
struct AB{
    int val, f, son[2], sz;
    ull hs;
}s[1000005];
int get_son(int x) {
    return x==s[s[x].f].son[1];
}
void update(int x) {
    if(!x) return;
    s[x].sz=1;
    if(s[x].son[0]) s[x].sz+=s[s[x].son[0]].sz;
    if(s[x].son[1]) s[x].sz+=s[s[x].son[1]].sz;
    s[x].hs=s[s[x].son[0]].hs+(ull)s[x].val*p[s[s[x].son[0]].sz] + s[s[x].son[1]].hs*p[s[s[x].son[0]].sz+1];
}
void build(int l, int r, int x) {
    if(l>r) return;
    int mid=(l+r)>>1;
    if (mid >= x) s[x].son[1] = mid;
    else s[x].son[0] = mid;
    s[mid].f = x, s[mid].sz = 1;
    if (l==r) return;
    build(l, mid-1, mid), build(mid+1, r, mid);
    update(mid);
    return ;
}
void rotate(int x) {
    int fa=s[x].f, ffa=s[fa].f, wson=get_son(x);
    s[fa].son[wson]=s[x].son[wson^1];
    s[s[fa].son[wson]].f=fa;
    s[x].son[wson^1]=fa;
    s[fa].f=x;
    s[x].f=ffa;
    if(ffa) s[ffa].son[s[ffa].son[1]==fa]=x;
    update(fa);
    update(x);
} 
void splay(int x, int goal) {
    for(int fa;(fa=s[x].f)!=goal;rotate(x)) {
        if(s[fa].f!=goal) {
            rotate((get_son(x)==get_son(fa))?fa:x);
        }
    }
    update(x);
    if(goal==0) root=x;
}
int find(int x) {
    int now=root;
    while(1) {
        if (s[s[now].son[0]].sz+1 == x) return now;
        if (s[s[now].son[0]].sz+1 < x) x -= (s[s[now].son[0]].sz+1), now = s[now].son[1];
        else now = s[now].son[0];
    }
}
int get_hash(int l, int r) {
    int x=find(l), y=find(r+2);
    splay(x, 0), splay(y, root);
    return s[s[s[root].son[1]].son[0]].hs;
}
char ch[1000005];
int t;
int main() {
    scanf("%s", ch+1);
    n=strlen(ch+1);
    p[0]=1;
    for(int i=1;i<=n*2;i++) p[i]=p[i-1]*27ull;
    for(int i=2;i<=n+1;i++) {
        s[i].val=s[i].hs=ch[i-1]-'a'+1;
    }
    build(1, n+2, root);
    root = (n+3) >> 1, size=n+2;
    cin>>t;
    while(t--) {
        char type[3], ch[3];
        scanf("%s", type);
        if(type[0]=='Q') {
            int x=read(), y=read();
            if(x>y) swap(x, y);
            int l=0, r=size-y-1, mid;
            while(l<r) {
                mid=(l+r+1)>>1;
                if(get_hash(x, x+mid-1)==get_hash(y, y+mid-1)) l=mid;
                else r=mid-1;
            }
            printf("%d\n", l);
        }
        if(type[0]=='R') {
            int x=read();
            scanf("%s", ch);
            splay(find(x+1), 0);
            s[root].val=ch[0]-'a'+1;
            update(root);
        }
        if(type[0]=='I') {
            int u=read();
            scanf("%s", ch);
            int x=find(u+1), y=find(u+2);
            splay(x, 0); splay(y, x);
            s[s[root].son[1]].son[0] = ++size;
            s[size].f = s[root].son[1];
            s[size].val = s[size].hs = ch[0]-'a'+1;
            splay(size, 0);
        }
    }
}