POJ 3481 Double Queue Treap

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

题目链接： http://poj.org/problem?id=3481
对于每个节点有val和key
操作3种：
1.加入节点val和key
2.查找key最大的节点，输出val，并删除节点
3.查找key最小的节点，输出val，并删除节点

Treap模板题
按key值构造Treap，最大点递归查找左孩子，最小点递归查找右孩子

代码：

#include <algorithm>
#include <cstdio>
#include <iostream>
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 1000000 + 500,INF = 0x3f3f3f3f;
int ch[maxn][2],key[maxn],fix[maxn],fa[maxn],tot;
int val[maxn];
int root,sroot;
void Treap_Init(){root = sroot = 0;ch[sroot][0] = ch[sroot][1] = 0;fa[sroot] = sroot;key[sroot] = fix[sroot] = INF;tot = 1;
}
int NewNode(int FA,int k,int v){fa[tot] = FA;ch[tot][0] = ch[tot][1] = 0;key[tot] = k;val[tot] = v;fix[tot] = rand();return tot++;
}
void rotate(int rt,int kind){int prt = fa[rt];ch[prt][kind] = ch[rt][!kind];fa[ch[rt][!kind]] = prt;ch[fa[prt]][ ch[fa[prt]][1] == prt ] = rt;fa[rt] = fa[prt];ch[rt][!kind] = prt;fa[prt] = rt;
}
void Insert(int k,int v){int rt = root;while(ch[rt][k > key[rt]]) rt = ch[rt][k > key[rt]];ch[rt][k > key[rt]] = NewNode(rt,k,v);rt = ch[rt][k > key[rt]];while(fa[rt] != sroot && fix[rt] > fix[ fa[rt] ]){rotate(rt,ch[fa[rt]][1] == rt);}if(fa[rt] == sroot) root = rt;
}void Delete(int rt){if(ch[rt][0] && ch[rt][1]){int nrt = ch[rt][0];if(fix[nrt] < fix[ch[rt][1]]) nrt = ch[rt][1];rotate(nrt,ch[rt][1] == nrt);Delete(rt);}else{int nrt;if(ch[rt][0] != sroot) nrt = ch[rt][0];else nrt = ch[rt][1];ch[fa[rt]][ch[fa[rt]][1] == rt] = nrt;fa[nrt] = fa[rt];if(fa[nrt] == sroot) root = nrt;}
}int Find_Min(){int rt = root;while(ch[rt][0] != sroot) rt = ch[rt][0];return rt;
}
int Find_Max(){int rt = root;while(ch[rt][1] != sroot) rt = ch[rt][1];return rt;
}
int main(){int a,b,c;Treap_Init();while(~sf("%d",&a)){if(a == 0) break;else if(a == 1){sf("%d %d",&b,&c);Insert(c,b);}else if(a == 2){b = Find_Max();if(b == sroot) pf("0\n");else{pf("%d\n",val[b]);Delete(b);}}else{b = Find_Min();if(b == sroot) pf("0\n");else{pf("%d\n",val[b]);Delete(b);}}}
}

这篇关于POJ 3481 Double Queue Treap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---