Day4 AM 分治 离线

正睿OI

例一 IOI2017练习赛 Mountains

$Description$
　　有一段山脉为n个点的折线，第i个点在i位置，高$h_i$。两个点不可见当且仅当其间存在一个点严格高于两点连线。求最多的互相不能看见的点。
　　$n\leq 2000$。
$Solution$
　　区间最高点左右的点是独立的，以它作为分治中间点枚举选与不选？

例2.吃特色菜2

$Description$
　　给定一个长为$n$的序列，求所有区间最大值乘以最小值的和。
　　$n\leq 5\times 10^5$。
$Solution$
　　数据随机：每次选最小值作为分治中心，期望深度$O(\log n)$。对每个位置找左右第一个比它大的位置。
　　数据不随机：选中间点分治。如果固定$l$，维护中间点到$l$的区间最大值$mx_l$和最小值$mn_l$。假设$l$在$mid$左侧，该区间过中点。。忘了，反正区间$[l,r]$的贡献为$\max\{mx_l,mx_r\}\times \min\{mn_l,mn_r\}$。维护$mx_i,mn_i,mx_i\times mn_i$的前缀和。

例3.

$Description$
　　动态最大全1正方形：$n\times n$的01点阵，$K$个操作，每次操作把某个位置变为0，然后求最大全1子正方形。
　　$n,K\leq 1000$。
$Solution$
　　DP没法处理修改。
　　非DP的话，每次分治长边，（暴力）求出分治边上所有点向上下/左右都是1能延伸的最长距离。然后扫一遍就可以知道过分支边的答案。继续分下去。复杂度$O(n^2\log n)$。
　　每次修改，分治递归找到要修改的位置，顺便更新影响的点的最长延伸距离以及扫一遍更新答案。每次修改复杂度$n+\frac{1}{2}n+\frac{1}{4}n+\ldots=2n$。

ZJOI2016 Day2T2 旅行者

$Description$
　　给定$n\times m$的带边权网格图。$Q$次询问从点$(x_i,y_i)$到点$(x_j,y_j)$的最短路。
　　$n\times m\leq 2\times 10^4,Q\leq 10^5$.
$Solution$
　　对分治线上的每个点进行一次Dijkstra。若该区域点数（面积）为S，则分治线如果选择较短的一边，其上点的个数$\leq\sqrt S$。每次选较短的分治复杂度$O(S\sqrt S\log S)$，若不这样复杂度$O(S\sqrt S\log^2 S？)$。（$T(n)=T(\frac{n}{2})+O(S\sqrt S\log S)=O(S\sqrt S\log S)$？网上题解有证明。）
　　若一次询问的$(x,y)$在分治线两侧，则可以枚举分治线上的点$i$用$\min\{dis_{i,x}+dis_{i,y}\}$更新答案，然后删掉这个询问；若$(x,y)$在分治线同侧，则也用$\min\{dis_{i,x}+dis_{i,y}\}$更新一次过分治线的答案，继续分治。

例5.质数长度路径统计

$Description$
　　给一棵N个点无权树，求长度为质数的路径数目。
　　$n\leq 10^5$。
$Solution$
　　点分治。枚举子树很容易被卡成$O(n^2)$，直接算整个连通块的，减去子树内部的。
　　记$sum[x]$为该点所有子树长为$x$的路径总数，即$sum[x]=\sum cnt[x]$，则过该点长度为$k$的路径条数：$sum[x]\times sum[k-x]-\sum cnt[x]\times cnt[k-x]$。
　　这是个卷积形式，FFT优化。

例6.采药人路径问题

$Description$
　　一棵树，每个点有点权1/-1。求有多少条路径$(u,v)$，满足点权和为0，且存在一个中间点$x$，满足$x$到$u,v$的两条路径点权和为0。中间点不同则路径也算作不同。
$Solution$
　　...
　　本题可以考虑树的点分治。问题就变成求过根满足条件的路径数。路径上的休息站一定是在起点到根的路径上，或者根到终点的路径上。
　　如何判断一条从根出发的路径是否包含休息站？只要在dfs中记录下这条路径的和x，同时用个标志数组判断这条路径是否存在前缀和为x的节点。
　　这样我们枚举根节点的每个子树。用$f[i][/1]$，$g[i][0/1]$分别表示前面几个子树以及当前子树和为i的路径数目，0和1用于区分路径上是否存在前缀和为i的节点。那么当前子树的贡献就是$f[0][0]\times g[0][0]+\sum f [i][0]\times g [-i][1]+f[i][1]\times g[-i][0]+f[i][1]\times g[-i][1]$，其中i的范围$[-d,d]$，$d$为当前子树的深度。

紫荆花之恋

$Description$
　　一棵树，每个点有一个权值$R_i$，求多少点对满足$dis(u,v)<R_u+R_v$，每次加点，强制在线。
　　$n\leq 10^5$。
$Solution$
　　求有多少条路径，满足$dis[u]-R_u+dis[v]-R_v<0$。
　　建点分树。因为多次加点后复杂度可能很不对，要类似替罪羊树一样重构。

CF.1010F.Tree

