常见数据结构与维护策略

$O(n)$表达式求值

双队列

$O(n)$维护一些分裂或者合并具有单调性的更新,如:合并果子、定比例切断、二路归并

单调队列单调栈

$O(n)$离线计算序列中每个位置之前出现的第一个比当前位置值小(单调增栈)或者大(单调减栈)的位置

$O(n)$离线计算带限制的最大子段和

$O(n)$离线计算横坐标单调的情况下的凸包

链表

对于具有可以转化为删除的性质的问题或许有奇效,有序的链表其前驱和后继记录了与当前值最接近的值

优先队列

$O(n\log n)$计算哈夫曼编码

可以用来维护带反悔的贪心,例如两两不相邻的最小k个元素的和

$O(\log n)$动态维护最小值

可并堆

$O(\log n)$合并两个堆

哈希

映射有用的信息,保持一定的可识别性

常用P: 131 13331 13131

常用MOD: 998244353 1e9+7

也可以采用unsigned long long自然溢出,可以双哈希

性质:$H(T)=(H(S+T)-H(S)*P^{length(T)})\mod MOD$

字典树

$O(ns)$计算最大的两两异或

常见贪心策略

区间问题

常见DP思想

括号相关

常见图论问题

常见字符串问题

编辑距离

可进行单字符替换、单字符删除、单字符插入,从一个s变换到到t最少需要的次数,可以dp$O(mn)$求出

模式匹配

预处理hash枚举开始位置或者用kmp(字符串首字母编号为1)

kmp的nxt[i]性质:以位置i-1结尾的所有t的子串中与t的某个前缀完全匹配的最大长度是nxt[i],即从0到nxt[i]-1位置的前缀

加速kmp:nxt[i] = nxt[nxt[…[nxt[i]]]]

扩展kmp:nxt[i]代表t和t[i … m-1]的最长公共前缀长度,extend[i]代表t和s[i … n-1]的最长公共前长度

AC自动机:fail[i]指向i代表的t[0 … ch[i]]的后缀能匹配到的最长前缀t[0 … ch[fail[i]] ],可以构成fail树

最长公共前缀(判断字典序)

预处理hash后二分可以$O(\log n)$求出

最长回文子串

正序倒序预处理hash枚举中点二分端点可以$O(n\log n)$计算

manacher可以$O(n)$计算以第i个字符为中心的回文半径