rt

Wa+Tle，下了一下第一个点的数据，本地运行数据和答案一样，但交上去一直WA……

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#define N 1100010
int n,m;
class Treap{
	public:
	int root,tot;
	class node{
		public:
		int l,r;
		int v,ma,mi,size,dat;
	}a[N];
	Treap(){
		root=tot=0;
		a[0].ma=0x80808080;
		a[0].mi=0x3f3f3f3f;
	}void up(int x){
		if(!x)return;
		a[x].size=a[a[x].l].size+a[a[x].r].size+1;
		a[x].ma=std::max(a[a[x].l].ma,std::max(a[a[x].r].ma,a[x].v));
		a[x].mi=std::min(a[x].v,std::min(a[a[x].l].mi,a[a[x].r].mi));
		return;
	}int newnode(int val){
		a[++tot].v=a[tot].ma=a[tot].mi=val;
		a[tot].size=1;
		a[tot].dat=std::rand();
		return tot;
	}
	void split(int p,int rk,int &x,int &y){
		if(p==0)x=y=0;
		else if(a[a[p].l].size+1>rk)y=p,split(a[p].l,rk,x,a[p].l);
		else x=p,split(a[p].r,rk-a[a[x].l].size-1,a[p].r,y);
		up(p);
	}int merge(int x,int y){
		if(!x||!y)return x+y;
		else if(a[x].dat<a[y].dat){
			a[x].r=merge(a[x].r,y);
			up(x);
			return x;
		}else{
			a[y].l=merge(x,a[y].l);
			up(y);
			return y;
		}
	}
	void insert(int rk,int val){
		int x,y;
		split(root,rk,x,y);
		root=merge(merge(x,newnode(val)),y);
		return;
	}void Delete(int rk){
		int x,y,z;
		split(root,rk,x,z);
		split(x,rk-1,x,y);
		y=merge(a[y].l,a[y].r);
		root=merge(merge(x,y),z);
		return;
	}int getm(int l,int r,bool fl){
		int x,y,z;
		split(root,r,x,z);
		split(x,l-1,x,y);
		int ma=a[y].ma,mi=a[y].mi;
		root=merge(merge(x,y),z);
		return fl?ma:mi;
	}
}bt;
int main(){
	std::srand(time(NULL));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		bt.insert(i,x);
	}for(int i=1;i<=m;i++){
		int opt,x,y;
		scanf("%d%d",&opt,&x);
		if(opt==1)bt.Delete(x);
		else {
			scanf("%d",&y);
			printf("%d %d\n",bt.getm(x,y,0),bt.getm(x,y,1));
		}
	}return 0;
}