Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
第一次写红黑树,居然1Y了。。你敢信??//居然1Y了,,,我。。。 #include <iostream> #include <cstdio> #include <cstring> using namespace std; int m,n; int a[60000]; enum COLOR { red,black }; struct RedBlack { COLOR color; int l; int r; int p; int key; int cnt; }; RedBlack tree[60000]; int lt; int root; void RB_Init() { tree[0].color=black; tree[0].key=-1; root=1; tree[1].l=0; tree[1].r=0; tree[1].p=0; tree[1].cnt=0; tree[1].key=-1; } void RB_KeyC_Fixup(int x) { tree[x].cnt=tree[tree[x].l].cnt+tree[tree[x].r].cnt+1; } void RB_Left_Rotate(int x) { int y; y=tree[x].r; tree[x].r=tree[y].l; if (tree[y].l != 0) { tree[tree[y].l].p=x; } tree[y].p=tree[x].p; if (tree[x].p == 0) { root=y; } else if (tree[x].p != 0 && x == tree[tree[x].p].l) { tree[tree[x].p].l=y; } else if (tree[x].p != 0 && x != tree[tree[x].p].l) { tree[tree[x].p].r=y; } tree[y].l=x; tree[x].p=y; RB_KeyC_Fixup(x); RB_KeyC_Fixup(y); } void RB_Right_Rotate(int y) { int x; x=tree[y].l; tree[y].l=tree[x].r; if (tree[x].r != 0) { tree[tree[x].r].p=y; } tree[x].p=tree[y].p; if (tree[y].p == 0) { root=x; } else if (tree[y].p != 0 && y == tree[tree[y].p].l) { tree[tree[y].p].l=x; } else if (tree[y].p != 0 && y != tree[tree[y].p].l) { tree[tree[y].p].r=x; } tree[x].r=y; tree[y].p=x; RB_KeyC_Fixup(y); RB_KeyC_Fixup(x); } void RB_Insert_Fixup(int z) { int y; while (tree[tree[z].p].color == red) { if (tree[z].p == tree[tree[tree[z].p].p].l) { y=tree[tree[tree[z].p].p].r; if (tree[y].color == red) { tree[tree[z].p].color=black; tree[y].color=black; tree[tree[tree[z].p].p].color=red; z=tree[tree[z].p].p; } else if (tree[y].color != red && z == tree[tree[z].p].r) { z=tree[z].p; RB_Left_Rotate(z); } else if (tree[y].color != red && z == tree[tree[z].p].l) { tree[tree[z].p].color=black; tree[tree[tree[z].p].p].color=red; RB_Right_Rotate(tree[tree[z].p].p); } } else { y=tree[tree[tree[z].p].p].l; if (tree[y].color == red) { tree[tree[z].p].color=black; tree[y].color=black; tree[tree[tree[z].p].p].color=red; z=tree[tree[z].p].p; } else if (tree[y].color != red && z == tree[tree[z].p].l) { z=tree[z].p; RB_Right_Rotate(z); } else if (tree[y].color != red && z == tree[tree[z].p].r) { tree[tree[z].p].color=black; tree[tree[tree[z].p].p].color=red; RB_Left_Rotate(tree[tree[z].p].p); } } } tree[root].color=black; } void RB_Insert(int n) { int x,y; y=0; x=root; while (tree[x].key != -1) { y=x; tree[x].cnt++; if (n < tree[x].key) { x=tree[x].l; } else { x=tree[x].r; } } tree[lt].p=y; if (y == 0) { root=lt; } else if (y != 0 && n < tree[y].key) { tree[y].l=lt; } else if (y != 0 && n >= tree[y].key) { tree[y].r=lt; } tree[lt].l=0; tree[lt].r=0; tree[lt].color=red; tree[lt].key=n; tree[lt].cnt=1; RB_Insert_Fixup(lt); lt++; } int RB_Query(int k) { int x,y; x=root; while (k != 1 || tree[x].cnt != 1) { // printf("->%d %d\n",k,tree[x].key); if (k <= tree[tree[x].l].cnt && tree[x].l != 0) { x=tree[x].l; } else if (k == tree[tree[x].l].cnt+1) { return tree[x].key; } else if (k > tree[tree[x].l].cnt+1) { k-=tree[tree[x].l].cnt+1; x=tree[x].r; } //printf("->%d %d %d\n",k,tree[x].key,tree[x].cnt); } return tree[x].key; } void printTree(int x) { if (tree[x].l != 0) printTree(tree[x].l); printf("[%d %d]\n",tree[x].key,tree[x].cnt); if (tree[x].r!= 0) printTree(tree[x].r); } int main() { int i,j,pr,t,p; scanf("%d%d",&m,&n); for (i=1; i<=m; i++) { scanf("%d",a+i); } pr=1; p=1; lt=1; RB_Init(); while (n--) { scanf("%d",&t); for (i=pr; i<=t; i++) { // printf("i=%d\n",i); RB_Insert(a[i]); } // printTree(root); pr=t+1; printf("%d\n",RB_Query(p)); p++; } } Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator