Splay小结

2024-06-16 01:38
文章标签 小结 splay

本文主要是介绍Splay小结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Splay基本操作:

1.rotate() 旋转操作---包含三种情况

2.splay() 伸展-----一般是旋到根或根的父亲的下面

3.rotate_to() 先找到要伸展的结点，再splay;

4.push_up() 向上维护根的信息

5.push_down()向下下放延迟标记

6.Cut() 删除一个区间

7.insert()插入一个区间

8.Flip()翻转一个区间

9.pred()求结点的前驱

10.succ()求结点的后继

11.dfs()中序遍历---为了输出序列.

12.built()二分建树

13.New_Node()新建结点--如果多个函数要用到则写，否则不用！


poj3468--其它数据结构也可以实现！

//12344261		3468	Accepted	4468K	2907MS	C++	3222B	2013-12-01 11:37:06
#include <iostream>
#include<cstdio>
using namespace std;
#define MAX 100010
#define bint __int64
int N,Q,tot;
int A[MAX];
struct Node
{int size,vol,add;bint sum;Node*d[2];Node*pre;
}*Null,*root,space[MAX];
void updata(Node*p)
{p->size=p->d[0]->size+p->d[1]->size+1;p->sum=p->d[0]->sum+p->d[1]->sum+p->vol;
}
void Push_down(Node*x)
{if(x==Null) return;x->vol+=x->add;x->d[0]->add+=x->add;x->d[1]->add+=x->add;if(x->d[0]!=Null)x->d[0]->sum+=(bint)(x->add)*(x->d[0]->size);if(x->d[1]!=Null)x->d[1]->sum+=(bint)(x->add)*(x->d[1]->size);x->add=0;
}
void Rotate(Node*x,int c)
{Node*y=x->pre;Push_down(y),Push_down(x);y->d[!c]=x->d[c],x->pre=y->pre;if(x->d[c]!=Null) x->d[c]->pre=y;if(y->pre!=Null) y->pre->d[y->pre->d[1]==y]=x;y->pre=x,x->d[c]=y;if(root==y) root=x;updata(y);
}
void Splay(Node*x,Node*f)
{for(Push_down(x);x->pre!=f;){if(x->pre->pre==f)Rotate(x,x->pre->d[0]==x);else{Node *y=x->pre , *z=y->pre;if(z->d[0]==y)if(y->d[0]==x)Rotate(y,1),Rotate(x,1);elseRotate(x,0),Rotate(x,1);elseif(y->d[1]==x)Rotate(y,0),Rotate(x,0);elseRotate(x,1),Rotate(x,0);}}updata(x);
}
Node* New_Node(int x)
{Node*p=&space[tot++];p->d[0]=p->d[1]=p->pre=Null;p->add=0;p->size=1;p->sum=p->vol=x;return p;
}
Node* Make_Tree(int l,int r,Node* fa)
{if(l>r) return Null;int m=(l+r)>>1;Node*p=New_Node(A[m]);p->d[0]=Make_Tree(l,m-1,p);p->d[1]=Make_Tree(m+1,r,p);p->pre=fa;updata(p);return p;
}
void init()
{tot=0;Null=New_Node(0);Null->size=0;root=New_Node(-1);root->d[1]=New_Node(-1);root->d[1]->pre=root;updata(root);root->d[1]->d[0]=Make_Tree(1,N,root->d[1]);
}
void Select(int k,Node*f)
{Node*p=root;while(true){Push_down(p);int tem=p->d[0]->size;if(k==tem+1) break;if(k <= tem)p=p->d[0];elsep=p->d[1],k-=tem+1;}Splay(p,f);
}
int main()
{while(~scanf("%d%d",&N,&Q)){for(int i=1;i<=N;i++)scanf("%d",&A[i]);init();char op[2];for(int i=1;i<=Q;i++){scanf("%s",op);if(op[0]=='C'){int a,b,c;scanf("%d%d%d",&a,&b,&c);Select(a,Null);Select(b+2,root);root->d[1]->d[0]->add+=c;root->d[1]->d[0]->sum+=(bint)c*(root->d[1]->d[0]->size);}else{int a,b;scanf("%d%d",&a,&b);Select(a,Null);Select(b+2,root);printf("%I64d\n",root->d[1]->d[0]->sum);}}}return 0;
}


