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

题目链接 题解 题目大意：给两个串，S，T，问S中有多少个子串与T的差异是在3个字符以内的。 这道题解法有很多，像什么SAM，FFT，NTT之类的，然而我只会哈希orz 二分找它们的最长公共前缀，最多能跳3次，没了…… 设N为S的长度，M为T的长度 时间复杂度 $O((N-M)\times (logM))$ 代码 [crayon-67ece6ec8…

题目链接 题解 哈希真的是个好东西,在O(N)预处理之后,能在O(1)的时间内枚举任意子串. 这道题我们可以考虑对每种字母进行哈希. 具体来讲,hash1[i][c]存储的是字母c的哈希值(位置) 这样处理之后,就在S串里面枚举长度为T串的子串,再枚举两种字母,如果26个字母哈希值能够相等,那么这样的变化是没问题的 时间复杂度 $O(N\times…

题目链接 题解 $f[i][j]$ 表示 当前串为第j个位置到第i个位置的串的方案数 $O(n^3)$ 做法 $ f[i][j]=\sum_{j-k< i-j}f[j][k]$ 若 $s(k+1,j)< s(j+1,i),j-k=i-j$ 则 $f[i][j]+=f[j][k]$ $O(n^2)$ 做法 考虑 $O(1)$ check …

题目链接 题目大意 中国剩余定理"裸题" 这就当是我对(扩展)中国剩余定理的总结吧,还有好多细节的方面的归纳. 中国剩余定理(CRT) 用途就是解出这类问题 我们可以先考虑模数两两互质的情况下的做法. 我们想构造出一个合式使得 $x= r_1+r_2+r_3+\cdots +r_n$ 其中 $m_i$ 可以整除除了第i项的其他项 于是我们可以通过一…

其实和余数求和是同一道题... 但是范围加大取模就有点容易载坑 还是说一下思路吧 首先我们要求的是: $$\displaystyle\sum_{i=1}^m n\ mod \ i$$ 其实取模操作特殊在没有什么特殊性 基本上看到这种形式就会想到 $n\ mod\ i=n- \left\lfloor\frac{n}{i}\right\rfloor\t…

题目链接 题解 又是一道题一晚上系列(数据结构一生之敌) 调了很久的原因其实是写错了一个变量,其实还是很简单的 这里用的平衡树是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)，…