考虑如果按照键值排序
那么2个点的就是他们中间最大的点
找到后就只需要考虑怎么统计一个点到根的距离
实际上一个点到根的距离是分别往左往右的最长上升子序列的长度和
证明的话是显然的
考虑一个点,如果是往某个方向的最长上升序列上
那么一定是之间的最大值
所以，所以一定在到根的路径上
#include<bits/stdc++.h>
using namespace std;
const int RLEN=1<<20|1;
inline char gc(){
static char ibuf[RLEN],*ib,*ob;
(ob==ib)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
return (ob==ib)?EOF:*ib++;
}
#define gc getchar
#define int unsigned int
inline int read(){
char ch=gc();
int res=0,f=1;
while(!isdigit(ch))f^=ch=='-',ch=gc();
while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=gc();
return f?res:-res;
}
#define ll long long
#define re register
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define cs const
const int mod=1e9+7;
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline void Add(int &a,int b){a=add(a,b);}
inline int dec(int a,int b){return a>=b?a-b:a-b+mod;}
inline void Dec(int &a,int b){a=dec(a,b);}
inline int mul(int a,int b){return 1ll*a*b>=mod?1ll*a*b%mod:a*b;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,a=mul(a,a))(b&1)?(res=mul(res,a)):0;return res;}
inline void chemx(int &a,int b){a<b?a=b:0;}
inline void chemn(int &a,int b){a>b?a=b:0;}
cs int N=200005;
int n,m,tw[N<<1],a[N<<1];
struct opt{
int op,k,w;
}q[N];
namespace seg{
int mx[N<<2],sl[N<<2],sr[N<<2],mxp[N<<2];
#define lc (u<<1)
#define rc ((u<<1)|1)
#define mid ((l+r)>>1)
inline int queryL(int u,int l,int r,int k){
if(l==r)return mx[u]>=k;
if(mx[lc]<k)return queryL(rc,mid+1,r,k);
return sl[u]-sl[lc]+queryL(lc,l,mid,k);
}
inline int queryR(int u,int l,int r,int k){
if(l==r)return mx[u]>=k;
if(mx[rc]<k)return queryR(lc,l,mid,k);
return sr[u]-sr[rc]+queryR(rc,mid+1,r,k);
}
inline void pushup(int u,int l,int r){
if(mx[lc]>mx[rc])mx[u]=mx[lc],mxp[u]=mxp[lc];
else mx[u]=mx[rc],mxp[u]=mxp[rc];
sl[u]=sl[lc]+queryL(rc,mid+1,r,mx[lc]);
sr[u]=sr[rc]+queryR(lc,l,mid,mx[rc]);
}
inline void update(int u,int l,int r,int p,int k){
if(l==r){mx[u]=k,mxp[u]=l,sl[u]=sr[u]=1;return;}
if(p<=mid)update(lc,l,mid,p,k);
else update(rc,mid+1,r,p,k);
pushup(u,l,r);
}
inline void delet(int u,int l,int r,int p){
if(l==r){mx[u]=0,mxp[u]=0,sl[u]=sr[u]=0;return;}
if(p<=mid)delet(lc,l,mid,p);
else delet(rc,mid+1,r,p);
pushup(u,l,r);
}
inline pii query(int u,int l,int r,int st,int des){
if(st<=l&&r<=des)return pii(mx[u],mxp[u]);
if(des<=mid)return query(lc,l,mid,st,des);
if(mid<st)return query(rc,mid+1,r,st,des);
pii vl=query(lc,l,mid,st,des),vr=query(rc,mid+1,r,st,des);
return vl.fi>vr.fi?vl:vr;
}
inline pii qryL(int u,int l,int r,int st,int des,int k){
if(st<=l&&r<=des)return pii(max(mx[u],k),queryL(u,l,r,k));
if(des<=mid)return qryL(lc,l,mid,st,des,k);
if(mid<st)return qryL(rc,mid+1,r,st,des,k);
pii vl=qryL(lc,l,mid,st,des,k);
pii vr=qryL(rc,mid+1,r,st,des,vl.fi);
return pii(max(vl.fi,vr.fi),vl.se+vr.se);
}
inline pii qryR(int u,int l,int r,int st,int des,int k){
if(st<=l&&r<=des)return pii(max(mx[u],k),queryR(u,l,r,k));
if(des<=mid)return qryR(lc,l,mid,st,des,k);
if(mid<st)return qryR(rc,mid+1,r,st,des,k);
pii vl=qryR(rc,mid+1,r,st,des,k);
pii vr=qryR(lc,l,mid,st,des,vl.fi);
return pii(max(vl.fi,vr.fi),vl.se+vr.se);
}
inline int dis(int u){
int res=0;
if(u<m)res+=qryL(1,1,m,u+1,m,tw[u]).se;
if(1<u)res+=qryR(1,1,m,1,u-1,tw[u]).se;
return res;
}
inline int ask(int ku,int kv){
if(ku>kv)swap(ku,kv);
int pos=query(1,1,m,ku,kv).se;
return dis(ku)+dis(kv)-2*dis(pos);
}
};
signed main(){
n=read();
for(int i=1;i<=n;i++){
int op=read(),k=read(),w;q[i].op=op,q[i].k=k;
a[++m]=k;
if(op!=1)
w=read(),q[i].w=w,a[++m]=w;
}
sort(a+1,a+m+1);
m=unique(a+1,a+m+1)-a-1;
for(int i=1;i<=n;i++){
q[i].k=lower_bound(a+1,a+m+1,q[i].k)-a;
if(q[i].op!=1)q[i].w=lower_bound(a+1,a+m+1,q[i].w)-a;
}
for(int i=1;i<=n;i++){
int op=q[i].op,k=q[i].k,w=q[i].w;
if(op==0){
seg::update(1,1,m,k,w),tw[k]=w;
}
if(op==1){
seg::delet(1,1,m,k);
}
if(op==2){
cout<<seg::ask(k,w)<<'
';
}
}
}