#P2770. YY的Treap

    ID: 1876 传统题 1000ms 512MiB 尝试: 549 已通过: 89 难度: 5 上传者: 标签>CF1800普及+/提高-笛卡尔树LCA离线预收集坐标离散化普通线段树

YY的Treap

题目描述

志向远大的 YY 小朋友在学完快速排序之后决定学习平衡树,左思右想再加上 SY 的教唆,YY 决定学习 Treap。

Treap 是一种平衡树,通过对每个节点随机分配一个 prioritypriority,同时保证这棵平衡树关于 prioritypriority 是一个小根堆以保证效率。

友爱教教父 SY 如砍瓜切菜般教会了 YY 小朋友 Treap。这时候不怎么友爱的 510 跑了出来,他问了 YY 小朋友一个极不和谐的问题:怎么求 Treap 中两个点之间的路径长度。

YY 秒了之后决定把这个问题交给你来做,但只要求出树中两点的 LCA。

输入格式

第一行两个整数 n,mn,m。 第二行 nn 个整数表示每个元素的 key​key​。 第三行 nn 个整数表示每个元素的 prioritypriority。 接下 mm 行,每行一条命令:

  • I A B,插入一个元素,keykey 为 AA,prioritypriority 为 BB。
  • D A,删除一个元素,key​key​ 为 AA。
  • Q A B,询问 key​key​ 分别为 AA 和 BB 结点的 LCA 的 keykey。

输出格式

对于每个 Q 输出一个整数。

2 2
1 2
4 5
Q 1 2
I 3 3
1

数据规模与约定

对于 100%100\% 的数据,n≤105n\leq 10^5,m≤3×105m\leq 3\times 10^5,其余整数均不超过 int 的范围。 数据保证任意时刻树中 keykey 和 prioritypriority 均不相同。