[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);
}
}
}