SDOI2008[郁闷的小J]

数据结构类题目,赤裸裸的平衡树。


然后我自己写了一个随机函数,经过我自己的测试,用这个函数连续输出10^6个数,其中只有10^3多一点点的数重复次数超过1,有0个数重复次数超过2。所以这是一个不错的随机函数。


SDOI2008[郁闷的小J]解题报告 - 天之骄子 - 天之骄子的家

CODE:


/*


AUTHOR: Su Jiao


DATE: 2010-7-27


DESCRIPTION:


山东2008年省选 郁闷的小J


*/


#include <stdio.h>


 


struct Treap


{


       static const int MAXNODE=1000000;


       struct struct_node{struct_node* c[1<<1];int p,s,k;};


       typedef struct_node* node;


       static struct_node pool[MAXNODE];


       static node top;


       node root,null;


       Treap()


       {


              null=top++;


              null->c[0]=null->c[1]=null;


              null->p=(~0u)>>1;


              null->s=0;


              null->k=0;


              root=null;


       }


       int rand()


       {


           const int a=0x19930309,b=19930309;


           static int c,d;


           c^=d;


           return d=(b*d)+(a^c);


       }


       void resize(node x)


       {


            if (x!=null) x->s=x->c[0]->s+x->c[1]->s+1;


       }


       void rotate(node& x,bool d)


       {


            node y=x->c[!d];


            x->c[!d]=y->c[d];


            y->c[d]=x;


            resize(x),resize(y);


            x=y;


       }


       void insert(node& x,int k)


       {


            if (x==null)


            {


               x=top++;


               x->c[0]=x->c[1]=null;


               x->p=rand();


               x->k=k;


               resize(x);


            }


            else


            {


                if (x->k==k) return;


                bool d=x->k<k;


                insert(x->c[d],k);


                if (x->c[d]->p<x->p) rotate(x,!d);


                else resize(x);


            }


       }


       void remove(node& x,int k)


       {


            if (x!=null)


            {


               if (x->k==k)


               {


                  if (x->c[0]==null&&x->c[1]==null) x=null;


                  else if (x->c[0]==null) x=x->c[1];


                  else if (x->c[1]==null) x=x->c[0];


                  else


                  {


                      bool d=x->c[0]->p<x->c[1]->p;


                      rotate(x,d);


                      remove(x->c[d],k);


                  }


               }


               else remove(x->c[x->k<k],k);


               resize(x);


            }


       }


       node search(node x,int k)


       {


            if (x==null) return null;


            if (x->k==k) return x;


            else return search(x->c[x->k<k],k);


       }


       node select(node x,int k)


       {


            if (x==null) return x;


            if (x->c[0]->s>=k) return select(x->c[0],k);


            k-=x->c[0]->s;


            if (k==1) return x;


            k-=1;


            return select(x->c[1],k);


       }


       int rank(node x,int k)


       {


           if (x==null) return 0;


           if (k<x->k) return rank(x->c[0],k);


           else if (k==x->k) return x->c[0]->s+1;


           else return x->c[0]->s+1+rank(x->c[1],k);


       }


       void for_each(node x,void (*function)(node))


       {


            if (x==null) return;


            for_each(x->c[0],function);


            function(x);


            for_each(x->c[1],function);


       }


       void insert(int k)


       {


            insert(root,k);


       }


       void remove(int k)


       {


            remove(root,k);


       }


       node search(int k)


       {


            return search(root,k);


       }


       node select(int k)


       {


            return select(root,k);


       }


       int rank(int k)


       {


           return rank(root,k);


       }


       void for_each(void (*function)(node))


       {


            for_each(root,function);


       }


};


Treap::struct_node Treap::pool[Treap::MAXNODE];


Treap::node Treap::top=Treap::pool;


 


const int MAXN=100000+2;


const int MAXM=100000;


typedef Treap::node node;


int N,M;


int a[MAXN];


char order[MAXM];


int A[MAXM],B[MAXM],K[MAXM],P[MAXM];


Treap book;


Treap position[MAXN+MAXM];


void get_id(node x)


{


     static int id;


     x->s=id++;


}


int main()


{


    scanf(“%d%d”,&N,&M);


    for (int i=1;i<=N;i++)


        scanf(“%d”,a+i);


    for (int i=0;i<M;i++)


    {


        scanf(“\n%c”,&order[i]);


        if (order[i]==’C’) scanf(“%d%d”,A+i,P+i);


        else scanf(“%d%d%d”,A+i,B+i,K+i);


    }


    for (int i=1;i<=N;i++)


        book.insert(a[i]);


    for (int i=0;i<M;i++)


        if (order[i]==’C’) book.insert(P[i]);


        else book.insert(K[i]);


    book.for_each(get_id);


    for (int i=1;i<=N;i++)


    {


        node x=book.search(a[i]);


        position[x->s].insert(i);


    }


    for (int i=0;i<M;i++)


    {


        if (order[i]==’C’)


        {


           node x=book.search(a[A[i]]);


           position[x->s].remove(A[i]);


           node y=book.search(P[i]);


           position[y->s].insert(A[i]);


           a[A[i]]=P[i];


        }


        else


        {


            node x=book.search(K[i]);


            printf(“%d\n”,position[x->s].rank(B[i])-position[x->s].rank(A[i]-1));


        }


    }


}


 

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注