hdu4441---指定位置插入（最好用splay）

//9740664	2013-12-02 22:21:47	Accepted	4441	1140MS	9464K	3860 B	G++	
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<iostream>
using namespace std;
#define Stype(x) (ns[ns[x].f].son[1]==x)
typedef __int64 ll;
const int N = 100005;
int m;int posn[N],posp[N];
struct Splay
{int nns,begin,end;struct node{int size,key,f,son[2]; ll sum; bool p;}ns[2*N];inline int operator[](int x){return ns[x].key;}inline int NewNode(int x,int f){ns[++nns].key=ns[nns].sum=x;ns[nns].size=1;ns[nns].f=f;ns[nns].p=x>0;return nns;}inline void init(){nns=0;memset(ns,0,sizeof(ns));begin=ns[0].son[0]=NewNode(0,0);end=ns[1].son[1]=NewNode(0,1);Updata(1);}inline void Updata(int x){ns[x].sum=ns[ns[x].son[0]].sum+ns[ns[x].son[1]].sum+ns[x].key;ns[x].size=ns[ns[x].son[0]].size+ns[ns[x].son[1]].size+1;ns[x].p=ns[x].key>0 || ns[ns[x].son[0]].p || ns[ns[x].son[1]].p;}int pred(int x){splay(x);for(x=ns[x].son[0];ns[x].son[1];x=ns[x].son[1]);splay(x);return x;}int succ(int x){splay(x);for(x=ns[x].son[1];ns[x].son[0];x=ns[x].son[0]);splay(x);return x;}int ins(int x,int s){//cout<<"asdasda\n";int p=pred(s);splay(p),splay(s,p);x=ns[s].son[0]=NewNode(x,s);Updata(s),Updata(p);splay(x);return x;}int kth(int k){int x=ns[0].son[0],ls;while(true){ls=ns[ns[x].son[0]].size;if(ls+1==k) {splay(x);return x;}if(ls < k)x=ns[x].son[1],k-=ls+1;elsex=ns[x].son[0];}}int F(int x){splay(x);x=ns[x].son[1];if(!ns[x].p) return 0;while(true){if(ns[ns[x].son[0]].p)  x=ns[x].son[0];else if(ns[x].key > 0) {splay(x);return x;}else                    x=ns[x].son[1];}}void rot(int x){int ST=Stype(x),f=ns[x].f;ns[ns[f].f].son[Stype(f)]=x;ns[x].f=ns[f].f;ns[f].son[ST]=ns[x].son[!ST];if(ns[x].son[!ST]) ns[ns[x].son[!ST]].f=f;ns[f].f=x;ns[x].son[!ST]=f;Updata(f);}void splay(int x,int to=0){while(ns[x].f!=to)if(ns[ns[x].f].f!=to){if(Stype(x)==Stype(ns[x].f))rot(ns[x].f),rot(x);elserot(x),rot(x);}else rot(x);Updata(x);}void Del(int x){int s=succ(x),p=pred(x);splay(p),splay(s,p);ns[s].son[0]=0;Updata(s),Updata(p);}ll S(int l,int r){splay(l),splay(r,l);return ns[ns[r].son[0]].sum;}
}T;
void run()
{priority_queue< int, vector<int>, greater<int> > H;for(int i=1;i<=m;i++) H.push(i);T.init();char ch[8];int x,w,w2,key;for(int i=1;i<=m;i++){scanf("%s%d",ch,&x);if(ch[0]=='i'){key=H.top();H.pop();posp[key]=w=T.ins(key,T.kth(x+2));w2=T.F(w);if(w2)posn[key]=T.ins(-key,posn[T[w2]]);elseposn[key]=T.ins(-key,T.end);}else if(ch[0]=='r'){T.Del(posn[x]); T.Del(posp[x]);H.push(x);}elseprintf("%I64d\n", T.S(posp[x], posn[x]));}
}
int main()
{int t=0;while(~scanf("%d",&m)){printf("Case #%d:\n", ++t);run();}return 0;
}


hdu3487--区间翻转，切割

#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) (nod[x].son[0])#define r(x) (nod[x].son[1])#define Juge(x) (nod[pre[x]].son[1]==x)#define mid(x,y) ((x+y)>>1)
public:int a[MAXN],pre[MAXN];struct node{int val,rev,sz,son[2];}nod[MAXN];int root,tot;void init(){memset(nod,0,sizeof(nod));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){nod[rt].sz=nod[l(rt)].sz+nod[r(rt)].sz+1;}void swap(int &x,int &y){int tmp = x;x = y;y = tmp;}void push_down(int rt){if(nod[rt].rev){swap(l(rt),r(rt));if(l(rt)) nod[l(rt)].rev ^= 1;//采用异或 ^=if(r(rt)) nod[r(rt)].rev ^= 1;nod[rt].rev = 0;}}void rotate(int x,int f){/**分三步旋转**//**第一步：把x和y的儿子连好**/int y = pre[x];nod[y].son[!f]=nod[x].son[f];if(nod[y].son[!f]) pre[nod[y].son[!f]] = y;push_up(y);/**第二步：把x的父亲连好**/if(pre[y]) nod[pre[y]].son[r(pre[y])==y]=x;pre[x] = pre[y];/**第三步：把y的父亲连好**/nod[x].son[f] = y;pre[y] = x;}void splay(int x,int goal){/**分三种情形的旋转!**/while(pre[x]!=goal){int y = pre[x], z = pre[pre[x]];if(z==goal){rotate(x,!Juge(x));}else{if(Juge(y)){if(Juge(x)) rotate(y,0),rotate(x,0);else        rotate(x,1),rotate(x,0);}else{if(!Juge(x)) rotate(y,1),rotate(x,1);else         rotate(x,0),rotate(x,1);}}}push_up(x);/**最后在更新x的信息,没必要在rotate里面去更新,它里面只需更新改动的父亲结点信息!**/if(goal==0) root = x;/**要记得维护一下 root的信息!**/}void rotateTo(int k,int goal){/**先找到第k个位置,然后splay到goal！**/int x = root;while(1){push_down(x);int tmp = nod[l(x)].sz+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;nod[rt].val=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);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);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);int x = l(r(root));nod[x].rev^=1;/**延迟标记**/}void dfs(int rt,int &size){if(!rt) return;push_down(rt);/**遍历使要下放延迟标记，才能得到正确结果!**/dfs(l(rt),size);a[size++] = nod[rt].val;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;
}


hdu4286--双向链表实现的区间翻转\

TLE  普通的翻转，即每翻转一次就把区间里所有节点都翻转过来！


#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 500010
struct Node
{int pred,last,vol;
}a[maxn];
int l,r,tot,size;
void reverse()
{for(int i=a[l].last;i!=r;i=a[i].pred) swap(a[i].pred,a[i].last);a[a[l].last].last=r;a[a[r].pred].pred=l;swap(a[l].last,a[r].pred);
}
void Del(char ch)
{size--;if(ch=='L'){a[a[a[l].last].last].pred=l;a[l].last=a[a[l].last].last;}else{a[a[a[r].pred].pred].last=r;a[r].pred=a[a[r].pred].pred;}
}
void init(int n)
{tot=0;size=0;l=0;r=n+1;a[l].pred=-1;a[l].last=r;a[r].pred=l;a[r].last=-1;
}
void Insert(char ch,int vol)
{a[++tot].vol=vol;size++;if(ch=='L'){a[tot].pred=l;a[tot].last=a[l].last;a[a[l].last].pred=tot;a[l].last=tot;}else{a[tot].last=r;a[tot].pred=a[r].pred;a[a[r].pred].last=tot;a[r].pred=tot;}
}
void left(char ch)
{if(ch=='L') l=a[l].pred;else        r=a[r].pred;
}
void right(char ch)
{if(ch=='L') l=a[l].last;else        r=a[r].last;
}
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);init(n);for(int i=1;i<=n;i++){scanf("%d",&a[++tot].vol);a[tot].pred=l;a[tot].last=a[l].last;a[l].last=tot;a[a[tot].last].pred=tot;l=tot;size++;}scanf("%d%d",&l,&r);l--;r++;int m;scanf("%d",&m);while(m--){char op[10];scanf("%s",op);if(op[0]=='R') {reverse(); continue;}else if(op[0]=='D') {scanf(" %c",&op[0]);Del(op[0]);}else if(op[0]=='I') {int d;scanf(" %c%d",&op[0],&d);Insert(op[0],d);}else{char ch;scanf(" %c",&ch);if(strcmp(op,"MoveLeft")==0)  left(ch);else                        right(ch);}}for(int i=1,k=0;i<=size;i++){k=a[k].last;if(i==1)    printf("%d",a[k].vol);else        printf(" %d",a[k].vol);}printf("\n");}return 0;
}


