欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

BZOJ1014: [JSOI2008]火星人prefix(splay 二分 hash)

程序员文章站 2022-04-14 20:22:05
题意 "题目链接" Sol 一眼splay + 二分hash,不过区间splay怎么写来着呀 试着写了两个小时发现死活不对 看了一下yyb的代码发现自己根本就不会splay。。。。 cpp // luogu judger enable o2 include define ull unsigned l ......

题意

题目链接

sol

一眼splay + 二分hash,不过区间splay怎么写来着呀

试着写了两个小时发现死活不对

看了一下yyb的代码发现自己根本就不会splay。。。。

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ull unsigned long long 
using namespace std;
const int maxn = 1e6 + 10;
const ull base = 27;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m;
char s[maxn];
int root, tot, ch[maxn][2], fa[maxn], siz[maxn];
ull ha[maxn], val[maxn], po[maxn];
bool rev[maxn];
int ident(int x) {
    return ch[fa[x]][1] == x;
}
void connect(int x, int f, int id) {
    fa[x] = f; ch[f][id] = x;
}
void update(int x) {
    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
    ha[x] = ha[ch[x][0]] + val[x] * po[siz[ch[x][0]]] + po[siz[ch[x][0]] + 1] * ha[ch[x][1]];
}
void rotate(int x) {
    int y = fa[x], r = fa[y], yson = ident(x), rson = ident(y);
    int b = ch[x][yson ^ 1];
    connect(x, r, rson); connect(b, y, yson); connect(y, x, yson ^ 1);
    update(y); update(x); 
}
void splay(int x, int to) {
    //to = fa[to];
    while(fa[x] != to) {
        if(fa[fa[x]] == to) rotate(x);
        else if(ident(x) == ident(fa[x])) rotate(fa[x]), rotate(x);
        else rotate(x), rotate(x);
    }
    if(!to) root = x; update(x);
}
int find(int k) {
    int x = root;
    while(1) {
        if(siz[ch[x][0]] + 1 == k) return x;
        if(siz[ch[x][0]] + 1 < k) k -= siz[ch[x][0]] + 1, x = ch[x][1];//tag
        else x = ch[x][0];
    }
}
ull gethash(int l, int len) {
    int x = find(l), y = find(l + len + 1);
    splay(x, 0); splay(y, x); 
    return ha[ch[y][0]];
}
int lcp(int y, int x) {
    int l = 0, r = tot - max(x, y) - 1, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(gethash(x, mid) == gethash(y, mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    return ans;
}
void insert(int x, int v) {
    int l = find(x + 1), r = find(x + 2);
    splay(l, 0); splay(r, l);
    val[++tot] = v; fa[tot] = r; ch[r][0] = tot; splay(tot, 0); 
}
void change(int x, int v) {
    int l = find(x), r = find(x + 2);
    splay(l, 0); splay(r, l);
    val[ch[r][0]] = v; update(ch[r][0]); 
    update(r); update(l);
}
int main() {
//  freopen("a.in", "r", stdin);freopen("a.out", "w", stdout);
    po[0] = 1; 
    for(int i = 1; i <= (int)1e5; i++) po[i] = base * po[i - 1];
    scanf("%s", s + 1); n = strlen(s + 1);  
    ch[1][1] = 2; fa[2] = 1; tot = 2; root = 1; update(2); update(1); 
    for(int i = 1; i <= n; i++) 
        insert(i - 1, s[i]);
    int m = read();
    while(m--) {
        char opt[3]; scanf("%s", opt);
        if(opt[0] == 'q') {int x = read(), y = read(); printf("%d\n", lcp(x, y));}
        else if(opt[0] == 'r') {
            int x = read(); scanf("%s", opt + 1);
            change(x, opt[1]);
        } else {
            int x = read(); scanf("%s", opt + 1);
            insert(x, opt[1]); 
        }
    }
    return 0;
}
/*
*/