题目描述
志向远大的YY小朋友在学完快速排序之后决定学习平衡树，左思右想再加上SY的教唆，YY决定学习Treap。友爱教教父SY如砍瓜切菜般教会了YY小朋友Treap（一种平衡树，通过对每个节点随机分配一个priority，同时保证这棵平衡树关于priority是一个小根堆以保证效率）。这时候不怎么友爱的510跑了出来，他问了YY小朋友一个极不和谐的问题：怎么求Treap中两个点之间的路径长度。YY秒了之后决定把这个问题交给你来做，但只要求出树中两点的LCA。
输入
第一行两个整数n，m
第二行n个整数表示每个元素的key
第三行n个整数表示每个元素的priority
接下m行，每行一条命令
I A B，插入一个元素，key为A, priority为B
D A，删除一个元素，key为A
Q A B，询问key分别为A和B的LCA的key
输出
对于每个Q输出一个整数。
样例输入
2 1
1 2 4 5 Q 1 2样例输出
1
题解
权值线段树
一个小结论：不妨设$a\le b$，则Treap中权值为$a$、$b$两点的LCA为权值在$[a,b]$之间，优先级最小的点。
证明：
1.LCA的权值在$[a,b]$之间：考虑从$a$、$b$找到LCA的最后一步：一定是$a$在LCA的非右子树，$b$在LCA的非左子树。否则$a$、$b$在同子树内则LCA可以为更优的该儿子节点。
2.权值在$[a,b]$之间的节点一定都在LCA的子树内：如果不在LCA的子树内，那么节点如果在LCA右侧则一定大于$b$，或在LCA左侧则一定小于$a$。
3.LCA的子树中所有节点的优先级都小于等于LCA：证明显然。
4.LCA一定在LCA的子树内：证明显然。
因此由1、2、3、4得证。
于是只需要对每个数的key维护权值线段树，维护权值在某区间内的数的优先级最小值及其位置。查询时直接区间查询即可。
为了避免一些细节问题（比如两个int加起来爆int之类的），代码中使用了离线离散化。
时间复杂度$O(n\log n)$。
#include#include #include #define N 100010#define lson l , mid , x << 1#define rson mid + 1 , r , x << 1 | 1#define id(x) lower_bound(v + 1 , v + tot + 1 , x) - v#define inf 0x7fffffffusing namespace std;typedef pair pr;int key[N] , pri[N] , opt[N * 3] , qx[N * 3] , qy[N * 3] , v[N << 2] , tot;pr mn[N << 4];char str[5];void build(int l , int r , int x){ mn[x] = pr(inf , inf); if(l == r) return; int mid = (l + r) >> 1; build(lson) , build(rson);}void insert(int p , int v , int l , int r , int x){ if(l == r) { mn[x] = pr(v , p); return; } int mid = (l + r) >> 1; if(p <= mid) insert(p , v , lson); else insert(p , v , rson); mn[x] = min(mn[x << 1] , mn[x << 1 | 1]);}void erase(int p , int l , int r , int x){ if(l == r) { mn[x] = pr(inf , inf); return; } int mid = (l + r) >> 1; if(p <= mid) erase(p , lson); else erase(p , rson); mn[x] = min(mn[x << 1] , mn[x << 1 | 1]);}pr query(int b , int e , int l , int r , int x){ if(b <= l && r <= e) return mn[x]; int mid = (l + r) >> 1; pr ans(inf , inf); if(b <= mid) ans = min(ans , query(b , e , lson)); if(e > mid) ans = min(ans , query(b , e , rson)); return ans;}int main(){ int n , m , i; scanf("%d%d" , &n , &m); for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &key[i]) , v[++tot] = key[i]; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &pri[i]); for(i = 1 ; i <= m ; i ++ ) { scanf("%s%d" , str , &qx[i]); if(str[0] == 'I') opt[i] = 1 , scanf("%d" , &qy[i]) , v[++tot] = qx[i]; else if(str[0] == 'D') opt[i] = 2; else opt[i] = 3 , scanf("%d" , &qy[i]); } sort(v + 1 , v + tot + 1); build(1 , tot , 1); for(i = 1 ; i <= n ; i ++ ) insert(id(key[i]) , pri[i] , 1 , tot , 1); for(i = 1 ; i <= m ; i ++ ) { if(opt[i] == 1) insert(id(qx[i]) , qy[i] , 1 , tot , 1); else if(opt[i] == 2) erase(id(qx[i]) , 1 , tot , 1); else if(qx[i] < qy[i]) printf("%d\n" , v[query(id(qx[i]) , id(qy[i]) , 1 , tot , 1).second]); else printf("%d\n" , v[query(id(qy[i]) , id(qx[i]) , 1 , tot , 1).second]); } return 0;}