只要 在L 的前面设一个 LL 在R后面设一个 RR就可以避免上述的没翻转一次全部结点翻转了！

这样的话，LL就相当于是给 L 一个方向感！ RR也是一样的，只不过它代表R的后.

/*
HDU
G++  4015ms  11968K
双向链表模拟
注意细节
*/#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<algorithm>
using namespace std;
const int MAXN=2000000;
struct Node
{int from;int to;int val;
}node[MAXN];
int tol;int L,R;//两个指针
int LL,RR;//分别是指针L，R的左侧和右侧，由于倒一下可能改变方向，所以记录下方向
int n;void moveleft_L(void)//左移L指针
{if(L==0)return;//最左侧了if(node[L].to==LL){LL=L;L=node[L].from;}else{LL=L;L=node[L].to;}
}void moveleft_R()
{if(RR==0)return;if(node[RR].to==R){R=RR;RR=node[RR].from;}else{R=RR;RR=node[RR].to;}
}
void moveright_L()
{if(LL==n+1)return;if(L==node[LL].from){L=LL;LL=node[LL].to;}else{L=LL;LL=node[LL].from;}
}void moveright_R()
{if(R==n+1)return;if(node[R].from==RR){RR=R;R=node[R].to;}else{RR=R;R=node[R].from;}
}void insert_L(int v)
{node[tol].val=v;node[tol].from=L;node[tol].to=LL;if(node[L].to==LL)node[L].to=tol;else node[L].from=tol;if(node[LL].from==L)node[LL].from=tol;else node[LL].to=tol;LL=tol;tol++;
}
void insert_R(int v)
{node[tol].val=v;node[tol].from=RR;node[tol].to=R;if(node[RR].to==R)node[RR].to=tol;else node[RR].from=tol;if(node[R].from==RR)node[R].from=tol;else node[R].to=tol;RR=tol;tol++;
}void del_L()
{if(LL==n+1)return;if(L==n+1)return;int t;if(node[LL].from==L)t=node[LL].to;else t=node[LL].from;if(node[t].from==LL)node[t].from=L;else node[t].to=L;if(node[L].to==LL)node[L].to=t;else node[L].from=t;LL=t;
}void del_R()
{if(RR==0)return;if(R==0)return;int t;if(node[RR].to==R)t=node[RR].from;else t=node[RR].to;if(node[t].from==RR)node[t].from=R;else node[t].to=R;if(node[R].from==RR)node[R].from=t;else node[R].to=t;RR=t;
}void reverse()
{if(node[L].to==LL)node[L].to=RR;else node[L].from=RR;if(node[LL].from==L)node[LL].from=R;else node[LL].to=R;if(node[R].from==RR)node[R].from=LL;else node[R].to=LL;if(node[RR].to==R)node[RR].to=L;else node[RR].from=L;int temp;temp=LL;LL=RR;RR=temp;
}void output()
{int flag=true;int tt=0;for(int i=node[0].to;i!=n+1;){if(flag)flag=false;else printf(" ");printf("%d",node[i].val);if(node[i].from==tt){tt=i;i=node[i].to;}else{tt=i;i=node[i].from;}}printf("\n");
}char str[20];
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int T;int m;scanf("%d",&T);while(T--){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&node[i].val);node[i].from=i-1;node[i].to=i+1;}node[0].to=1;node[0].from=-1;node[n+1].from=n;node[n+1].to=-1;tol=n+2;//结点数scanf("%d%d",&LL,&RR);L=LL-1;R=RR+1;scanf("%d",&m);while(m--){scanf("%s",&str);if(strcmp(str,"MoveLeft")==0){scanf("%s",&str);if(str[0]=='L')moveleft_L();else moveleft_R();}else if(strcmp(str,"MoveRight")==0){scanf("%s",&str);if(str[0]=='L')moveright_L();else moveright_R();}else if(strcmp(str,"Delete")==0){scanf("%s",&str);if(str[0]=='L')del_L();else del_R();}else if(strcmp(str,"Insert")==0){scanf("%s",&str);if(str[0]=='L'){int v;scanf("%d",&v);insert_L(v);}else{int v;scanf("%d",&v);insert_R(v);}}else reverse();}output();}
}





