题目链接 题解 最近学后缀数组学得有点晕，还是要多练啊。 题目就一句话：求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。 根据容斥原理，只要分别求出两个子串合并后的答案和两个子串单独的答案，最后的答案就是它们…

题目链接 题解 题目大意：求最小不重复相同子串。 考虑把两个字符串合并起来，求出sa，rk和Height数组。 我们可以从小到大枚举子串长度k，然后再枚举后缀。 具体来说，我们是根据子串字典序从小到大枚举后缀的 如果He…

题目链接 题解 看到这个首发平台就觉得是rainbowcat出的题，一看题面——都有Freda了，就确定是rainbowcat出的了。 这一题第一次写我写挂了orz 由于与运算和或运算在每一位上都是独立的，我们可以考虑对…

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

题目链接 题解 又是一道题一晚上系列(数据结构一生之敌) 调了很久的原因其实是写错了一个变量,其实还是很简单的 这里用的平衡树是Treap 你可以把原始数列看成n个链表,首尾相连的那种,但是我们要分段存 用vector就…

题目链接 题解 这道题一开始用的是Treap写的,死活调不出来,题解又全是指针的 然后就用splay来写,发现思路自然了许多 引用自FlierKing 平衡树，需支持五个操作： 1. 将某元素置顶：将元素旋到根，然后将左…

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

题目链接 题解 这个淀粉质点分治有点意思，与其他的点分治的题目不同的是，这题目并没有让你费劲心思怎么去用log的复杂度进行内层的统计，而是让你想到如何确定当前答案是否最优。 （下面不会讨论点分治的具体实现，此题不适合作为…

导言 淀粉质点分治是一种统计方法，具体来说，是对树上的点的一些值来进行统计，标准的点分治统计复杂度为 O(Nlog^2N) 是解决树上疑难杂症的不三之选（还有一个是树形dp） 算法思路&&具体问题 【洛谷…

T1 增援前线 实锤乱搞题，考试的时候写了一个错误的dp，只拿了一半的分。 实际上这一题应该属于贪心吧 我们用f[i]表示i号点能站多少人。 显然，前l个点的f[i]=a[i]； 对于其他情况，f[i]应由i-l到i-1…