Treap隨機pri

domen111

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

在這篇文章「可持久化Treap」那邊看到好像有人也是用類似的寫法，不過他的隨機權重好像和我的寫法不同
http://blog.csdn.net/wjf_wzzc/article/details/39672563