这篇关于Splay小结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1065161。

相关文章

Java调用Python代码的几种方法小结

Java调用Python代码的几种方法小结

《Java调用Python代码的几种方法小结》Python语言有丰富的系统管理、数据处理、统计类软件包,因此从java应用中调用Python代码的需求很常见、实用,本文介绍几种方法从java调用Pyt... 目录引言Java core使用ProcessBuilder使用Java脚本引擎总结引言python
阅读更多...
Node.js 中 http 模块的深度剖析与实战应用小结

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器：基石搭建（一
阅读更多...
Redis的Hash类型及相关命令小结

Redis的Hash类型及相关命令小结

《Redis的Hash类型及相关命令小结》edisHash是一种数据结构,用于存储字段和值的映射关系,本文就来介绍一下Redis的Hash类型及相关命令小结,具有一定的参考价值,感兴趣的可以了解一下... 目录HSETHGETHEXISTSHDELHKEYSHVALSHGETALLHMGETHLENHSET
阅读更多...
python中cv2.imdecode()与cv2.imencode()的使用小结

python中cv2.imdecode()与cv2.imencode()的使用小结

《python中cv2.imdecode()与cv2.imencode()的使用小结》本文介绍了cv2.imencode()和cv2.imdecode()函数的使用,文中通过示例代码介绍的非常详细,对... 目录1、图片路径带中文的读取和写入1.1 读取1.2 写入2、在网络中传输图片cv2.imencod
阅读更多...
Java将时间戳转换为Date对象的方法小结

