我们知道二叉搜索树的中序遍历是一个已经排好序的序列，知道序列我们无法确定树的形态（因为有多种）。
但是，Treap如果告诉我们它的关键字以及权值，那么就可以唯一确定树的形态（Treap的O(logn)的期望时间复杂度就是依靠一个随机堆的深度不会太深）
具体的，已知关键字序列：k1,k2,k3...kn和优先级序列：p1,p2,p3,...pn，
如果我们想要找ki的父亲，只需要找“左边第一个p比它大的和右边第一个p比它大的中，p较小的那个“
至于lca(ki,kj)，是对应的pi~pj中的最小值（因为是小根堆）
至于深度，多次找父亲，路径长度就是深度，然后画一下图可以发现轨迹的特点，然后就可以搞了（求两段递增子序列长度）
/**************************************************************
Problem: 2770
User: idy002
Language: C++
Result: Accepted
Time:6140 ms
Memory:46124 kb
****************************************************************/ #include <cstdio>
#include <vector>
#include <algorithm>
#define oo 0x6FFFFFFF
#define maxn 400010
using namespace std; typedef pair<int,int> dpr; struct Node {
int lf, rg, mid;
dpr st;
bool leaf;
Node *ls, *rs;
} pool[maxn*], *tail=pool, *root;
vector<Node*> stk; int disc[maxn], ntot;
int sv[maxn];
int pr[maxn][]; Node *build( int lf, int rg ) {
Node *nd = ++tail;
nd->lf=lf, nd->rg=rg, nd->mid=(lf+rg)>>;
if( lf==rg ) {
nd->st = dpr( oo, );
nd->leaf = true;
} else {
nd->ls = build( lf, nd->mid );
nd->rs = build( nd->mid+, rg );
nd->st = dpr( oo, );
nd->leaf = false;
}
return nd;
}
dpr qu_min( Node *nd, int lf, int rg ) {
if( lf <= nd->lf && nd->rg <= rg ) return nd->st;
dpr rt = dpr( oo, );
if( lf <= nd->mid )
rt = qu_min( nd->ls, lf, rg );
if( rg > nd->mid )
rt = min( rt, qu_min( nd->rs, lf, rg ) );
return rt;
}
void pushup( Node *nd ) {
nd->st = min( nd->ls->st, nd->rs->st );
}
void modify( Node *nd, int pos, int val ) {
if( nd->leaf ) {
nd->st = dpr( val, pos );
return;
}
if( pos <= nd->mid )
modify( nd->ls, pos, val );
else
modify( nd->rs, pos, val );
pushup( nd );
}
int lca( int u, int v ) {
if( u>v ) swap(u,v);
return qu_min( root, u, v ).second;
} int main() {
int n, m, T;
scanf( "%d%d", &n, &m );
T = n+m;
for( int i=; i<=n; i++ ) {
pr[i][] = ;
scanf( "%d", pr[i]+ );
disc[++ntot] = pr[i][];
}
for( int i=; i<=n; i++ )
scanf( "%d", pr[i]+ );
for( int i=n+; i<=T; i++ ) {
char opt[];
scanf( "%s", opt );
pr[i][] = opt[]=='I' ? :
opt[]=='D' ? : ;
if( pr[i][]== ) {
scanf( "%d%d", pr[i]+, pr[i]+ );
disc[++ntot] = pr[i][];
} else if( pr[i][]== ) {
scanf( "%d", pr[i]+ );
} else {
scanf( "%d%d", pr[i]+, pr[i]+ );
}
}
sort( disc+, disc++ntot );
ntot = unique( disc+, disc++ntot ) - disc - ;
for( int i=; i<=T; i++ ) {
pr[i][] = lower_bound( disc+, disc++ntot, pr[i][] )-disc;
if( pr[i][]== )
pr[i][] = lower_bound( disc+, disc++ntot, pr[i][] )-disc;
}
root = build( , ntot );
for( int i=; i<=T; i++ ) {
if( pr[i][]== ) {
modify( root, pr[i][], pr[i][] );
} else if( pr[i][]== ) {
modify( root, pr[i][], oo );
} else {
int u = pr[i][];
int v = pr[i][];
printf( "%d\n", disc[lca(u,v)] );
}
}
}