YY的Treap
时间限制:10s 空间限制:128MB
题目描述
志向远大的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 2 1 2 4 5 Q 1 2 I 3 3
样例输出
1
提示
数据保证n<=10^5,m<=3*10^5
其余整数均不超过long的范围
数据保证任意时刻树中key和priority均不相同
题目来源
没有写明来源