[可持久化平衡树]洛谷3835【可持久化平衡树】题解
题目概述Luogu3835解题报告由于非旋Treap的Split和Merge都是自上而下的操作，因此可以很方便的可持久化。未解之谜：Split肯定需要新建节点，但是Merge好像并不需要？洛谷这...
[线段树二分+树状数组]2020 ICPC 澳门 J【Jewel Grab】题解
题目概述Jewel Grab解题报告因为 $k\le 10$ ，其实就是个暴力题。记录 $pre_x$ 表示 $x$ 前面第一个颜色相同的位置（没有就记成 $0$ ），如果不能跳过，那么一定是在...
[主席树二分+复杂度分析]牛客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解题报告找性质题过于困难……首先很明显，如果两个合法区间有重叠部分，那重叠部分一定也是合法的。更进一步，根据这个性质可以得知答案一定是唯一的，否则两个答案区间的重叠部分...
[离线+ODT+扫描线+线段树]2022 CCPC 广州 B【Ayano and sequences】题解
题目概述Ayano and sequences解题报告其实并不是很难，但感觉考场上性价比不高 🤔 ，也可能只是我们队做的太慢了 😭 。这个问题如果在线做会发现涉及到时间和区间两个维度，并不是很好...
