@KirinBill
2017-09-18T16:59:07.000000Z
字数 2993
阅读 4154
学习笔记
数据结构
目录
严格说来,笛卡尔树不是一种平衡树,它没有后续的插入等操作,只有建树操作,因此建树后的功能操作通常用Treap实现,我们在此也只讨论建树的实现:
- 笛卡尔树的构造类似左偏树,只是它是“右偏的”;
- 我们先将节点按值升序排列,这样按顺序每次只向树的右侧插入即可;
- 但我们还要维护该树的堆性质(这里小根堆会方便些),所以我们考虑用一个栈维护树最右边的一条链;
- 我们先令节点入栈,即超级根,因为rand()
函数值域非负,所以构造小根堆就不需考虑将超级根的赋为了
以上操作贪心(每次找第一个满足要求的节点)的保证了笛卡尔树的两个性质。同时,每个节点只入栈出栈各1次,瓶颈只在排序,因此复杂度。
void build(int n,int val[],int key[]){
static stack<int> stk;
for(int i=1;i<=n;++i){
d[i].val=val[i];
d[i].key=key[i];
d[i].sz=1;
}
sort(d+1,d+n+1);
stk.push(0);
for(int i=1,fa;i<=n;++i){
while(fa=stk.top(),d[fa].key>d[i].key){
upd(fa);
stk.pop();
}
d[i].ls=d[fa].rs;
d[fa].rs=i;
stk.push(i);
}
while(stk.size()>1){
upd(stk.top());
stk.pop();
}
stk.pop();
rt=d[0].rs;
}
代码:
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <utility>
#include <climits>
#include <cctype>
#include <iostream>
#include <stack>
#define val first
#define key second
using std::sort;
using std::pair;
using std::ostream;
using std::cout;
using std::stack;
template<const int MAXN>
class string{
private:
int sz;
char c[MAXN];
public:
string(){};
string(char chr,int cnt){
for(int i=0;i<cnt;++i)
c[i]=chr;
sz=cnt;
}
string& operator+= (char chr){c[sz++]=chr;}
friend bool operator< (const string &a,const string &b){
return strcmp(a.c,b.c)<0;
}
friend ostream& operator<< (ostream &out,const string &a){
printf("%s",a.c);
return out;
}
};
typedef pair<string<20>,int> data;
const int MAXN=50005;
data tmp[MAXN];
struct node{
int ls,rs;
data w;
friend bool operator< (const node &a,const node &b){
return a.w<b.w;
}
};
class CartesianT{
private:
int rt;
node d[MAXN];
void inorder_prt(int u){
putchar('(');
if(d[u].ls) inorder_prt(d[u].ls);
cout<<d[u].w.val;
putchar('/');
printf("%d",d[u].w.key);
if(d[u].rs) inorder_prt(d[u].rs);
putchar(')');
}
public:
void clear(){memset(d,0,sizeof(d));}
void build(int n,data a[]){
static stack<int> stk;
for(int i=1;i<=n;++i)
d[i].w=a[i];
sort(d+1,d+n+1);
stk.push(0);
d[0].w=data(string<20>(CHAR_MAX,20),INT_MAX);
for(int i=1,fa;i<=n;++i){
while(fa=stk.top(),d[fa].w.key<d[i].w.key)
stk.pop();
d[i].ls=d[fa].rs;
d[fa].rs=i;
stk.push(i);
}
while(stk.size()) stk.pop();
rt=d[0].rs;
}
void inorder_prt(){inorder_prt(rt);}
}T;
int main(){
int n;
char c;
while(scanf("%d",&n),n){
T.clear();
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=n;++i){
do{c=getchar();}while(!islower(c));
while(islower(c)){
tmp[i].val+=c;
c=getchar();
}
scanf("%d",&tmp[i].key);
}
T.build(n,tmp);
T.inorder_prt();
putchar('\n');
}
return 0;
}
其实也是用于建树,单独拿出来说是因为用于这种Treap建树是一般性的而不是只用于刚刚说的特殊情况。因为非旋转式Treap的ist()
需要一次split()
和两次merge()
,常数略大,用笛卡尔树建树比较快。