离线

1.把询问有序化来方便处理。

在考虑离线算法的时候应该往[如何把随机的询问转化后有序的询问]去考虑。莫队和cdq分治都是一种调整性有序,区间拆法也是使询问有序的方法。对于树上的问题还可以处理成dfs序的形式变得有序。

典中点:[CSP-S2020] 儒略日

然而有的时候把问题变成有序并不是一件很直观的事情。可能需要转换一个视角,反复尝试对题目中出现的每一个变量枚举的道路是否走得通。对于不是用枚举来处理的其他变量,可能是直接扫过去,也可能掺杂着一些其他的东西(桶,莫队等等)或者数据结构(并查集,线段树/树剖,平衡树左偏树等等)来辅助维护。

例题:

P1967 [NOIP2013 提高组] 货车运输

P1600 [NOIP2016 提高组] 天天爱跑步

P4216 [SCOI2015]情报传递

P4211 [LNOI2014] LCA 

2.把形态固定化来省略维护

有的时候问题中不止要求维护询问功能,可能还会有添加/删除等操作

这个时候可以通过离线来吧每一个时刻的研究对象固定化来方便处理

这个想法已经有了一种典型的优化技巧,叫做线段树分治。

例题:

P4219 [BJOI2014]大融合

3.把操作进行压缩性延迟处理后统一进行降低总操作量

简称:差分(树上差分)。

4.对所有可能形式进行统一化处理

一种见到的是 把路径的信息转化成路径端点到根节点的信息并来降维

例题:

P4551 最长异或路径

5.直接推测答案的值

二分答案/整体二分(就是一个询问/多个询问)。最典型的就是[最大值的最小值]和[最小值的最大值]。有的时候询问只会写出一个最值(“求出最大值/最小值”),但是可以考虑答案如果有单调性,那么同样可以去二分答案。

例题:

P2680 [NOIP2015 提高组] 运输计划

6.对区间/树上路径询问共性处理

分治是一种很优秀的优化技巧

序列上可表现为中点分治,树上可以表现为点分治。

带有一些特殊性质的题目,往往用分治可以得到很好的处理结果。

① 多次离线询问区间/树上路径

例:

P3373 【模板】线段树 2 

 FJOIP-J2022 T4幸运区间

② 维护的信息带有易于插入,但不易于合并的性质

例如背包,线性基等等

容易想到的处理方法如同求和一般是直接建一棵线段树/树链剖分,但是有时候built的时间复杂度就让人难以接受(O(n*合并))

于是采用从中间一分为二,来大幅减少合并的需要

例:

双端栈 

T228288 C. 树上背包 【省选计划 · 模拟赛 #7】