总结一些最近见到的 TRICK

总结一些最近见到的 TRICK：

1. 并查集 $O(n+m)$ 解决区间合并问题 3115. 疯狂的馒头。

2. 滑动窗口枚举到 $i$ 点时求 $[i-k,i-j]$ 中的最值。

3. 单调栈求距离自身最近的最右的某个值需要倒序。

4. 枚举矩阵有 4 个自由度，可以通过枚举上下两个边界将矩阵变成 1 维的，在用二分或双指针实现 $O(n^3)$ 遍历。

5. 给定一个 $n\ast m$ 的矩阵 求一个 $c\ast c$ 大小的子矩阵中的最值。可以用二维滑动窗口实现。核心思路还是二维看成一维。先每一行求一个长度为 $c$ 的滑动窗口，在每一列求一个长度为 $c$ 的滑动窗口，最后枚举答案。

6. DP的本质是组合数学，可以通过0/1背包，完全背包的思路推导组合数学中组合数公式和可重集组合公式。

7. 区间合并问题要记住一些智慧数据，区间合并可以 $O(n)$ 实现，左端点从小到大排序。

8. unorder_map,均摊 $O(1),最坏O(n)$ , 快排是均摊 $O(nlogn),最坏O(n^2)$可以通过初始化大小防止被卡，（CF除外，需要mt19937）

9. 区间合并有3种做法，并查集，贪心，离散化+差分。

10. 刷表法可以求解背包问题 $K$ 优解。

11. 给定一个矩阵，求带限制的最大的子矩阵的面积，还是每一行单独考虑，跑 $n$ 次 单调栈。

12. 给一堆东西染色求最后的颜色，可以倒着考虑。

13. 很多求树上问题的思路来源都是 树的重心 还有 树的直径。

14. 许多问题要逐步分解，如果没有思路，可以尝试，画图找规律和性质，二分答案转成判定，等

15. 双指针关键（其实写多了就没啥关键不关键的了），定义 $j=f[i]$ , 如果 $i$ 确定之后，$j$ 只能单调向左（没见过）/右移动，就可以直接双指针了。while循环里边是否定条件。

16. 矩阵上求最值除了求 $n$ 遍单调队列还可以二维 $ST$ 表。

17. 线段树指针写法，new 超慢，可以定义静态的节点再用一个移动一位。

18. $LCA$ 有 $tarjan$ ，并查集，倍增 三种写法， 至少会背一个。

19. 如果两个区间$[l_1,R_1],[R_1+1,R_2]$ 想多空一个间隔，可以下标乘2。 有点sb

20. 二维一维化可以传二维数组的一维进去，但是要是按照列来做呢？要么重写一个，要么把数据先按照列拿出来，再传进去。

21. 有的时候我会把DP状态表示的太死，然后发现状态转移方程完全写不出来，可以退一步，让DP多带一维信息，再试试。比如，一定选，一定不选。

22. 可行性DP，可以用 bitset 装逼实现。

23. 一些已知中序遍历和xx遍历，输出bfs序的题，在dfs里边穿一个层，就能直接记录下bfs序。
    笛卡尔树 。