首页 > 代码库 > POJ 1442 splay
POJ 1442 splay
前几天用treap写了这一题，不过treap支持的操作不如splay的多，作为一个完美主义者，重新用splay写了这一题。
splay大部分操作可以通过 强大到无与伦比的数据结构splay-tree 然后根据其中步骤写出来。
一定要注意的一点：几乎所有操作的背后，都要splay(x, 0)一下。
一开始我还以为只是一种打乱，或者是一种取巧的方法，但实际上这样做是为了将双旋的优势体现出来，能够保证当前节点的祖先能够之后查询的时候均摊为O（lgn）
此处需要格外注意。
若不加绝壁超时。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <map>#include <set>#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define INF 0x3f3f3f3f#define MAXN 100005using namespace std;int cnt=1, rt=0;struct Tree{ int key, size, fa, son[2]; void set(int _key, int _size, int _fa) { key=_key; size=_size; fa=_fa; son[0]=son[1]=0; }}T[MAXN];inline void PushUp(int x){ T[x].size=T[T[x].son[0]].size+T[T[x].son[1]].size+1;}inline void Rotate(int x, int p) //0左旋 1右旋{ int y=T[x].fa; T[y].son[!p]=T[x].son[p]; T[T[x].son[p]].fa=y; T[x].fa=T[y].fa; if(T[x].fa) T[T[x].fa].son[T[T[x].fa].son[1] == y]=x; T[x].son[p]=y; T[y].fa=x; PushUp(y); PushUp(x);}void Splay(int x, int To) //将x节点插入到To的子节点中{ while(T[x].fa != To) { if(T[T[x].fa].fa == To) Rotate(x, T[T[x].fa].son[0] == x); else { int y=T[x].fa, z=T[y].fa; int p=(T[z].son[0] == y); if(T[y].son[p] == x) Rotate(x, !p), Rotate(x, p); else Rotate(y, p), Rotate(x, p); } } if(To == 0) rt=x;}void Insert(int key){ if(rt == 0) T[rt = cnt++].set(key, 1, 0); else { int x=rt, y=0; while(x) { y=x; x=T[x].son[key > T[x].key]; } T[x = cnt++].set(key, 1, y); T[y].son[key > T[y].key]=x; Splay(x, 0); }}int GetPth(int p){ int x=rt, ret=0; while(x) { if(p == T[T[x].son[0]].size+1) break; if(p>T[T[x].son[0]].size+1) { p-=T[T[x].son[0]].size+1; x=T[x].son[1]; } else x=T[x].son[0]; } Splay(x, 0); return x;}int n,m,a[MAXN],u[MAXN],x,y,ans[MAXN];int main(){ scanf("%d%d", &n, &m); for(int i=0; i<n; i++) scanf("%d", &a[i]); for(int i=1; i<=m; i++) { scanf("%d", &u[i]); for(int j=u[i-1]; j<u[i]; j++) Insert(a[j]); printf("%d\n", T[GetPth(i)].key); } return 0;}
POJ 1442 splay
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。