KMP字符串

一. AcWing831_KMP字符串 二. 理论 1. kmp原理 2. 循环节 KMP算法中最重要的就是next数组,next[i]表示是字符串中所有以 i 为结尾的非前缀子串中与前缀能匹配的长度的最大值。可能有点绕,缕一缕吧,这就是next[ ]数组的定义而已。 我们求最小循环节也是利用nex


朴素KMP

一. 模式串匹配 KMP字符串_理论 二. DP


教主的魔法

一. 洛谷P2801_教主的魔法 二. 思路 若每个块内有序, 我们可以利用二分,logn算出这个块对答案的贡献 所以对每个块, 多维护一个s数组,里面是当前块内的所有值的有序数组 对于修改操作,不完整的块直接暴力判断,然后排序对s数组,根号n*logn 完整的块直接累加懒标记, 显然整块加并不会改


块状数组

一个简单的整数问题2_理论 教主的魔法_区间修改+求区间>=x数的个数


一个简单的整数问题2

一. AcWing243_一个简单的整数问题2 二. 理论 三. 代码 #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #includ


单调栈

一. AcWing830_单调栈 二. 理论 每次将当前元素和栈顶比较, 若栈顶元素>=当前数,则栈顶永远不可能是答案,出栈 直到栈顶元素<当前数,将当前数入栈 每次栈顶就是当前数嘴边小于他的数最近的 三. 代码 #include<iostream> #include&


单调栈

单调栈_理论_求数左边或右边第一个比他大或小的数