[可持久化平衡树]洛谷5055【可持久化文艺平衡树】题解
题目概述Luogu5055解题报告带tag的可持久化平衡树，Pushdown需要在新建的节点上进行，并且Pushdown需要新建两个儿子，以避免影响之前的信息。好像看到了很多Pushdown在原...
[可持久化平衡树]洛谷3835【可持久化平衡树】题解
题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。未解之谜：Split肯定需要新建节点，但是Merge好像并不需要？洛谷这...
[线段树二分+树状数组]2020 ICPC 澳门 J【Jewel Grab】题解
题目概述Jewel Grab解题报告因为 $k\le 10$ ，其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置（没有就记成 $0$ ），如果不能跳过，那么一定是在...
[Splay+并查集]AGM 2020 Qualification Round【Unpredictable Tree】题解
题目概述CFGYM102566L解题报告如果没有询问路径就是很裸的平衡树维护DFS序，对于每个节点维护入栈节点 $x_{in}$ 和出栈节点 $x_{out}$ ，就可以方便的维护出DFS序。套...
[三维不重复数点]2022牛客暑期多校训练营4 E【Jobs (Hard Version)】题解
题目概述Jobs (Hard Version)解题报告首先我们先考虑二维不重复数点问题：不难发现按照 $x$ 排序后，只有 $y$ 递降的那些点是有用的，其他点肯定都被包含在了某些点中。假设前一...
[Splay维护序列]Codeforces GYM103145F【Permutation】题解
题目概述CF GYM103145F解题报告其实两个反转操作是独立的，我们可以用两棵Splay来维护位置的序列（A树）以及数值的序列（B树）。每次询问位置 $i$ 的时候，我们先找到 $i$ 位置...
[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解
题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的，所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并，考虑用set维护一个块的最大值，并查集合并的时候set启...
[cdq分治+动态凸包]HDU5127【Dogs' Candies】题解
题目概述HDU5127解题报告我们分析在甜度热爱为 $x$ ，酸度热爱为 $y(y>0)$ 时，$A(p_1,q_1),B(p_2,q_2)(p_1<p_2)$ 中 $A$ 比 $B...
[动态凸包]Codeforces70D【Professor's task】题解
题目概述动态加点维护凸包，每次询问 $(x,y)$ 是否在凸包中。解题报告终于写了下动态凸包……其实就是用set维护凸包中的点，动态做Andrew算法。我用的是水平序，维护上下两个凸壳（这里有技...
数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内，所以可以把值域也分块，这样移动指针就不需要带 $l...
