区间翻转:由于以root为根的树的中序遍历表示该区间,那么翻转只要递归的交换左右子树即可,加入lazy思想,降低时间复杂度。
Tips:做区间翻转的时候rev[rt]的含义是——以rt为根的子树所表示的区间是否将要被翻转,目前并没有执行翻转操作,如果改成先翻转,再标记,就会出现大问题。
Code:没用的push_down写多了。
/*http://acm.hdu.edu.cn/showproblem.php?pid=3487*/ /*splay区间切割+翻转*/ #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 333333; #define m_set(ptr,v,type,size) memset(ptr,v,sizeof(type)*size) #define loop(begin,end) for(int i=begin;i<end;i++) class SplayTree{ #define l(x) (ch[x][0]) #define r(x) (ch[x][1]) #define mid(x,y) ((x+y)>>1) public: int ch[MAXN][2],pre[MAXN]; int sz[MAXN],val[MAXN],rev[MAXN],a[MAXN]; int root,tot; void init(){ m_set(ch,0,int,MAXN*2); m_set(pre,0,int,MAXN); m_set(sz,0,int,MAXN); m_set(val,0,int,MAXN); m_set(rev,0,int,MAXN); root = tot = 0; } void read(int n){ a[1] = a[n+2] = 0; loop(2,n+2){ a[i] = i-1; } } void push_up(int rt){ sz[rt] = sz[l(rt)]+sz[r(rt)]+1; } void swap(int &x,int &y){ int tmp = x; x = y; y = tmp; } void push_down(int rt){ if(rt&&rev[rt]){ swap(l(rt),r(rt)); if(l(rt)) rev[l(rt)] ^= 1; if(r(rt)) rev[r(rt)] ^= 1; rev[rt] = 0; } } void rotate(int x,int f){ int y = pre[x]; push_down(x); push_down(y); ch[y][!f] = ch[x][f]; if(ch[y][!f]) pre[ch[y][!f]] = y; push_up(y); if(pre[y]) ch[pre[y]][r(pre[y])==y] = x; pre[x] = pre[y]; ch[x][f] = y; pre[y] = x; } void splay(int x,int goal){ push_down(x); while(pre[x]!=goal){ int y = pre[x], z = pre[pre[x]]; if(z==goal){ rotate(x,l(y)==x); }else{ int f = l(z)==y; if(ch[y][!f]==x){ rotate(y,f); rotate(x,f); }else{ rotate(x,!f); rotate(x,f); } } } push_up(x); if(goal==0) root = x; } void rotateTo(int k,int goal){ int x = root; while(1){ push_down(x); int tmp = sz[l(x)]+1; if(k==tmp) break; else if(k<tmp) x = l(x); else{ k -= tmp; x = r(x); } } splay(x,goal); } void buildTree(int l,int r,int &rt,int f){ if(l>r)return; int m = mid(l,r); rt = ++tot; val[rt] = a[m]; pre[rt] = f; buildTree(l,m-1,l(rt),rt); buildTree(m+1,r,r(rt),rt); push_up(rt); } void rangeCut(int l,int r,int goal){ rotateTo(l-1,0); rotateTo(r+1,root); push_down(r(root)); int x = l(r(root)); l(r(root)) = 0; pre[x] = 0; push_up(r(root)); push_up(root); rotateTo(goal,0); rotateTo(goal+1,root); push_down(r(root)); l(r(root)) = x; pre[x] = r(root); push_up(r(root)); push_up(root); } void rangeFlip(int l,int r){ rotateTo(l-1,0); rotateTo(r+1,root); push_down(r(root)); int x = l(r(root)); rev[x] ^= 1; } void dfs(int rt,int &size){ if(!rt) return; push_down(rt); dfs(l(rt),size); a[size++] = val[rt]; dfs(r(rt),size); } /////////////////debug/////////////////////// }spt; int main(){ int n,m; while(scanf("%d%d",&n,&m),!(n<0&&m<0)){ spt.init(); spt.read(n); spt.buildTree(1,n+2,spt.root,0); char op[5]; int a,b,c; while(m--){ scanf("%s%d%d",op,&a,&b); if(op[0]=='C'){ scanf("%d",&c); spt.rangeCut(a+1,b+1,c+1); }else{ spt.rangeFlip(a+1,b+1); } } n = 0; spt.dfs(spt.root,n); loop(1,n-1){ if(i!=1)printf(" "); printf("%d",spt.a[i]); } printf("\n"); } return 0; }
相关推荐
给定一个长度为N的序列,每个序列的长度是一个整数。要支持以下三种操作: ... 将[L,R]这个区间翻转,例如 1234变成 4321 求[L,R]区间的最大值 能力有限,实现可能有纰漏,也没有用到lazy_tag
Splay,平衡树的一种,支持部分区间操作。
Splay结构体的模板,含有各种旋转、插入、翻转等操作,注释清晰
SplayTree详细解释
Splay教学课件
splay经典代码,hdu1890,经典入门题,可作为模板
Splay基础教程 By Sqybi.自底向上型的
讲解Splay的经典论文 -------- Randomized Splay Trees: Theoretical and Experimental Results Susanne Albers Marek Karpinski
展树(Splay Tree)是一种二叉搜索树,它能在O(log n)内完成插入、查找和删除操作。它由Daniel Sleator和Robert Tarjan创造。它的优势在于不需要记录用于平衡树的冗余信息。在伸展树上的一般操作都基于伸展操作。
1、对于区间加的操作,只需要加上一个加标记,并且修改这个节点维护的区间 2、对于区间翻转操作,只需要加上一个翻转标记 3、对于区间插入操作,如果插入到 pos,
伸展树(Splay Tree),也叫分裂树,是一种二叉排序树,它能在O(log n)内完成插入、查找和删除操作。它由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明的。伸展树是一种自...
SplayTree优化版C源代码,带有完整的解释,其实就是置顶向下的Splay tree
splay 伸展树.ppt
splay和动态树的经典,是ACM选手了解动态树和Splay的重要资源。欢迎大家下载,并能熟练利用动态树和splay解题。
splay程序,希望大家可以看一下,适合新手
splay tree C# code 伸展树的C#代码实现 我看到没有C#实现版本,所以就把java代码转化成C#实现了一把
伸展树的主要特点:每次访问某个节点时,都把此节点旋转到根部。保证从空树开始任意M次操作最多花费O(MlogN)的时间,也就是说它的摊还时间为O(F(N))。 伸展数的主要难点:展开函数的实现。 ...
Splay模板包括旋转,主函数Splay,插入,删除,最大值,最小值,查询k大,查询排名
一个简单的 AVL树、splay树、以及二叉搜索树的代码实现 也可在我的github仓库中下载: https://github.com/yunwei37/myClassNotes
avl树,bst树(二叉查找树),rbt(红黑树),sbt(size平衡树),splay(伸展树),treap树。 3.代码以一个bst_base为基础,实现通用算法。将对象特征和存储结构通过模板参数向上传递,实现特化算法。最终各个不同...