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; } /* */
上一篇: css精灵图&字体图标