本帖最後由 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)
[mw_shl_code=cpp,true]#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);
}
}
}[/mw_shl_code]
