常见数据结构与维护策略

$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思想

括号相关

常见图论问题

常见字符串问题

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

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

最长回文子串

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

可以manacher

模式匹配

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

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