简介无旋树堆(一般统称\(\text{FHQ-Treap}\))，是一种平衡树。可以用很少的代码达到很优秀的复杂度。前置知识：二叉搜索树\(\text{BST}\)\(\text{Treap}\)基本知识普通平衡树例题引入P6136【模板】普通平衡树（数据加强版）您需要写一种数据结构，来维护一些整数，其中需要提供以下操作：插入一个整数\(x\)。删除一个整数\(x\)（若有多个相同的数，只删除一个）。查询整数\(x\)的排名（排名定义为比当前数小的数的个数\(+1\)）。查询排名为\(x\)的数（如果不存在，则认为是排名小于\(x\)的最大数。保证\(x\)不会超过当前数据结构中数的总数）。求

题目传送门：https://codeforces.com/problemset/problem/527/C题意：给出一个面积为h×w的长方形，有m次操作，每次操作可以横着或竖着在某个位置砍一刀，问你在m次操作后，在所有块中面积最大的一个。思路：理解题意，就是让你求砍m次后，剩下的部分的最长的高和最长的宽，相乘就是最大面积，所以我们可以利用平衡树中的前驱和后继来求所切割点所在部分的长度，同时利用两颗平衡树来维护高和宽，再利用multiset来维护切割后的高度和宽度，每次切割时，要先在multiset中找到所要切割线段的长度，将其切割后再放回去，最后从multiset中找到最长的高和宽相乘即是所求

题目传送门：https://codeforces.com/problemset/problem/527/C题意：给出一个面积为h×w的长方形，有m次操作，每次操作可以横着或竖着在某个位置砍一刀，问你在m次操作后，在所有块中面积最大的一个。思路：理解题意，就是让你求砍m次后，剩下的部分的最长的高和最长的宽，相乘就是最大面积，所以我们可以利用平衡树中的前驱和后继来求所切割点所在部分的长度，同时利用两颗平衡树来维护高和宽，再利用multiset来维护切割后的高度和宽度，每次切割时，要先在multiset中找到所要切割线段的长度，将其切割后再放回去，最后从multiset中找到最长的高和宽相乘即是所求

「学习笔记」平衡树基础：Splay和Treap点击查看目录目录「学习笔记」平衡树基础：Splay和Treap知识点平衡树概述Splay旋转操作Splay操作插入\(x\)查询排名为\(k\)的数查询\(x\)的排名查询\(x\)的前驱查询\(x\)的后继删除\(x\)代码替罪羊树TreapFHQ_Treap树套树平衡树的区间操作例题P3391文艺平衡树思路P4036[JSOI2008]火星人思路P4309[TJOI2013]最长上升子序列思路星系探索思路代码知识点平衡树概述二叉搜索树（BST）的简单定义：根节点的左子树权值\(根节点权值\(根节点的右子树权值；左子树和右子树均为二叉搜索树。这样

「学习笔记」平衡树基础：Splay和Treap点击查看目录目录「学习笔记」平衡树基础：Splay和Treap知识点平衡树概述Splay旋转操作Splay操作插入\(x\)查询排名为\(k\)的数查询\(x\)的排名查询\(x\)的前驱查询\(x\)的后继删除\(x\)代码替罪羊树TreapFHQ_Treap树套树平衡树的区间操作例题P3391文艺平衡树思路P4036[JSOI2008]火星人思路P4309[TJOI2013]最长上升子序列思路星系探索思路代码知识点平衡树概述二叉搜索树（BST）的简单定义：根节点的左子树权值\(根节点权值\(根节点的右子树权值；左子树和右子树均为二叉搜索树。这样