查看: 956|回復: 1

[提問] Treap隨機pri

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2014-12-15 22:34:36 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    x
    本帖最後由 domen111 於 2014-12-15 22:39 編輯

    Treap隨機的值為什麼要存在pri,他用一個隨機值去保持Heap的性質,但是為什麼不要在第25行直接改成rand()%2就好了,都一樣是隨機啊,可是這樣就完全沒有甚麼Heap的概念在了
    實際測試
    有pri: AC http://hoj.twbbs.org/judge/judge/submission/26364 (code在下面)
    沒pri,直接rand: AC http://hoj.twbbs.org/judge/judge/submission/26382 (http://ideone.com/Tv3G1H)


    [C++] 純文本查看 復制代碼
    #include<cstdio>
    #include<cstdlib>
    #include<ctime>
    #include<algorithm>
    #define SIZE(t) ((t)?(t)->size:0) 
    #define MAXNUM(t) ((t)?(t)->mn:0) 
    using namespace std;
    struct Treap{
        Treap *L,*R;
        int pri,size,num,mn;
        Treap(int _num){
            num=mn=_num;
            pri=rand();
            L=R=NULL; 
            size=1;
        }
        void up(){
            size=SIZE(L)+SIZE(R)+1;
            mn=max(num,max(MAXNUM(L),MAXNUM(R)));
        }
    }*tr;
    Treap *merge(Treap *a,Treap *b)
    {
        if(!a||!b) return a?a:b;
        if(a->pri>=b->pri){
            a->R=merge(a->R,b);
            a->up();
            return a;
        }else{
            b->L=merge(a,b->L);
            b->up();
            return b;
        }
    }
    void split(Treap *tr,Treap *&a,Treap *&b,int k)
    {
        if(k==0){
            a=NULL; b=tr;
        }else{
            if(SIZE(tr->L)>=k){
                b=tr;
                split(b->L,a,b->L,k);
                b->up();
            }else{
                a=tr;
                split(a->R,a->R,b,k-SIZE(a->L)-1);
                a->up();
            }
        }
    }
    int main()
    {
        srand(time(NULL));
        int n,q;
        scanf("%d %d",&n,&q);
        int tmp;
        scanf("%d",&tmp);
        tr=new Treap(tmp);
        for(int i=1;i<n;i++){
            scanf("%d",&tmp);
            tr=merge(tr,new Treap(tmp));
        }
         
        for(int i=0;i<q;i++)
        {
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            if(a==1)
            {
                Treap *x,*y,*z;
                split(tr,x,y,b-1);
                split(y,y,z,1);
                y=new Treap(c);
                x=merge(x,y);
                tr=merge(x,z);
            }
            else
            {
                Treap *x,*y,*z;
                split(tr,y,z,c);
                split(y,x,y,b-1);
                printf("%d\n",MAXNUM(y));
                x=merge(x,y);
                tr=merge(x,z);
            }
        }
    }


    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

     樓主| 發表於 2014-12-17 20:58:34 | 顯示全部樓層
    在這篇文章「可持久化Treap」那邊看到好像有人也是用類似的寫法,不過他的隨機權重好像和我的寫法不同
    http://blog.csdn.net/wjf_wzzc/article/details/39672563
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復 支持 反對

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表