POJ1442(Treap板子记录)

【题意】给一个序列&＃xff0c;然后给出m个查询&＃xff0c;每次查询输入一个数x&＃xff0c;对于第i次查询&＃xff0c;输出前x个数中第i大的关键字的值。

【解题方法】就是裸Treap板子了&＃xff0c;先介绍一下Treap。

Treap是一棵二叉搜索树&＃xff0c;只是每个节点多了一个优先级fix&＃xff0c;对于每个节点&＃xff0c;该节点的优先级小于等于其所有孩子的优先级。

当然&＃xff0c;引入优先级fix的目的就是防止BST退化成一条链&＃xff0c;从而影响查找效率。

所以&＃xff0c;这样看来就是&＃xff1a;Treap中对于节点的关键字key来说&＃xff0c;它是一棵二叉搜索树&＃xff0c;而对于fix来说&＃xff0c;它是一个最小堆&＃xff0c;所以

Treap可以看成是Tree&＃43;Heap&＃xff0c;只是这里的Heap不一定是完全二叉树。Treap的平均时间复杂度为log(n).

Treap跟笛卡尔树几乎是一模一样的&＃xff0c;只是用途不同。

笛卡尔树是把已有的一些&＃xff08;key, fix&＃xff09;二元组拿来构造树&＃xff0c;然后利用构树过程和构造好的树来解决LCA,RMQ等等问题。而

Treap的目的只是对一些key进行二叉搜索&＃xff0c;但是为了保证树的平衡性&＃xff0c;为每个key随机地额外增加了一个fix属性&＃xff0c;这样从概

率上来讲可以让这棵树更加平衡。

对于Treap来说&＃xff0c;主要有几大操作&＃xff1a;插入&＃xff0c;删除&＃xff0c;查找&＃xff0c;旋转&＃xff0c;找第K大元素&＃xff0c;找关键字x的排名&＃xff0c;计算Treap的高度&＃xff0c;删除

Treap&＃xff0c;其它的操作比如合并&＃xff0c;分离&＃xff0c;反转等等以后再说&＃xff0c;另外&＃xff0c;对于Treap来说&＃xff0c;它的中序遍历的结果就是按照关键字从小到

大的顺序排列的。

#include
#include
#include
#include
using namespace std;struct Treap
{int size;int key,fix;Treap *ch[2];Treap(int key){size&＃61;1;fix&＃61;rand();this->key&＃61;key;ch[0]&＃61;ch[1]&＃61;NULL;}int compare(int x) const{if(x&＃61;&＃61;key) return -1;return xsize;if(ch[1]!&＃61;NULL) size&＃43;&＃61;ch[1]->size;}
};void Rotate(Treap* &t,int d)
{Treap *k&＃61;t->ch[d^1];t->ch[d^1]&＃61;k->ch[d];k->ch[d]&＃61;t;t->Maintain(); //必须先维护t&＃xff0c;再维护k&＃xff0c;因为此时t是k的子节点k->Maintain();t&＃61;k;
}void Insert(Treap* &t,int x)
{if(t&＃61;&＃61;NULL) t&＃61;new Treap(x);else{//int d&＃61;t->compare(x); //如果值相等的元素只插入一个int d&＃61;x key ? 0:1; //如果值相等的元素都插入Insert(t->ch[d],x);if(t->ch[d]->fix > t->fix)Rotate(t,d^1);}t->Maintain();
}//一般来说&＃xff0c;在调用删除函数之前要先用Find()函数判断该元素是否存在
void Delete(Treap* &t,int x)
{int d&＃61;t->compare(x);if(d&＃61;&＃61;-1){Treap *tmp&＃61;t;if(t->ch[0]&＃61;&＃61;NULL){t&＃61;t->ch[1];delete tmp;tmp&＃61;NULL;}else if(t->ch[1]&＃61;&＃61;NULL){t&＃61;t->ch[0];delete tmp;tmp&＃61;NULL;}else{int k&＃61;t->ch[0]->fix > t->ch[1]->fix ? 1:0;Rotate(t,k);Delete(t->ch[k],x);}}else Delete(t->ch[d],x);if(t!&＃61;NULL) t->Maintain();
}bool Find(Treap *t,int x)
{while(t!&＃61;NULL){int d&＃61;t->compare(x);if(d&＃61;&＃61;-1) return true;t&＃61;t->ch[d];}return false;
}int Kth(Treap *t,int k)
{if(t&＃61;&＃61;NULL||k<&＃61;0||k>t->size)return -1;if(t->ch[0]&＃61;&＃61;NULL&&k&＃61;&＃61;1)return t->key;if(t->ch[0]&＃61;&＃61;NULL)return Kth(t->ch[1],k-1);if(t->ch[0]->size>&＃61;k)return Kth(t->ch[0],k);if(t->ch[0]->size&＃43;1&＃61;&＃61;k)return t->key;return Kth(t->ch[1],k-1-t->ch[0]->size);
}int Rank(Treap *t,int x)
{int r;if(t->ch[0]&＃61;&＃61;NULL) r&＃61;0;else r&＃61;t->ch[0]->size;if(x&＃61;&＃61;t->key) return r&＃43;1;if(xkey)return Rank(t->ch[0],x);return r&＃43;1&＃43;Rank(t->ch[1],x);
}void DeleteTreap(Treap* &t)
{if(t&＃61;&＃61;NULL) return;if(t->ch[0]!&＃61;NULL) DeleteTreap(t->ch[0]);if(t->ch[1]!&＃61;NULL) DeleteTreap(t->ch[1]);delete t;t&＃61;NULL;
}void Print(Treap *t)
{if(t&＃61;&＃61;NULL) return;Print(t->ch[0]);cout<key<ch[1]);
}
int val[1000010];
int main()
{int n,m,x;while(scanf("%d%d",&n,&m)!&＃61;EOF){for(int i&＃61;1; i<&＃61;n; i&＃43;&＃43;) scanf("%d",&val[i]);int index&＃61;1;Treap *root&＃61;NULL;for(int i&＃61;1; i<&＃61;m; i&＃43;&＃43;){scanf("%d",&x);for(int j&＃61;index; j<&＃61;x; j&＃43;&＃43;){Insert(root,val[j]);}index&＃61;x&＃43;1;printf("%d\n",Kth(root,i));}DeleteTreap(root);}
}