1.感觉之前邵叔叔教的做fib的那个支持删除(其实删除只是打标记,而且不支持插入。。。)和查询的排序二叉树就是个静态的名次树嘛。我居然学到了这么奇怪的数据结构。。。
2.写的时候坑了几次
(1)不要乱用引用,getKth里那个参数o没过脑子用了引用,结果把树搞烂了,一堆ch[x]赋值成NULL了。
(2)写查找的时候lchsize<k一开始把不等号写反了。。。泪目
(3)重载小于号玩脱了。坑了好久。用小于号以前没对指针解除引用。那个if总是进去,每次都左旋,然后基本搞成一条链。果然我语言没学好吗。
POJ1442http://poj.org/problem?id=1442
Code #include <iostream> #include <cstdio> #include <cstdlib> #include <ctime> using namespace std; struct Node { Node *ch[2]; int r,v,s; Node(int v):v(v) {s=1;ch[0]=ch[1]=NULL;r=rand();} int cmp(int x) const{ if(x==v)return(-1); return (x<v)?(0):(1); } void maintain(){ s=1; if(ch[0]!=NULL)s+=ch[0]->s; if(ch[1]!=NULL)s+=ch[1]->s; } }; void rotate(Node* &o,int d) { Node* k=o->ch[d^1]; o->ch[d^1]=k->ch[d]; k->ch[d]=o; o->maintain(); k->maintain(); o=k; } void insert(Node* &o,int x) { if(o==NULL) o=new Node(x); else { int d=(x<o->v)?0:1; insert(o->ch[d],x); if((o->r)<(o->ch[d]->r)) rotate(o,d^1); } o->maintain(); } void remove(Node* &o,int x) { int d=o->cmp(x); if(d==-1){ Node* u=o; if(o->ch[0]==NULL){o=o->ch[1];delete u;}else if(o->ch[1]==NULL){o=o->ch[0];delete u;}else { int c=(o->ch[0])>(o->ch[1])?(1):(0); rotate(o,c); remove(o->ch[c],x); } } else remove(o->ch[d],x); if(o!=NULL) o->maintain(); } int find(Node* &o,int x) { while(o!=NULL){ int d=o->cmp(x); if(d==-1) return 1; else o=o->ch[d]; } return 0; } int getKth(Node* o,int k) { while(o!=NULL){ int lchsize=(o->ch[0]!=NULL)? (o->ch[0]->s):0; if(lchsize+1==k) return o->v; else { int d=(lchsize<k); o=o->ch[d]; k-=d*(lchsize+1); } } return 0; } void print(Node* o,int h) { if(o->ch[0]!=NULL){ printf("( "); print(o->ch[0],h+1); printf(" )"); } printf("{%d}[%d]",o->v,h); if(o->ch[1]!=NULL){ printf("( "); print(o->ch[1],h+1); printf(" )"); } } const int M=30000; int m,n,p=0,ans,A[M+1],u; Node* root=NULL; int main() { srand(time(0)); scanf("%d%d",&m,&n); for(int i=0;i<m;i++) scanf("%d",A+i); for(int i=0;i<n;i++){ scanf("%d",&u); while(p<u) insert(root,A[p++]); ans=getKth(root,i+1); printf("%d\n",ans); } return 0; }
void clear(Node* &o) { if(o->ch[0]!=NULL) clear(o->ch[0]); if(o->ch[1]!=NULL) clear(o->ch[1]); delete o; o=NULL; }