带旋Treap（三棵平衡树）MLE 70pts MnZn 求助

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6+10,md = 1e7+7;
#define int long long 
//维护三棵差值平衡树，一棵平衡树维护的是两个相邻的数的差，一棵平衡树维护的是排序后的数，一棵平衡树维护的是排序后的数的差
int n,m,a[N],rt,rt2,cnt,cnt2,rt3,cnt3,b[N]; 
struct T{
	int l;
	int r;
	int val;
	int pri;
	int size;
}tree[N],tree2[N],tree3[N];
void update(int x){
	tree[x].size=tree[tree[x].l].size+tree[tree[x].r].size+1;	
}
void right_rorate(int &now){
	int tmp=tree[now].l;
	tree[now].l=tree[tmp].r;
	tree[tmp].r=now;
	tree[tmp].size=tree[now].size;
	update(now);
	now=tmp;	
}
void left_rorate(int &now){
	int tmp=tree[now].r;
	tree[now].r=tree[tmp].l;
	tree[tmp].l=now;
	tree[tmp].size=tree[now].size;
	update(now);
	now=tmp;
}
inline void insert(int &now,int w){
	if(now==0){
		now=++cnt;
		tree[now].size=1;
		tree[now].val=w;
		tree[now].pri=rand()*rand()%md;
		return;
	}
	tree[now].size++;
	if(w>=tree[now].val){
		insert(tree[now].r,w);
	}
	else{
		insert(tree[now].l,w);
	}
	if(tree[now].l!=0&&tree[now].pri>tree[tree[now].l].pri){
		right_rorate(now);
	}
	if(tree[now].r!=0&&tree[now].pri>tree[tree[now].r].pri){
		left_rorate(now);
	}
	update(now);
}
inline void erase(int &now,int w){
	tree[now].size--;
	if(tree[now].val==w){
		if(tree[now].l==0&&tree[now].r==0){
			now=0;
			return;
		}
		if(tree[now].l==0||tree[now].r==0){//如果没有左儿子或右儿子，那删除当前节点后，当前节点的儿子顶替了当前节点的位置 
			now=tree[now].l+tree[now].r;
			return;
		}
		if(tree[tree[now].l].pri<tree[tree[now].r].pri){
			right_rorate(now);
			erase(tree[now].r,w);
			return;
		} 
		else{
			left_rorate(now);
			erase(tree[now].l,w);
			return;
		}
	}	
	if(tree[now].val>=w){
		erase(tree[now].l,w);
	}
	else{
		erase(tree[now].r,w);
	}
	update(now);
}
inline int rk(int now,int w){
	if(now==0){
		return 0;
	}
	if(w>tree[now].val){
		return tree[tree[now].l].size+1+rk(tree[now].r,w);
	}
	return rk(tree[now].l,w);
}
inline int find(int now,int w){
	if(w==tree[tree[now].l].size+1){
		return tree[now].val;
	}
	if(w>tree[tree[now].l].size+1){
		return find(tree[now].r,w-tree[tree[now].l].size-1);
	}
	return find(tree[now].l,w);
}
void update2(int x){
	tree2[x].size=tree2[tree2[x].l].size+tree2[tree2[x].r].size+1;	
}
void right_rorate2(int &now){
	int tmp=tree2[now].l;
	tree2[now].l=tree2[tmp].r;
	tree2[tmp].r=now;
	tree2[tmp].size=tree2[now].size;
	update2(now);
	now=tmp;	
}
void left_rorate2(int &now){
	int tmp=tree2[now].r;
	tree2[now].r=tree2[tmp].l;
	tree2[tmp].l=now;
	tree2[tmp].size=tree2[now].size;
	update2(now);
	now=tmp;
}
inline void insert2(int &now,int w){
	if(now==0){
		now=++cnt;
		tree2[now].size=1;
		tree2[now].val=w;
		tree2[now].pri=rand()*rand()%md;
		return;
	}
	tree2[now].size++;
	if(w>=tree2[now].val){
		insert2(tree2[now].r,w);
	}
	else{
		insert2(tree2[now].l,w);
	}
	if(tree2[now].l!=0&&tree2[now].pri>tree2[tree2[now].l].pri){
		right_rorate2(now);
	}
	if(tree2[now].r!=0&&tree2[now].pri>tree2[tree2[now].r].pri){
		left_rorate2(now);
	}
	update2(now);
}
inline void erase2(int &now,int w){
	tree2[now].size--;
	if(tree2[now].val==w){
		if(tree2[now].l==0&&tree2[now].r==0){
			now=0;
			return;
		}
		if(tree2[now].l==0||tree2[now].r==0){//如果没有左儿子或右儿子，那删除当前节点后，当前节点的儿子顶替了当前节点的位置 
			now=tree2[now].l+tree2[now].r;
			return;
		}
		if(tree2[tree2[now].l].pri<tree2[tree2[now].r].pri){
			right_rorate2(now);
			erase2(tree2[now].r,w);
			return;
		} 
		else{
			left_rorate2(now);
			erase2(tree2[now].l,w);
			return;
		}
	}	
	if(tree2[now].val>=w){
		erase2(tree2[now].l,w);
	}
	else{
		erase2(tree2[now].r,w);
	}
	update2(now);
}
inline int rk2(int now,int w){
	if(now==0){
		return 0;
	}
	if(w>tree2[now].val){
		return tree2[tree2[now].l].size+1+rk2(tree2[now].r,w);
	}
	return rk2(tree2[now].l,w);
}
inline int find2(int now,int w){
	if(w==tree2[tree2[now].l].size+1){
		return tree2[now].val;
	}
	if(w>tree2[tree2[now].l].size+1){
		return find2(tree2[now].r,w-tree2[tree2[now].l].size-1);
	}
	return find2(tree2[now].l,w);
}
int query_pre2(int now,int w){
	if(now==0){
		return 0;
	}
	if(tree2[now].val>=w){
		return query_pre2(tree2[now].l,w);
	}
	int tmp=query_pre2(tree2[now].r,w);
	if(tmp==0){
		return tree2[now].val;
	}
	return tmp;
}
int query_suf2(int now,int w){
	if(now==0){
		return 0;
	}
	if(tree2[now].val<=w){
		return query_suf2(tree2[now].r,w);
	}
	int tmp=query_suf2(tree2[now].l,w);
	if(tmp==0){
		return tree2[now].val;
	}
	return tmp;
}
//后面的函数和前面的差不多，只是换了个数组                         
void update3(int x){
	tree3[x].size=tree3[tree3[x].l].size+tree3[tree3[x].r].size+1;	
}
void right_rorate3(int &now){
	int tmp=tree3[now].l;
	tree3[now].l=tree3[tmp].r;
	tree3[tmp].r=now;
	tree3[tmp].size=tree3[now].size;
	update3(now);
	now=tmp;	
}
void left_rorate3(int &now){
	int tmp=tree3[now].r;
	tree3[now].r=tree3[tmp].l;
	tree3[tmp].l=now;
	tree3[tmp].size=tree3[now].size;
	update3(now);
	now=tmp;
}
inline void insert3(int &now,int w){
	if(now==0){
		now=++cnt;
		tree3[now].size=1;
		tree3[now].val=w;
		tree3[now].pri=rand()*rand()%md;
		return;
	}
	tree3[now].size++;
	if(w>=tree3[now].val){
		insert3(tree3[now].r,w);
	}
	else{
		insert3(tree3[now].l,w);
	}
	if(tree3[now].l!=0&&tree3[now].pri>tree3[tree3[now].l].pri){
		right_rorate3(now);
	}
	if(tree3[now].r!=0&&tree3[now].pri>tree3[tree3[now].r].pri){
		left_rorate3(now);
	}
	update3(now);
}
inline void erase3(int &now,int w){
	tree3[now].size--;
	if(tree3[now].val==w){
		if(tree3[now].l==0&&tree3[now].r==0){
			now=0;
			return;
		}
		if(tree3[now].l==0||tree3[now].r==0){//如果没有左儿子或右儿子，那删除当前节点后，当前节点的儿子顶替了当前节点的位置 
			now=tree3[now].l+tree3[now].r;
			return;
		}
		if(tree3[tree3[now].l].pri<tree3[tree3[now].r].pri){
			right_rorate3(now);
			erase3(tree3[now].r,w);
			return;
		} 
		else{
			left_rorate3(now);
			erase3(tree3[now].l,w);
			return;
		}
	}	
	if(tree3[now].val>=w){
		erase3(tree3[now].l,w);
	}
	else{
		erase3(tree3[now].r,w);
	}
	update3(now);
}
inline int rk3(int now,int w){
	if(now==0){
		return 0;
	}
	if(w>tree3[now].val){
		return tree3[tree3[now].l].size+1+rk3(tree3[now].r,w);
	}
	return rk3(tree3[now].l,w);
}
inline int find3(int now,int w){
	if(w==tree3[tree3[now].l].size+1){
		return tree3[now].val;
	}
	if(w>tree3[tree3[now].l].size+1){
		return find3(tree3[now].r,w-tree3[tree3[now].l].size-1);
	}
	return find3(tree3[now].l,w);
}
signed main(){
	cin>>n>>m;
	priority_queue<int> q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
		if(i!=1) insert(rt,abs(a[i]-a[i-1]));
		q.push(a[i]);
	}
	int last=-1;
	while(!q.empty()){
		int x=q.top();
		q.pop();
		insert2(rt2,x);
		if(last!=-1) insert3(rt3,abs(x-last));
		last=x;
	}
	for(int i=1;i<=m;i++){
		string s;
		int x,y;
		cin>>s;
		if(s=="INSERT"){
			cin>>x>>y;
			if(x!=n){
				erase(rt,abs(a[x+1]-b[x]));
			}
			insert(rt,abs(y-b[x]));
			if(x!=n){
				insert(rt,abs(a[x+1]-y));
			}
			int p=rk2(rt2,y);
			int fr=query_pre2(rt2,y);
			int lyq=find2(rt2,p+1);
			int sf=query_suf2(rt2,y);
			insert2(rt2,y);
			if(p==0){
				if(lyq==y){
					insert3(rt3,0);
				}	
				else{
					if(sf==0) insert3(rt3,abs(sf-y));
				}
			} 
			else if(sf==0){
				if(lyq==y){
					insert3(rt3,0);
				}
				else{
					insert3(rt3,abs(y-fr));
				}
			}
			else{
				if(lyq==y){
					insert3(rt3,0);
				}
				else{
			    	erase3(rt3,abs(sf-fr));
			    	insert3(rt3,abs(sf-y));
					insert3(rt3,abs(y-fr));
				}
			}
			b[x]=y;
		}
		else if(s=="MIN_SORT_GAP"){
			cout<<find3(rt3,1)<<endl;
		}
		else{
			cout<<find(rt,1)<<endl; 
		}
	}
	return 0;
}