鉴于许多数据结构题都是一些套路的组合，把一些坑过本人的 trick 记录下来。
在没有特别说明的情况下，$n$ 均为维护元素个数，$W = 10^9$。
可重集
$O(1)$ 单点加删，$O(\sqrt{n})$ 第k大，值域 $O(n)$
对值域分块，询问枚举答案在哪一块即可。
$O(\sqrt{n})$ 单点加删，$O(1)$ 第k大，值域 $O(W)$
按顺序每 $\sqrt{n}$ 个数分一块，块状链表保证加删点后每个块长不变即可。
$O(1)$ 单点删除，均摊 $O(1)$ 查某数前驱，值域 $O(n)$
维护下每个数的前驱与这个数是否仍存在，不存在就继续往前跳，每个数被删只会改变 1 个数的前驱，故均摊 $O(1)$。（没发现怎么搞单点加入）
$O(\sqrt{n})$ 单点加删，均摊 $O(1)$ 查某数前驱，值域 $O(n)$
对值域分块，对每一块维护这一块之前有数的第一块，块内每个数维护块内前驱。
加入删除暴力重构该块内部关系与该块与其他块之间关系。
至于能不能做到两种操作均 $O(1)$，我也不知道。
$O(\log W)$ 全体加值，$O(\log W)$ 查与某数异或所得最值，值域 $O(W)$
一棵 trie 搞定，细节可以现场推。（记这个是因为某次把全体加值当成了两个log的）
树
对每个节点最大化其子树外大小 $O(1)$ 点集的价值
假如我们可以复杂度较优地维护节点的集合，并支持加入节点与求出节点集合中价值最大的点集，则可以先对全树求出价值最大的点集。容易发现只有价值最大的点集中的 $O(1)$ 个节点到根的路径的答案不确定。
对于一条从根出发的路径，显然可以再次维护节点集合，在 $O(n)$ 次加入后得出该路径上每个节点的答案。
其他小东西
一些和为 $n$ 的非负整数中，不小于 $\sqrt{n}$ 的最多 $\sqrt{n}$ 个。
$\sum\limits_{x\cdot y\le n} 1 = O(n\log n)$