进阶算法思想

单调数据结构

单调队列，单调栈都是均摊\(O(1)\)，是不支持撤销的，只能按照正常过程加入。

单调栈

求最近的大于小于其的值

CF280B Maximum Xor Secondary：枚举最大值，次大值并不容易确定，但枚举次大值的位置，这样最大值就是其左右两边第一个比其大的值，用单调栈可求出。其实就是要枚举不好确定的那个

CF1407D Discrete Centrifugal Jumps：单调栈求出处理 DP 转移的范围，反向ST表优化DP即可。

单调队列

队列的元素满足：值是单调的，位置在原序列也是单调的。（似乎就是一个LCS？？）

ABC352D Permutation Subsequence：做两个单调队列，\(\forall i\in [1,n-k+1]\) 分别求出值域 \([i,i+k-1]\) 最大最小值即可。

CF1195E OpenStreetMap：横着滑动窗口，求出横着的信息，再竖着求一遍得到矩阵信息，二维拆为两个一维

贪心（拟阵）

归纳法

每一步取到最优解

ABC236F Spices

CF1552E Colors and Interval：每 k-1为一组覆盖，使得这些不相交即可。贪心：每组一定可以选出k-1个区间，考虑数学归纳法，\(k=2\) 显然成立，\(k>2\) 时，取出第一个区间 \([l,r]\)，一定有 \([1,r-1]\) 中不存在一种颜色出现两次，因此取完后归纳到 \(k-1\) 的情况，证明成功。

交换法

原理：交换两步操作，答案不优

条件：交换两部操作，只有 \(O(1)\) 个位置发生改变。

思路：如果交换不优，则应满足条件A，那么满足条件A，则也大概率就不能交换，这样直接排序即可

P1080 国王游戏

倍增

自下向上

跳步型（有具体结构）

条件：每一步的跳跃是唯一的（形如）

比如：倍增LCA

CF1142B Lynyrd Skynyrd

CF932D Tree

拆分型

倍增处理\(2^k\) 的答案

例子：ST表

拆分的ST表可以使用二进制拆分的 \(O(\log)\) 单点查询。

CF1848F Vika ans Wiki：对于这种迭代变化的题一定尝试多次手摸找规律，或者发现进行 \(m\) 迭代时是什么样的。

分治（合治）

类完全二叉树分治

就是题目给了你一个分治结构

P7143 线段树：线段树区间定位数定理：2*区间长度-区间覆盖节点数

具体结构分治

CDQ

将 \(n\) 维静态问题变为 \(n-1\) 维静态问题。

排序可以去掉一维，CDQ常常结合最开始的排序。

扫描线将 \(n\) 维静态问题转化为 \(n-1\) 维动态问题。

CDQ优化DP

导弹拦截

KD-T复杂度

矩形查询：\(O(n^{1-\frac 1k})\)

欧几里得最近邻：\(O(玄学)\)

曼哈顿最近邻：\(\le O(n^{1-\frac 1k}\log n)\)

笛卡尔树

什么是笛卡尔树，以及笛卡尔树的应用

\(<\land > \lor\)

区间物品DP？

动量变化