首页 > 代码库 > HDU3487 Play With Chains(Splay)
HDU3487 Play With Chains(Splay)
很裸的Splay,抄一下CLJ的模板当作复习,debug了一个下午,收获是终于搞懂了以前看这个模板里不懂的内容。以前用这个模板的时候没有看懂为什么get函数返回的前缀要加个引用,经过一下午的debug终于明白,如果加了引用的时候是会被修改到的,删除实际上就是将root->ch[1]->ch[0]置为null,但由于我们还要把这一段插回去,所以get的时候的t前面没有加引用,否则一旦置为null的话 t也会变为null。还有就是这次是第一次用这个模板进行插入,本题倒腾了很久就是在这个插入上,没有找到合适的姿势。经过摸索一个正确的姿势是在 1 2 3 4 5 ... n 的第k个位置后插入,应该是先get(k+1,k+1),然后直接在root->ch[1]里设置左儿子即可。复习Splay是为了学习LCT做准备吧。。- -0
#pragma warning(disable:4996)#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <vector>#include <algorithm>#include <map>using namespace std;#define ll long long#define maxn 350000struct Node{ Node *ch[2], *p; int size,val; int rev; Node(){ size = 0; val = 0; rev = 0; } bool d(){ return this == p->ch[1]; } void setc(Node *c, int d){ ch[d] = c; c->p = this; } void relax(); void revIt() { rev ^= 1; } void upd(){ size = ch[0]->size + ch[1]->size + 1; }}Tnull,*null=&Tnull;Node mem[maxn], *C = mem;void Node::relax(){ if (rev){ swap(ch[0], ch[1]); for (int i = 0; i < 2; i++){ if (ch[i] != null) ch[i]->revIt(); } rev = 0; }}Node *make(int v){ C->ch[0] = C->ch[1] = null; C->size = 1; C->val = v; C->rev = 0; return C++;}Node* build(int l, int r){ if (l >= r) return null; int m = (l + r) >> 1; Node *t = make(m); t->setc(build(l, m), 0); t->setc(build(m + 1, r), 1); t->upd(); return t;}Node *root;void rot(Node *t){ Node *p = t->p; p->relax(); t->relax(); int d = t->d(); p->p->setc(t, p->d()); p->setc(t->ch[!d], d); t->setc(p, !d); p->upd(); if (p == root) root = t;}void splay(Node *t, Node *f = null){ while (t->p != f){ if (t->p->p == f) rot(t); else t->d() == t->p->d() ? (rot(t->p), rot(t)) : (rot(t), rot(t)); } t->upd();}Node* select(int k) { for (Node*t = root;;) { t->relax(); int c = t->ch[0]->size; if (k == c) return t; if (k > c) k -= c + 1, t = t->ch[1]; else t = t->ch[0]; }}Node*&get(int l, int r) { //[l,r) Node*L = select(l - 1); Node*R = select(r); splay(L); splay(R, L); return R->ch[0];}int n, m;int main(){ while (cin >> n >> m) { if (n <0 && m <0) break; memset(mem, 0, sizeof(mem)); C = mem; root = build(0, n + 2); root->p = null; char oper[10]; int li, ri, wi; for (int i = 0; i < m; i++){ scanf("%s", oper); if (oper[0] == ‘C‘){ scanf("%d%d%d", &li, &ri, &wi); Node *t = get(li, ri + 1); root->ch[1]->ch[0] = null; splay(root->ch[1]); Node *&x = get(wi+1, wi+1); root->ch[1]->setc(t, 0); } else{ scanf("%d%d", &li, &ri); Node *&t = get(li, ri + 1); t->revIt(); splay(t); } } for (int i = 1; i <= n; i++){ if (i >= 2) printf(" "); Node *&t = get(i, i + 1); printf("%d", t->val); } puts(""); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。