$\texttt{FHQtreap}$ 错的离谱

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
#include<queue>
//#include<map>
#include<vector>
#include<math.h>
using namespace std;
#define int long long
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define repp(i,a,b) for(int i=a;i>=b;i--)
#define INF 1e9
#define ll long long
#define MAXN 200005
const int _x[]={0,1,0,-1,0},_y[]={0,0,1,0,-1};
#define mem(a,n) memset(a,n,sizeof(a));
#define chkmax(a,b) a=a>b?a:b;
#define chkmin(a,b) a=a<b?a:b;
#include<set>
#include<stack>
#define lc tree[i].l
#define rc tree[i].r
#define MOD 1000000
int root,cnt;
struct FHQtree{
	int l,r;
	int size,key;
	int val;
}tree[MAXN*4];
void update(int i){
	tree[i].size=tree[lc].size+tree[rc].size+1;
}
int add(int i){
	tree[++cnt].val=i;
	tree[cnt].key=rand();
	tree[cnt].size=1;
	return cnt;
}
void split(int i,int k,int &l,int &r){
	if(!i){
		l=r=0;
		return;
	}
	if(tree[i].val<=k){
		l=i;
		split(rc,k,rc,r);
	}
	else{
		r=i;
		split(lc,k,l,lc);
	}
	update(i);
}
int merge(int l,int r){
	if(!l||!r){
		return l+r;
	}
	if(tree[l].key<=tree[r].key){
		tree[l].r=merge(tree[l].r,r);
		update(l);
		return l;
	}
	else if(tree[l].key>tree[r].key){
		tree[r].l=merge(l,tree[r].l);
		update(r);
		return r;
	}
}
int l,r,p;
void insert(int i){
	split(root,i,l,r);
	root=merge(merge(l,add(i)),r);
}
void pop(int i){
	split(root,i,l,p);
	split(l,i-1,l,r);
	r=merge(tree[r].l,tree[r].r);
	root=merge(merge(l,r),p);
}
int findrk(int x){
	split(root,x-1,l,r);
	int k=tree[l].size+1;
	root=merge(l,r);
	return k;
}
int findval(int i,int k){
	if(tree[lc].size+1==k){
		return tree[i].val;
	}
	if(tree[lc].size>=k){
		return findval(lc,k);
	}
	else{
		return findval(rc,k-tree[lc].size-1);
	}
}
int pre(int i){
	split(root,i,l,r);
	p=l;
	while(tree[i].r){
	  p=tree[p].r;
  }
  root=merge(l,r);
  return p;
}
int back(int i){
	split(root,i,l,r);
	p=r;
	while(tree[p].l){
	  p=tree[p].l;
  }
  root=merge(l,r);
  return p;
}
int n,ans;
int tot;
signed main(){
  srand(1145141919810);
  scanf("%lld",&n);
  forr(i,1,n){
    int opt,x;
    scanf("%lld%lld",&opt,&x);
    if(opt==tot){
      insert(x);
      continue;
    }
    else if(!tree[root].size){
      tot=opt;
      insert(x);
      continue;
    }
    else{
      int p1=pre(x),p2=back(x);
      if(p1||p2){
        ans+=((p1|p2)-tree[p1|p2].val);
        ans%=MOD;
        pop(tree[p1|p2].val);
        continue;
      }
      int pr=x-tree[p1].val,ba=tree[p2].val-x;
      pr>ba?(ans+=ba,pop(ba)):(ans+=pr,pop(pr));
    }
  }
  printf("%lld",ans);
}