[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$ 越小得到的答案就越小。...
[广义后缀自动机]Codeforces316G3【Good Substrings】题解
题目概述CF316G3解题报告用广义后缀自动机做可以避免很多复杂的情况。把 $s$ 和所有 $p$ 都扔进广义SAM里，然后把 $s$ 扔进SAM匹配得出所有属于 $s$ 的节点（注意 $fai...
[NTT]Codeforces528D【Fuzzy Search】题解
题目概述CF528D解题报告奇怪的字符串匹配，并且字符集很小，考虑卷积。对于字符 $ch$ ，如果 $S$ 的 $i$ 位置是 $ch$ ，说明 $[i-K,i+K]$ 这些位置都可以匹配。令 ...
[后缀自动机+线段树合并]Codeforces GYM102411L【Lengths and Periods】题解
题目概述给一个字符串 $S$ ，选一个子串 $T$ ，使 ${T\over T-Border(T)}$ 最大。解题报告每个串的Border并不好考虑，但是可以考虑枚举Border，然后去找子串。...
[长链剖分+DP]Codeforces1009F【Dominant Indices】题解
题目概述CF1009F解题报告定义 $f_{i,j}$ 表示 $i$ 子树内到 $i$ 距离为 $j$ 的个数，则显然 $f_{i,0}=1,f_{i,j}=\sum_{u\in son(i)}...
[思维+Palindrome Series]Codeforces932G【Palindrome Partition】题解
题目概述CF932G解题报告首先原题意有点恐怖，我们需要进行一定的转化。原题意需要分成偶数个串，然后前后对称相同，如果我们把串的后一半翻转，那么就会发现前后对应的两个字符串是互相翻转的。进一步转...
[离线+分块+Tarjan缩点+bitset维护传递闭包]The 19th Zhejiang Provincial Collegiate Programming Contest K【Dynamic Reachability】题解
题目概述CF GYM103687K解题报告科技题过于困难。考虑离线，如果我们把询问分成若干个长度为 $BLK$ 的块，那么块中最多涉及到 $BLK$ 条边，$2BLK$ 个点。这样就可以大大减小...
[矩阵乘法+线段树]Codeforces1701F【Points】题解
题目概述CF1701F解题报告对于 $x$ ，设 $[x-d,x-1]$ 上共有 $cnt$ 个点，那么以 $x$ 作为结尾的三元组个数为 ${cnt\choose 2}={1\over 2}(...
[Splay维护序列]Codeforces GYM103145F【Permutation】题解
题目概述CF GYM103145F解题报告其实两个反转操作是独立的，我们可以用两棵Splay来维护位置的序列（A树）以及数值的序列（B树）。每次询问位置 $i$ 的时候，我们先找到 $i$ 位置...
