FHQ-treap 求调,马蜂阳间,调完就可以获得关注

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000;
struct node{
	long long val,rd;
}p1[10005],p2[10005];
long long T,op,x,tot,root1,root2,rx,ry,rz,cnt1=0,cnt2=0;
long long son1[10005][2],size1[10005],son2[10005][2],size2[10005];
void update1(long long p){
	size1[p]=size1[son1[p][0]]+size1[son1[p][1]]+1;
}
long long add1(long long x){
	cnt1++;
	p1[cnt1].rd=rand();
	p1[cnt1].val=x;
	size1[cnt1]=1;
	return cnt1;
}
void split1(long long rt,long long key,long long &x,long long &y){
	if(!rt){
		x=y=0;
		return;
	}
	if(p1[rt].val<=key){
		x=rt;
		split1(son1[rt][1],key,son1[rt][1],y);
	}else{
		y=rt;
		split1(son1[rt][0],key,x,son1[rt][0]);
	}
	update1(rt);
}
long long merge1(long long l,long long r){
	if(l==0||r==0){
		return l+r;
	}
	if(p1[l].val<=p1[r].val){
		son1[l][1]=merge1(son1[l][1],r);
		update1(l);
		return l;
	}else{
		son1[r][0]=merge1(l,son1[r][0]);
		update1(r);
		return r;
	}
}
long long getrnk1(long long x,long long k){
	while(true){
		if(k==(size1[son1[x][0]]+1)){
			return x;
		}else if(k>(size1[son1[x][0]]+1)){
			k-=(size1[son1[x][0]]+1);
			x=son1[x][1];
		}else{
			x=son1[x][0];
		}
	}
}
void update2(long long p){
	size2[p]=size2[son2[p][0]]+size2[son2[p][1]]+1;
}
long long add2(long long x){
	cnt2++;
	p2[cnt2].rd=rand();
	p2[cnt2].val=x;
	size2[cnt2]=1;
	return cnt2;
}
void split2(long long rt,long long key,long long &x,long long &y){
	if(!rt){
		x=y=0;
		return;
	}
	if(p2[rt].val<=key){
		x=rt;
		split2(son2[rt][1],key,son2[rt][1],y);
	}else{
		y=rt;
		split2(son2[rt][0],key,x,son2[rt][0]);
	}
	update2(rt);
}
long long merge2(long long l,long long r){
	if(l==0||r==0){
		return l+r;
	}
	if(p2[l].val<=p2[r].val){
		son2[l][1]=merge2(son2[l][1],r);
		update2(l);
		return l;
	}else{
		son2[r][0]=merge2(l,son2[r][0]);
		update2(r);
		return r;
	}
}
long long getrnk2(long long x,long long k){
	while(true){
		if(k==(size2[son2[x][0]]+1)){
			return x;
		}else if(k>(size2[son2[x][0]]+1)){
			k-=(size2[son2[x][0]]+1);
			x=son2[x][1];
		}else{
			x=son2[x][0];
		}
	}
}
void print(){
	cout<<"_______________________"<<endl;
	cout<<root1<<endl;
	for(long long i=1;i<=cnt1;i++){
		cout<<p1[i].val<<" ";
	}cout<<endl;
	for(long long i=1;i<=cnt1;i++){
		cout<<son1[i][0]<<" "<<son1[i][1]<<endl;
	}
	cout<<"____"<<endl;
	cout<<root2<<endl;
	for(long long i=1;i<=cnt2;i++){
		cout<<p2[i].val<<" ";
	}cout<<endl;
	for(long long i=1;i<=cnt2;i++){
		cout<<son2[i][0]<<" "<<son2[i][1]<<endl;
	}
	cout<<"_______________________"<<endl;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--){
		cin>>op>>x;
		if(op==0){
			if(size2[root2]>0){
				split2(root2,x,rx,ry);
				long long pre=0,nxt=0;
				if(size2[rx]>0) pre=getrnk2(rx,size2[rx]);
				if(size2[ry]>0) nxt=getrnk2(ry,1);
				if(nxt==0&&pre!=0){
					tot=(tot+abs(x-p2[pre].val))%mod;
					split2(rx,p2[pre].val-1,rx,rz);
					root2=merge2(rx,ry);
				}else if(pre==0&&nxt!=0){
					tot=(tot+abs(x-p2[nxt].val))%mod;
					split2(ry,p2[nxt].val+1,ry,rz);
					root2=merge2(rx,rz);
				}else if(abs(x-p2[pre].val)<=abs(x-p2[nxt].val)){
					tot=(tot+abs(x-p2[pre].val))%mod;
					split2(rx,p2[pre].val-1,rx,rz);
					root2=merge2(rx,ry);
				}else{
					tot=(tot+abs(x-p2[nxt].val))%mod;
					split2(ry,p2[nxt].val+1,ry,rz);
					root2=merge2(rx,rz);
				}
			}else{
				split1(root1,x,rx,ry);
				root1=merge1(merge1(rx,add1(x)),ry);
			}
		}else{
			if(size1[root1]>0){
				split1(root1,x,rx,ry);
				long long pre=0,nxt=0;
				if(size1[rx]>0) pre=getrnk1(rx,size1[rx]);
				if(size1[ry]>0) nxt=getrnk1(ry,1);
				if(nxt==0&&pre!=0){
					tot=(tot+abs(x-p1[pre].val))%mod;
					split1(rx,p1[pre].val-1,rx,rz);
					root1=merge1(rx,ry);
				}else if(pre==0&&nxt!=0){
					tot=(tot+abs(x-p1[nxt].val))%mod;
					split1(ry,p1[nxt].val+1,ry,rz);
					root1=merge1(rx,rz);
				}else if(abs(x-p1[pre].val)<=abs(x-p1[nxt].val)){
					tot=(tot+abs(x-p1[pre].val))%mod;
					split1(rx,p1[pre].val-1,rx,rz);
					root1=merge1(rx,ry);
				}else{
					tot=(tot+abs(x-p1[nxt].val))%mod;
					split1(ry,p1[nxt].val+1,ry,rz);
					root1=merge1(rx,rz);
				}
			}else{
				split2(root2,x,rx,ry);
				root2=merge2(merge2(rx,add2(x)),ry);
			}
		}
		//print();
	}
	cout<<tot<<endl;
	
	return 0;
}