首页 > 代码库 > _bzoj1014 [JSOI2008]火星人prefix【Splay】
_bzoj1014 [JSOI2008]火星人prefix【Splay】
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1014
天,写kth()时,把判断条件k <= siz[ch[x][0]]错写成了k <= ch[x][0],RE不停,还爆掉了几个小时,以后写数据结构题一定要头脑清晰啊!
#include <cstdio> #include <cstring> const int maxn = 300005, base = 131; int fa[maxn], ch[maxn][2], key[maxn], siz[maxn], root, cnt; unsigned long long hash[maxn], poww[maxn]; int n, m, t1, t2, stk[maxn], top; char s[maxn], opr, t3; inline void pushup(int x) { hash[x] = hash[ch[x][0]] * (poww[siz[ch[x][1]] + 1]) + key[x] * poww[siz[ch[x][1]]] + hash[ch[x][1]]; siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1; } inline void rotate(int x) { int y = fa[x]; if (y == ch[fa[y]][0]) { ch[fa[y]][0] = x; } else { ch[fa[y]][1] = x; } fa[x] = fa[y]; int dir = x == ch[y][1]; ch[y][dir] = ch[x][dir ^ 1]; fa[ch[x][dir ^ 1]] = y; ch[x][dir ^ 1] = y; fa[y] = x; pushup(y); pushup(x); } inline void splay(int x, int rt) { int p; while (fa[x] != rt) { p = fa[x]; if (fa[p] == rt) { rotate(x); } else { if ((p == ch[fa[p]][1]) ^ (x == ch[p][1])) { rotate(x); } else { rotate(p); } rotate(x); } } if (!rt) { root = x; } } int make_tree(int left, int right) { if (left > right) { return 0; } int rt = (left + right) >> 1; key[rt] = s[rt]; ch[rt][0] = make_tree(left, rt - 1); fa[ch[rt][0]] = rt; ch[rt][1] = make_tree(rt + 1, right); fa[ch[rt][1]] = rt; pushup(rt); return rt; } inline int kth(int k) { int x = root; while (k != siz[ch[x][0]] + 1) { if (k <= siz[ch[x][0]]) { x = ch[x][0]; } else { k -= siz[ch[x][0]] + 1; x = ch[x][1]; } } return x; } inline void modify(int root1, int root2) { root1 = kth(root1); root2 = kth(root2); splay(root1, 0); splay(root2, root1); } inline void ist(int pos, int _key) { modify(pos, pos + 1); ++cnt; hash[cnt] = key[cnt] = _key; siz[cnt] = 1; ch[ch[root][1]][0] = cnt; fa[cnt] = ch[root][1]; pushup(ch[root][1]); pushup(root); } /*void ist(int x, int k, int _key) { if (k == siz[ch[x][0]] + 1) { if (ch[x][1]) { top = 0; int i; for (i = ch[x][1]; ch[i][0]; i = ch[i][0]) { stk[top++] = i; } ++cnt; ch[i][0] = cnt; fa[cnt] = i; key[cnt] = _key; siz[cnt] = 1; pushup(i); for (i = top - 1; ~i; --i) { pushup(stk[i]); } } else { ++cnt; ch[x][1] = cnt; fa[cnt] = x; key[cnt] = _key; } pushup(x); splay(cnt, 0); return; } if (k <= siz[ch[x][0]]) { ist(ch[x][0], k, _key); } else { ist(ch[x][1], k - siz[ch[x][0]] - 1, _key); } }*/ void upd(int x, int k, int _key) { if (k == siz[ch[x][0]] + 1) { key[x] = _key; pushup(x); return; } if (k <= siz[ch[x][0]]) { upd(ch[x][0], k, _key); } else { upd(ch[x][1], k - siz[ch[x][0]] - 1, _key); } pushup(x); } unsigned long long gethash(int start, int end) { modify(start - 1, end + 1); return hash[ch[ch[root][1]][0]]; } int main(void) { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); scanf("%s", s + 2); n = strlen(s + 2); s[1] = s[n + 2] = ‘$‘; n += 2; cnt = n; poww[0] = 1; for (int i = 1; i < maxn; ++i) { poww[i] = poww[i - 1] * base; } root = make_tree(1, n); scanf("%d", &m); int left, right, mid; while (m--) { while ((opr = getchar()) < ‘A‘); scanf("%d", &t1); ++t1; if (opr == ‘I‘) { while ((t3 = getchar()) < ‘a‘); ist(t1, t3); ++n; } else if (opr == ‘R‘) { while ((t3 = getchar()) < ‘a‘); upd(root, t1, t3); } else { scanf("%d", &t2); ++t2; left = 0; right = n - (t1 > t2? t1: t2); while (left != right) { mid = (left + right + 1) >> 1; if (gethash(t1, t1 + mid - 1) == gethash(t2, t2 + mid - 1)) { left = mid; } else { right = mid - 1; } } printf("%d\n", left); } } return 0; }
_bzoj1014 [JSOI2008]火星人prefix【Splay】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。