2018睿集训提高班day2dp分治

1、分治Scape分治核心：化在线为离线分治一般分治树分治CDQ分治对时间分治线段树分治特殊二分整体二分陈老师二分分治主要思想一般分治例1. IOI2017练习赛 Mountains你有一段山脉为n个点的折线，第i个点在(i,yi)的位置，两个点不可见当且仅当其间存在一个点严格高于两点连线。求最多的互相不能看见的点。n 2000.最高点能看到的点之间的区间是独立的，然后分治？例2. 吃特色菜2给一个长度为n的序列，求所有区间最大值乘以最小值的和。N 500000.分治，处理过中心的区间例3. 动态最大全1正方形N*N的01点阵，K个操作，每次操作把某个位置变为0，维护最大全1子正方形。N 1000

2、; K 1000.切长边？维护过切割线的答案！例4. tourist一个N*M的带权网格图，K组询问两点最短路。N,M 200; K 50000.记录分治线最短路信息？树分治统计过根的答案通过采用重心使得对整棵树dfs成为可能单层计算采用dfs+data structure或者dp例5. 质数长度路径统计给一棵N个点无权树，求长度为质数的路径数目。N 100000.分治+FFT例6.采药人路径问题采药人的药田是一个树状结构，每条路径上都种植着同种药材。采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。采药人每天都要进行采药活动。他选择的路径是很有讲究

3、的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。本题可以考虑树的点分治。问题就变成求过根满足条件的路径数。路径上的休息站一定是在起点到根的路径上，或者根到终点的路径上。如何判断一条从根出发的路径是否包含休息站？只要在dfs中记录下这条路径的和x，同时用个标志数组判断这条路径是否存在前缀和为x的节点。这样我们枚举根节点的每个子树。用fi01，gi01分别表示前面几个子树以及当前子树和为i的路径

4、数目，0和1用于区分路径上是否存在前缀和为i的节点。那么当前子树的贡献就是f00 * g00 + f i0 * g -i1 + fi1 * g-i0 + fi1 * g-i1，其中i的范围-d,d，d为当前子树的深度。例7. 紫荆花之恋一棵树，每个点有一个权值Ri，求多少点对满足dist(u,v)Ru+Rv，每次加点，强制在线。N 100000.替罪羊树思想维护树分治结构CDQ分治例8. 逆序对计数给一个长度为N的序列，求逆序对数目。N 100000.经典题例9. 三维偏序在长度为N的序列中求最大子序列使得ai,bi属性同时递增。N 100000.CDQ分治，每层按ai排序后树状数组维护。例1

5、0 百度地图的实时路况定义d(u,v,w)为从u号点出发，严格不经过v号点，最终到达w号点的最短路径长度，如果不存在这样的路径，d(u,v,w) 的值为-1。计算每个d（u,v,w)n 300例11.Package有N个物品，每个物品的重量是Wi,价值是Gi每个物品只能取一个给定Q个询问，每个询问由两个数(X,I)组成给定最大容量为X的背包，使用除了第i件物品以外的所有物品，能够得到的最大价值之和N=100询问中的X=10000Q=1000000例12. Cash维护DP方程Fi=maxFj+aixj+biyjN 100000.平衡树维护凸包？分治离线扫凸包。对时间分治操作-询问类维护问题，有

6、些情况下可以采用对时间分治：除了要满足离线问题可解之外，还要满足三个强度依次减弱的条件：多个操作对询问的贡献是可加的多个操作对询问的贡献是无序的前面操作对后面操作的影响是可计算的一般采用分治处理左边的问题处理左边操作对右边询问的影响预处理左边操作对右边操作的影响例13. 二维区间和M个操作，1操作给一个矩形x1,x2*y1,y2加c，2操作询问矩形和。M 100000; x1,x2,y1,y2 1000000; c 10分治，操作差分成4个二维前缀，询问差分成4个二维后缀。前缀对其二维偏序小的后缀有贡献。线段树分治在线的静态数据结构离线解决在询问区间可拆解的情况下，可以预先把询问拆到线段树节点

7、里。并在之后遍历线段树过程中离线求出答案。例14. 向量给一个长度为N的向量序列，有M个询问每次询问一个区间内和一个向量v点积最大的向量。N,M 300000.区间很难，全局能离线做吗？线段树节点的子问题是全局的？合并凸包？两个log的瓶颈在排序？排序后再插入，一个log。例15. 踩气球N个盒子第i个盒子里有ai个气球，M个孩子每个孩子有自己的区间，如果一个孩子自己的区间内所有气球都被踩爆了他就会很高兴，Q个操作，每次选一个盒子踩一个气球问有多少个孩子高兴。N,M,Q 100000.把孩子的区间扔到线段树上。时间线段树把对时间分治的结构用线段树保存下来，离线处理。例16. 离线动态图插入边删

8、除边询问两个点连通性，可以离线，N个点M个操作。N,M 200000.每条边是个时间区间对时间建线段树。在线段树上打标记用带撤销并查集维护no路径压缩，按秩合并例17. 网络在树上插入一条链，删除一条链（链有权），求目前存在的经过某个点的链中的最大权值。N,M 100000.每条链是一个时间区间。暴力虚树/LCT整体二分有时候问题是可以二分的，然而判定太慢了把判定过程中与询问无关的部分进行预处理，可以加速判定时间。不妨将所有询问离线后一起处理。预处理+处理判定的时间复杂度必须和当前答案区间内询问数+答案数相关，与全部询问数和答案数无关。例18. Storm例19. K大数查询有n 个位置和m 个操作。操作有两种，每次操作如果是1 a b c 的形式，表示往第a 个位置到第b 个位置每个位置加入一个数c。如果操作形如2 a b c 的形式，表示询问从第a 个位置到第b 个位置，第c 大的数是多少。n,m=50000陈老师二分例20. 地壳运动N个点M条边，每条边有u,v两个权值，每次给出k1,k2，求权值为k1u+k2