题目链接 题解 最近学后缀数组学得有点晕，还是要多练啊。 题目就一句话：求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。 根据容斥原理，只要分别求出两个子串合并后的答案和两个子串单独的答案，最后的答案就是它们相减。 问题的关键就是如何在可以接受的复杂度内求这个答案。（我一开始连这个答案是什么都不知道） 实际上我们要求的是所有子串的lcp…

题目链接 题解 题目大意：求最小不重复相同子串。 考虑把两个字符串合并起来，求出sa，rk和Height数组。 我们可以从小到大枚举子串长度k，然后再枚举后缀。 具体来说，我们是根据子串字典序从小到大枚举后缀的 如果Height[i]不小于k（即第i-1个子串和第i个子串的最长公共前缀不小于k）， 并且如果此后缀的起始点在第一个字符串，cnt1++…

题目链接 题解 看到这个首发平台就觉得是rainbowcat出的题，一看题面——都有Freda了，就确定是rainbowcat出的了。 这一题第一次写我写挂了orz 由于与运算和或运算在每一位上都是独立的，我们可以考虑对每一位进行计算。 我们先考虑与运算（其实两个运算是一样的） 于是就成了一个求一个矩阵中，有多少个0/1子矩阵，我们可以考虑用单调栈…

题目链接 题解 一道线段树模板题，离散化需要注意下，居然交了10次，丢人…… 细节还是很多的，最近都在写平衡树，一开始把线段树写成和权值树那样的分治方法了orz 代码 [crayon-68274a9cb235a112438509/]

题目链接 题解 又是一道题一晚上系列(数据结构一生之敌) 调了很久的原因其实是写错了一个变量,其实还是很简单的 这里用的平衡树是Treap 你可以把原始数列看成n个链表,首尾相连的那种,但是我们要分段存 用vector就很舒服 然后对于第三个操作,其实只要每次进入平衡树的元素查找下前驱后继与它本身作差取最小值即可(这里的前驱后继是非严格的) 对于第…

题目链接 题解 这道题一开始用的是Treap写的,死活调不出来,题解又全是指针的 然后就用splay来写,发现思路自然了许多 引用自FlierKing 平衡树，需支持五个操作： 1. 将某元素置顶：将元素旋到根，然后将左子树合并到该元素的后继 2. 将某元素置底：将元素旋到根，然后将右子树合并到该元素的前驱 3. 将某元素提前/滞后1位：直接与该元…

题目链接 题解 这道题坑了我好久,其实不难,就是有个地方与模板不一样导致错误(死背模板的后果) 考虑用splay维护区间翻转,每次的翻转左边界是确定的,而右边界则是第i小的数所在位置 输入存在a数组里,按高度排序,每次我们就取出a[i].id,它的位置作为右边界,每次输出它的size 由于每次都单独地splay(a[i].id,rt) ,所以旋转的…

题目链接 题解 这个淀粉质点分治有点意思，与其他的点分治的题目不同的是，这题目并没有让你费劲心思怎么去用log的复杂度进行内层的统计，而是让你想到如何确定当前答案是否最优。 （下面不会讨论点分治的具体实现，此题不适合作为点分治入门题） 在此我们可以将情况分为两种： 1. 点对内 如图，我们的树长这样（假设边权全部为1），标红的是一对点对(6,7)，…

导言 淀粉质点分治是一种统计方法，具体来说，是对树上的点的一些值来进行统计，标准的点分治统计复杂度为 $O(Nlog^2N)$ 是解决树上疑难杂症的不三之选（还有一个是树形dp） 算法思路&&具体问题 【洛谷P3806】点分治 给你一棵树，有m个询问，每个询问包含一个k，问树中是否存在距离为k的点对 这是一道很好的模板题，在这道题里…

T1 增援前线 实锤乱搞题，考试的时候写了一个错误的dp，只拿了一半的分。 实际上这一题应该属于贪心吧 我们用f[i]表示i号点能站多少人。 显然，前l个点的f[i]=a[i]； 对于其他情况，f[i]应由i-l到i-1这段区间内的点更新而来。 具体来说，就是“能跳则跳，满员为止” 我们优先选择距离当前点较远的点来更新，下面将证明这一结论。 我们每…