$Description$
　　给一棵二叉树，求包含根节点的大小为$i$的联通块个数？对$998244353$取模。
$Solution$
　　...
　　在DFS序上DP。$f_{i,j}$表示DFS序的前i个选择j个的和。若$i+1$选，则$f_{i,j}\rightarrow f_{i+1,j+1}$；若$i+1$不选，则要跳过$i+1$这棵子树，$f_{i,j}\rightarrow f_{ed[i+1],j}$。
　　$f_v=x+1$
　　$f_v=f_1*x+1$
　　$\begin{aligned}f_v&=(((f_{a_1}x*f_{a_2}x+1)*a_3x+1)*a_4x+1)*a_5x\\&=b_1b_2b_3b_4+b_2b_3b_4+b_3b_4+b_4+1\\&=b_3b_4(b_1b_2+b_2)+(b_3b_4..)\end{aligned}$
　　$\sum_{i=1}^k\prod_{j=1}^kb_j$
　　$\log^2n$
　　树链剖分，二叉树
　　所有轻边子树size和$n\log n$，因为每个点最多属于$\log n$条轻边。

UNKNOWN

$Description$
　　M个操作，在末尾插入/删除向量，询问区间内与某个向量叉积最大的向量。
　　$n\leq 5\times10^5$。
$Solution$
　　处理过当前分治中心的询问。
　　最大的向量在凸包上，凸包具有可加性，只要求根节点...。Treap/Splay维护，每次加一个点，二分一下要删哪些点。

计算之道2016 复赛T1 百度地图实时路况

$Description$
　　定义$d(u,v,w)$为从$u$号点出发，严格不经过$v$号点，最终到达$w$号点的最短路径长度。如果不存在这样的路径，$d(u,v,w)$的值为-1。计算每个$d(u,v,w)$。
　　$n\leq300$。
$Solution$
　　暴力：$O(n^4)$，枚举删掉某个点Floyd。
　　Floyd本质是枚举中间点进行更新，与枚举顺序无关。$Solve(l,r)$表示求解$v\in[l,r]$时的情况。递归左区间时就把$[mid+1,r]$中所有点作为中间点枚举更新一遍dis，递归右区间时把dis复原，然后把$[l,mid]$中所有点作为中间点枚举更新一遍dis。$l==r$时$O(n^2)$枚举一下$u,w$就可以得到$v=l$时的答案。$O(n^3\log n)$。

例11.Package

$Description$
　　有$n$个物品，每个物品的重量是$w_i$,价值是$val_i$。每个物品只能取一个。
　　给定$Q$个询问，每个询问由两个数$(X,i)$组成。
　　$(X,i)$表示：给定最大容量为X的背包，使用除了第i件物品以外的所有物品，能够得到的最大价值之和。
　　$n\leq100,X\leq10^4,q\leq10^6$。
$Solution$
　　同上题一样的分治。

例12.CASH

$Description$
　　维护DP方程$F_i=max\{F_{i-1},a_ix_j+b_iy_j\}$。
　　$n\leq10^5$。
$Solution$
　　$f_i=\max(a_ix_j+b_iy_j)$，$(x_j,y_j)$一定在凸包上，维护凸包二分可以在线做。
　　CDQ，对于每个询问在前面区间的凸包上二分，$log^2n$。
　　对于询问按斜率排序，单调，$O(n+m)$。

二维（园丁的烦恼）

$Solution$
　　拆询问，CDQ。

例14.BZOJ4311.向量

$Description$
　　给一个长度为N的向量序列，有M个询问每次询问一个区间内和一个向量v点积最大的向量。
　　$n\leq3\times 10^5$。
$Solution$
　　...
　　把区间拆成若干个区间，取$\max$。
　　建线段树，存区间所有向量，对区间求一个凸包。对每个区间在其凸包上二分。$O(n\log^2n+q\log^2n)$。
　　建树：区间可由两个儿子归并得到，建凸包就是$O(n)$的。
　　Solve：对每个询问先按斜率排序，答案单调，$O(n+m)$。把线段树区间改成$[1,q]$？基数排序？...

例15.踩气球

$Description$
　　$n$个盒子，第$i$个盒子里有$a_i$个气球，$m$个孩子每个孩子有自己的区间，如果一个孩子自己的区间内所有气球都被踩爆了他就会很高兴。$Q$个操作，每次选一个盒子踩一个气球并询问有多少个孩子高兴。
　　$n,m,Q\leq 10^5$。
$Solution$
　　建线段树，将每个孩子的区间放到线段树上。对每个节点设$0/1$变量。
　　每个孩子相当于对节点打一个$tag$。$tag$的总个数是$O(n\log n)$的，所以均摊也是$O(n\log n)$的。

例16.离线动态图

$Description$
　　插入边删除边询问两个点连通性，可以离线，N个点M个操作。
　　$n,m\leq2\times 10^5$。
$Solution$
　　每条边存在的时间是一段区间，建一棵时间线段树。某一个时刻存在的所有边就是其到根节点路径的并。
　　按时间建线段树，对每条边维护其出现时间，即将时间在线段树上分成若干区间。询问就在线段树的某叶子节点上。
　　对整棵树DFS，当进入一个节点时，将这个点代表的这段区间中出现的边全部合并起来，离开这个点时撤销。
　　可以用不路径压缩、按秩合并的并查集维护连通性。合并时用栈记录合并前状态，合并前的父节点用x or fa[x]都行，因为合并的是集合根节点。。
　　如果秩改变也要加入栈。

林克卡特树

$Solution$
　　序列上：选$k$段不相交的区间，使其权值和最大。
　　证明答案是凸的：网络流是凸的，这题可以用网络流做：模拟费用流。所以答案是凸的，即$Ans_{i}-Ans{i-1}\geq Ans_{i+1}-Ans_i$。
　　树剖，$O(n\log^2n)$。
　　带权二分+DP。