Java将时间戳转换为Date对象的方法小结

《Java将时间戳转换为Date对象的方法小结》在Java编程中,处理日期和时间是一个常见需求,特别是在处理网络通信或者数据库操作时,本文主要为大家整理了Java中将时间戳转换为Date对象的方法... 目录1. 理解时间戳2. Date 类的构造函数3. 转换示例4. 处理可能的异常5. 考虑时区问题6.
阅读更多...
分布式系统的个人理解小结

分布式系统的个人理解小结

分布式系统：分的微小服务，以小而独立的业务为单位，形成子系统。 然后分布式系统中需要有统一的调用，形成大的聚合服务。 同时，微服务群，需要有交流（通讯，注册中心，同步，异步），有管理（监控，调度）。 对外服务，需要有控制的对外开发，安全网关。
阅读更多...
Linux环境配置中问题小结

Linux环境配置中问题小结

在Linux环境配置中，遇到问题首先猜测： 1、是否是权限问题； 2、软连接是否配置；
阅读更多...
long long,_int64使用小结

long long,_int64使用小结

前言： 　　在16位环境下，int/unsigned int 占16位，long/unsigned long占32位 　　在32位环境下，int占32位，unsigned int占16位，long/unsigned long占32位 何时需要使用： 　　long 和 int 范围是[-2^31,2^31)，即-2147483648~2147483647，而unsigned范围是[0,2^32)，
阅读更多...
密码学读书笔记小结

密码学读书笔记小结

密码学是保证消息的私密性和完整性以及消息认证的基础。加密算法的选择和密钥的管理是安全机制的效率、性能和可用性的关键。 公钥加密算法： 分发密钥比较容易，但是对大数据量的加密性能较差密钥加密算法： 更适合大批的加密任务混合型加密协议： 例如TLS，先用公钥加密建立一个安全通道，然后使用通道交换密钥，并将此密钥用于后续数据交换。 对分布式系统攻击的分类： 窃听： 未经授权获得消息副本伪装： 在未
阅读更多...
Android 源码中jni项目 加载so目录小结

Android 源码中jni项目 加载so目录小结

Android 源码中jni项目 加载so目录小结 文章目录 Android 源码中jni项目 加载so目录小结一、前言二、so目录验证测试1、jni so文件错误报错（1）报错1 - 未找到so文件：（2）报错2 - so文件中未找到native方法： 2、验证的几种情况（1）apk下面的 lib/arm64/ 放置正确的so文件（2）apk下面的 lib/arm64/ 放置错误的so文
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2