题面去内网找。。
先写题解，后写吐槽。。。
把treap中序遍历一边就是一个单调的序列，又因为它保证了权值，键值都不互相重复，同一权值的点不会同时出现两个，那么可以把权值离散一下，用下标搞可线段树啊。。因此我们离线处理，先建出所有点的线段树，把键值设为0，然后一点一点搞即可。
那么如何求两点的距离呢？
首先我们会想到LCA，但是这个LCA可以用线段树解决，因为两点间键值最大的那个点就是他们的LCA（想证的自己证一下，举不出反例），那么根据正规的LCA思想，接下来就要求出两点到根节点的距离，再减去LCA到根节点距离的2倍。
思路没错。
事实证明，键值比他小的点深度都比他浅（废话。。），那么某个点向左向右第一个比他浅的点一定是他的某个祖先（你可以再证一下。。）。以此类推，就可以找到到根节点的路径了，因此我们可以把问题简化一下：说白了就是求这个点向左向右的上升序列的长度之和。
那么这道题就变成求某一段的上升序列长度了。求法相同于 bzoj2957 楼房重建.我的题解
正常人分界线
谁知道考试时看到这道题时我什么心情。。一看以为是平衡树模拟，然后发现rand（）出的值是他给的，所以树的形态很可能被卡。。。一脸茫然，最后用范浩强treap打了个LCA。。。最后正解是线段树。。。代码长度200+～110不等。。考得倒是联赛的内容。。。。
#pragma GCC optimize("O3")
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define N 200005
using namespace std;
int read()
{int sum=0,f=1;char x=getchar();while(x<'0'||x>'9'){
if(x=='-')f=-1;x=getchar();}while(x>='0'&&x<='9'){sum=(sum<<1)+(sum<<3)+x-'0';x=getchar();}return sum*f;
}
struct node{
int xp,k,w;}b[N];
int n,tot,a[N],c[N];
namespace Tree
{struct tree{
int l,r,h,g,szl,szr;}t[N*4];typedef pair<int,int> hh;int s,h,mh;void build(int l,int r,int x){t[x].l=l;t[x].r=r;if(l==r){t[x].h=t[x].szl=t[x].szr;return;}int mid=l+r>>1;build(l,mid,x*2);build(mid+1,r,x*2+1);}int q_r(int k,int x){if(t[x].l==t[x].r){
return k<t[x].h;}int mid=t[x].l+t[x].r>>1;if(t[x*2].h<k)return q_r(k,x*2+1);else return q_r(k,x*2)+t[x].szr-t[x*2].szr;}int q_l(int k,int x){if(t[x].l==t[x].r){
return k<t[x].h;}int mid=t[x].l+t[x].r>>1;if(t[x*2+1].h<k)return q_l(k,x*2);else return q_l(k,x*2+1)+t[x].szl-t[x*2+1].szl;}hh q_h(int l,int r,int x){if(t[x].l>=l&&t[x].r<=r)return hh(t[x].h,t[x].g);int mid=t[x].l+t[x].r>>1; hh s1,s2;if(l<=mid)s1=q_h(l,r,x*2);if(r>mid)s2=q_h(l,r,x*2+1);return s1.first>s2.first ? s1:s2;}void up(int x){if(t[x*2].h>t[x*2+1].h){t[x].h=t[x*2].h,t[x].g=t[x*2].g;}else {t[x].h=t[x*2+1].h,t[x].g=t[x*2+1].g;}t[x].szr=t[x*2].szr+q_r(t[x*2].h,x*2+1);t[x].szl=t[x*2+1].szl+q_l(t[x*2+1].h,x*2);}void C(int l,int k,int x){if(t[x].l==t[x].r){t[x].g=l;t[x].h=k;t[x].szl=t[x].szr=1;return;}int mid=t[x].l+t[x].r>>1;if(l<=mid)C(l,k,x*2);else C(l,k,x*2+1);up(x);}void Q_l(int l,int r,int x){if(t[x].l>=l&&t[x].r<=r){h+=q_l(mh,x);mh=max(mh,t[x].h);return;}int mid=t[x].l+t[x].r>>1;if(r>mid)Q_l(l,r,x*2+1);if(l<=mid)Q_l(l,r,x*2);}void Q_r(int l,int r,int x){if(t[x].l>=l&&t[x].r<=r){h+=q_r(mh,x);mh=max(mh,t[x].h);return;}int mid=t[x].l+t[x].r>>1;if(l<=mid)Q_r(l,r,x*2);if(r>mid)Q_r(l,r,x*2+1);} int Q(int l,int k){s=0;h=1;mh=k;Q_l(1,l,1);s+=h;h=1;mh=k;Q_r(l,tot,1);s+=h;return s;}void work(int l,int r){hh d=q_h(l,r,1);int lca=d.second,k;k=Q(l,c[l])+Q(r,c[r])-2*Q(lca,c[lca]);printf("%d\n",k);}int get(int x){
return lower_bound(a+1,a+tot+1,x)-a;}
}
using namespace Tree;
int main()
{n=read();for(int i=1;i<=n;i++){b[i].xp=read();b[i].k=read();if(b[i].xp!=1)b[i].w=read();if(b[i].xp==0)a[++tot]=b[i].k;}sort(a+1,a+tot+1);tot=unique(a+1,a+tot+1)-a-1;build(1,tot,1);int k,w;for(int i=1;i<=n;i++){if(b[i].xp==0)k=get(b[i].k),C(k,b[i].w,1),c[k]=b[i].w;if(b[i].xp==1)k=get(b[i].k),C(k,0,1),c[k]=0;if(b[i].xp==2){k=get(b[i].k);w=get(b[i].w);if(k>w)swap(k,w);work(k,w);}}
}