[可持久化平衡树]洛谷5055【可持久化文艺平衡树】题解
题目概述Luogu5055解题报告带tag的可持久化平衡树，Pushdown需要在新建的节点上进行，并且Pushdown需要新建两个儿子，以避免影响之前的信息。好像看到了很多Pushdown在原...
[可持久化平衡树]洛谷3835【可持久化平衡树】题解
题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。未解之谜：Split肯定需要新建节点，但是Merge好像并不需要？洛谷这...
[主席树二分+复杂度分析]牛客IOI周赛28-提高组 C【下克上の天邪鬼】题解
题目概述下克上の天邪鬼解题报告顺着 ${\lfloor{a_i\over 2}\rfloor}\le a_j<a_i$ 想，不难想到利用这个 $\lfloor{a_i\over 2}\rf...
[Splay+并查集]AGM 2020 Qualification Round【Unpredictable Tree】题解
题目概述CFGYM102566L解题报告如果没有询问路径就是很裸的平衡树维护DFS序，对于每个节点维护入栈节点 $x_{in}$ 和出栈节点 $x_{out}$ ，就可以方便的维护出DFS序。套...
[后缀自动机+线段树合并]Codeforces1037H【Security】题解
题目概述CF1037H解题报告算法不难得出：对于 $x$ 的每个前缀 $x[1,i]$ ，往后添加一个比 $x_{i+1}$ 大的字符 $ch$ ，$i$ 越大 $ch$ 越小得到的答案就越小。...
[广义后缀自动机+DP+单调队列]洛谷4022(CTSC2012)【熟悉的文章】题解
题目概述Luogu4022解题报告不难想到二分答案 $mid$ ，然后求 $L\ge mid$ 是否可行。令 $K={\lfloor{len\over 10}\rfloor}$ ，那么舍弃的位置...
[广义后缀自动机]Codeforces316G3【Good Substrings】题解
题目概述CF316G3解题报告用广义后缀自动机做可以避免很多复杂的情况。把 $s$ 和所有 $p$ 都扔进广义SAM里，然后把 $s$ 扔进SAM匹配得出所有属于 $s$ 的节点（注意 $fai...
[后缀自动机+线段树合并]HydroH1079【‘Minami Kotori’ Pantw 和他的召唤物二元葡萄】题解
题目概述HydroH1079解题报告建出SAM，找到 $[A,B]$ 对应节点 $p$ ，然后在 $p$ 的 $Right$ 集合上考虑。$[C,D]$ 中出现 $[A,B]$ 的子串比较难算，...
[离线+线段树+堆]洛谷4747(CERC2017)【Intrinsic Interval】题解
题目概述Luogu4747解题报告找性质题过于困难……首先很明显，如果两个合法区间有重叠部分，那重叠部分一定也是合法的。更进一步，根据这个性质可以得知答案一定是唯一的，否则两个答案区间的重叠部分...
[思维+后缀数组+调和级数]LOJ2083【「NOI2016」优秀的拆分】题解
题目概述LOJ2083解题报告想了很久匹配做法，不会做，实际上是性质题……如果能求出 $pre_i$ 表示以 $i$ 结尾的 $AA$ 个数和 $suf_i$ 表示以 $i$ 开头的 $BB$ ...
