原题链接：https://www.luogu.com.cn/problem/P3369题意解读：平衡树的基本操作，模版题。解题思路：1、二叉搜索树-BST二叉搜索树满足这样的性质：每一个节点的权值大于它的左儿子，小于它的右儿子。对BST进行中序遍历，将得到一个从小到大的有序序列，因此BST是为了维护一个有序序列的动态

直接抄WIDA的pbds板子#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>usingnamespace__gnu_pbds;usingnamespacestd;typedefpair<int,int>V;tree<V,null_type,less<V>,rb_tree_tag,tree_order_statistics_node_updat

写在前面推荐一个很实用的工具：红黑树可视化本文参考OIwiki中的红黑树代码，读者也可以参考该篇解析（写得还是很不错的），不过OIWiki里删除后平衡维护的Case4和Case5在代码细节上稍微有些问题（把c

原题链接题解1stl模拟，注意lowerbound的效果和pos的返回值code1#include<bits/stdc++.h>usingnamespacestd;vector<int>a;intmain(){intn;cin>>n;while(n--){intop,x;cin>>op>>x;if(op==1)a.inser

题目传送门闲话：Luogu总共105篇题解中只有4篇01Tire树解法，虽说是非正解但未免也太少了些（貌似也不少？）……总之01Tire树的效率并不低，这道题用01Tire是很轻松的。Q：这题为什么可以用01Tire树解？能否解决一个问题，无非于三个点：可行性，空间，时间。本题要求维护一个有序数集，能进行元素修改

有旋Treap模板#include<bits/stdc++.h>usingnamespacestd;structNode{ Node*ch[2]; intval,rank; intrep_cnt; intsiz; Node(intval):val(val),rep_cnt(1),siz(1){ ch[0]=ch[1]=nullptr; rank=rand(); } voidupd_siz(){ siz=

Splay参考资料题解P3369【【模板】普通平衡树】Splay树Splay简易教程splay详解（一）小蒟蒻yyb的博客

题意写一棵平衡树，需要实现如下几种操作：插入\(x\)数删除\(x\)数(若有多个相同的数，因只删除一个)查询\(x\)数的排名(排名定义为比当前数小的数的个数\(+1\))查

题目链接题目要求：插入数据，删除数据，查询数的排名，查询排名为x的数，找前驱，找后继旋转操作，左旋和右旋，旋转$x$，旋转操作一定要符合先序遍历前后一致voidrotate(intx){