注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

SDOI2008[郁闷的小J]  

2010-07-27 15:15:22|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

然后我自己写了一个随机函数,经过我自己的测试,用这个函数连续输出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));

        }

    }

}

 

  评论这张
 
阅读(768)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018