红黑树.cpp

一些比较难找的算法代码 中国剩余定理.cpp 高斯消元.cpp 红黑树.cpp 排序后第k位置数.cpp 修正单纯形.c

# include <iostream.h>
//# include <stdio.h>
//# include <time.h>
int a[2005],root,key[2005],size[2005],left[2005],right[2005];
int p[2005],color[2005];
int select(int x,int i)
{
        int r = size[left[x]]+1;
        if(i==r) return x;
        else if(i<r) return select(left[x],i);
        else return select(right[x],i-r);
}
int left_rotate(int x)
{
        int y=right[x];
        right[x]=left[y];
        if(left[y]) p[left[y]]=x;
        p[y]=p[x];
        if(p[x]==0) root=y;
        else if(x==left[p[x]]) left[p[x]]=y;
        else right[p[x]]=y;
        left[y]=x;
        p[x]=y;
        //augment
        size[y]=size[x];
        size[x]=size[left[x]]+size[right[x]]+1;
        size[0]=0;
        return 0;
}
int right_rotate(int x)
{
        int y=left[x];
        left[x]=right[y];
        if(right[y]) p[right[y]]=x;
        p[y]=p[x];
        if(p[x]==0) root=y;
        else if(x==right[p[x]]) right[p[x]]=y;
        else left[p[x]]=y;
        right[y]=x;
        p[x]=y;
        //augment
        size[y]=size[x];
        size[x]=size[left[x]]+size[right[x]]+1;
        size[0]=0;
        return 0;
}
int insert_fixup(int z)
{
        int y;
        while(color[p[z]]==0){
                if(p[z]==left[p[p[z]]]){//three cases;
                        y=right[p[p[z]]];
                        if(color[y]==0) { //case 1: uncle is red;
                                color[p[z]]=1;
                                color[y]=1;
                                color[p[p[z]]]=0;
                                z=p[p[z]];
                        }
                        else{//case 2 and 3: uncle is black;
                                if(z==right[p[z]]){ //case 2: z is right son;
                                        z=p[z];
                                        left_rotate(z);
                                }
                                color[p[z]]=1;
                                color[p[p[z]]]=0;
                                right_rotate(p[p[z]]);
                        }
                }
                else{// another three cases;
                        y=left[p[p[z]]];
                        if(color[y]==0) { //case 1: uncle is red;
                                color[p[z]]=1;
                                color[y]=1;
                                color[p[p[z]]]=0;
                                z=p[p[z]];
                        }
                        else{//case 2 and 3: uncle is black;
                                if(z==left[p[z]]){ //case 2: z is right son;
                                        z=p[z];
                                        right_rotate(z);
                                }
                                color[p[z]]=1;
                                color[p[p[z]]]=0;
                                left_rotate(p[p[z]]);
                        }
                }
        }
        color[root]=1;
        return 0;
}
int tree_insert(int z)
{
        int y=0;
        int x=root;
        while(x!=0){
                size[x]++;
                y=x;
                if(key[z]<key[x]) x=left[x];
                else x=right[x];
        } 
        p[z]=y;
        if(y==0) root=z;
        else if(key[z]<key[y]) left[y]=z;
        else right[y]=z;
        size[z]=1;
        left[z]=0;
        right[z]=0;
        color[z]=0;
        if(z==0) size[z]=0;
        insert_fixup(z);
        return 0;
}
int delete_fixup(int x)
{
        int w;
        while(x!=root&&color[x]==1){
                if(x==left[p[x]]){
                        w=right[p[x]];
                        if(color[w]==0){
                                color[w]=1;
                                color[p[x]]=0;
                                left_rotate(p[x]);
                                w=right[p[x]];
                        }
                        if(color[left[w]]==1&&color[right[w]]==1){
                                color[w]=0;
                                x=p[x];
                        }
                        else {
                                if(color[right[w]]==1){
                                        color[left[w]]=1;
                                        color[w]=0;
                                        right_rotate(w);
                                        w=right[p[x]];
                                }
                                color[w]=color[p[x]];
                                color[p[x]]=1;
                                color[right[w]]=1;
                                left_rotate(p[x]);
                                x=root;
                        }
                }
                else{
                        w=left[p[x]];
                        if(color[w]==0){
                                color[w]=1;
                                color[p[x]]=0;
                                right_rotate(p[x]);
                                w=left[p[x]];
                        }
                        if(color[right[w]]==1&&color[left[w]]==1){
                                color[w]=0;
                                x=p[x];
                        }
                        else {
                                if(color[left[w]]==1){
                                        color[right[w]]=1;
                                        color[w]=0;
                                        left_rotate(w);
                                        w=left[p[x]];
                                }
                                color[w]=color[p[x]];
                                color[p[x]]=1;
                                color[left[w]]=1;
                                right_rotate(p[x]);
                                x=root;
                        }
                }
        }
        color[x]=1;
        return 0;
}
int tree_min(int x)
{
        while(left[x]) x=left[x];
        return x;
}
int tree_successor(int x)
{
        int y;
        if(right[x]!=0) return tree_min(right[x]);
        y=p[x];
        while(y!=0&&x==right[y]) {
                x=y;
                y=p[y];
        }
        return y;
}
int tree_delete(int z)
{
        int y,x;
        if(left[z]==0||right[z]==0) y=z;
        else y=tree_successor(z);
        if(left[y]!=0) x=left[y];
        else x=right[y];
        p[x]=p[y];
        if(p[y]==0) root=x;
        else if(y==left[p[y]])  left[p[y]]=x;
        else right[p[y]]=x;
        if(y!=z) key[z]=key[y];
        //update augment;
        int r=p[y];
        while(r){
                size[r]=size[left[r]]+size[right[r]]+1;
                r=p[r];
        }
        if(r==0) size[r]=0;
        if(color[y]==1) delete_fixup(x);
        return y;
}
int output_tree(int n)
{
        for(int i=1;i<=n;i++){
                cout<<i<<" :"<<left[i]<<" "<<right[i]<<" color: "<<color[i]<<" size: 
"<<size[i];
                if(i==root) cout<<" Root"<<endl;
                else cout<<endl;
        }
        return 0;
}

int tree_build(int n)
{
        int i;
        color[0]=1;
        size[0]=0;
        root=1;
        key[root]=1;
        p[root]=0;
        size[root]=1;
        color[root]=1;
        for(i=2;i<=n;i++) {
                key[i]=i;
                tree_insert(i);
        }
        return 0;
}

int J(int n,int m)
{
        int remain=n,i;
        int pointer=0;
        tree_build(n);
        for(i=1;i<=n;i++){
                pointer=(pointer+m)%remain;
                int t=select(root,pointer+1);
                a[key[t]-1]=i;
                tree_delete(t);
                remain--;
        }
        return 0;
}
int main()
{
        int i,n,m;
//      clock_t start,finish;
//      start=clock();
//      freopen("in.txt","r",stdin);
//      freopen("out2.txt","w",stdout);
        while(cin>>n>>m){
                J(n,m);
                for(i=0;i<n-1;i++) cout<<a[i]<<' ';
                cout<<a[i]<<endl;
        }
//      finish=clock();
//      cout<<(double)(finish-start)/CLOCKS_PER_SEC;
        return 0;
}