前：day4上午——分治

衢州

T1 IOI练习

选了最高点，那么两部分都互相看不见，所以直接递归，左右两部分，相加。
不选最高点，那么在左边选了点后，会有一些被“埋”在下面了，这段区间也是独立的，递归求解。

T2 吃特色菜2

数据随机，和，数据不随机。

数据随机：每次选最小值，作为分治中心。
不过分治中心：递归。
过分治中心：向左找，向右找 第一个大于的值。

不随机：
过分治中心：
min_i, 从i到分治中心的最小值。
max_i，从i到分治中心的最大值。
区间[l,r]，min(min_l, min_r) * max(max_l, max_r);
处理min_i,max_i,max_i * min_i的前缀和，快速求出区间和。

个人理解：对于以i为中心的可以快速扫一遍，扫的过程维护前缀和，然后不以i为中心的也是从i开始扫一遍，直接根据另一边的前缀和求出。

T3 动态最大全1正方形

求一次：将正方形从中间划一条线，在这条线上求出往每个点向两边最大延伸距离，都是1。然后扫一遍就知道答案了（过中间线的最大全1正方形）。左右连边递归处理。n^2

修改：
如果在当前分治线左边，右边不递归，左边按上面处理方法处理。

T4 tourist

ZJOI 2016 day2 T2
离线询问
将网格切长边，分治线。
对分治线的每个点跑dijkstra。
询问点xy在分治线的两侧，可以直接处理。dis[i][x]+dis[i][y]。在一侧，分治下去。
$T(S) = 2T(S/2) + O(S\sqrt S logS)$
S面积
只在一边上切，$log^2S$

树分治

T5 质数长度路径统计

重心：每个子树的size 每个子树j中，cnt[j][i]长度为i的路径。
$sum[i] = \sum cnt[i]$
长度为k的路径：$sum[i] * sum[k-i] - \sum cnt[j][i] * cnt[j][k-i]$

枚举变成变成FFT。
sum,cnt自己卷自己

T6

采药人的药田是一个树状结构，每条路径上都种植着同种药材。采药人以自己对药材独到的见解，对每种药材进行了分类。大致分为两类，一种是阴性的，一种是阳性的。采药人每天都要进行采药活动。他选择的路径是很有讲究的，他认为阴阳平衡是很重要的，所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的，所以他希望他选出的路径中有一个可以作为休息站的节点（不包括起点和终点），满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。

题意：
问有多少路经满足：
1、路径的两种药材数量相等。
2、除起点和终点，有一个点满足起点到这个点，这个点到终点，也满足两种药材数量相等。

本题可以考虑树的点分治。问题就变成求过根满足条件的路径数。
路径上的休息站一定是在起点到根的路径上，或者根到终点的路径上。
如何判断一条从根出发的路径是否包含休息站？只要在dfs中记录下这条路径的和x，同时用个标志数组判断这条路径是否存在前缀和为x的节点。
这样我们枚举根节点的每个子树。用f[i][0…1]，g[i][0…1]分别表示前面几个子树以及当前子树和为i的路径数目，0和1用于区分路径上是否存在前缀和为i的节点。那么当前子树的贡献就是f[0][0] * g[0][0] + Σf [i][0] * g [-i][1] + f[i][1] * g[-i][0] + f[i][1] * g[-i][1]，其中i的范围[-d,d]，d为当前子树的深度。

当前点x，路径和为i，如果路径上存在前缀和为i的点y，那么从x到y的路径是0，就是相当于y做了休息站。

T7 紫荆花之恋

一棵树，每个点有一个权值Ri，求多少点对满足dist(u,v)< Ru+Rv，每次加点，强制在线。
N 100000.

点分治树
dis[u] + dis[v] < R[u] + R[v]
(dis[u] - R[u]) + (dis[v] - R[v]) < 0

T8 CF 1010 F

给一棵二叉树，求包含根节点的大小为i的联通块个数

n^2 dp
dfs序,f[i][j]，前i个点，选了j个。
f[i][j]
选 f[i+1][j+1]
不选f[ri+1][j] ri当前子树的结束位置。

分治FFT。

$T(n) = 2T(n/2) + O(nlogn) = nlog^2n$

链分治 + 分治FFT。
$nlog^3n$

T9 UNKOWN

操作树，询问一条路径上叉积最大的。
在凸包上，平衡树维护。

CDQ分治

T(n) = 2T(n/2)
f[i] = f[j] + 1，j< i,a[j]< a[i],h[j]< h[i]

T10 百度地图的实时路况

原题链接+思路
代码写的清晰
d(u,v,w)：从u到w，严格不经过v的路径长度，计算每个d(u,v,w)，n 300

floyed：枚举v，枚举k!=v，枚举i，枚举j，dis[i][j]=dis[i][k] + dis[k][j]
$n ^ 4$

优化：去掉一个点，重新做一遍floyed，太浪费了，对于23，除了23，其他的中间点都一样于是，于是考虑solve(l,r)为l-r的点去掉的floyed矩阵。
二分mid，solve(l,mid)，此时先用mid+1~r作为中间点更新了矩阵。然后递归下去处理solve(l,mid)，当l=r说明当前的矩阵是去掉了l这个点的矩阵，然后就统计答案。
cdq分治？

T11

T12

f[i] = max(a[i]x[j]+b[i]y[j])
x[j]y[j]在凸包上，
每次加入一个点，维护凸包，二分找到最大的点，nlogn，

离线：CDQ
每次处理左边的一块，对于右边的询问的影响，建出凸包，查询。
去log：第一个是怎么见凸包，排序，直接归并排序。
第二个：在凸包上二分，询问按斜率排序（归并排序），在凸包上的斜率是单调的，扫一遍。

对时间分治

本质CDQ分治。

T13 二维区间和

矩阵和。

线段树分治

T14

把一个区间分成多个区间，取max。
建一个线段树，对区间求一个凸包，每个询问在凸包上二分答案。
瓶颈：
建树，建凸包，排序，由儿子节点归并排序。
询问：把询问查到询问的区间里，按斜率排序，在凸包上扫一遍。基数排序。

T15

建线段树，每个线段树节点设一个变量0/1，有没有全踩爆，把每个孩子对应的区间标在区间上。每次踩爆的一个区间，然后找到对应的孩子，如果孩子的区间都踩爆了，就高兴了。

相当于消除tag的过程，tag没了->就高兴了。

对时间分治的标记，用线段树标记下来，分治下来，分治的结构就是线段树结构。

T16

线段树分治：对时间分治。
每条边存在的时间是一个区间，先建时间线段树。时间下标。dfs线段树，先左后右，存在的边加入到并茶集里，到叶子节点，那么当前叶子结点就是到了具体的一个时间（下标->时间），当前时间存在的边，就是并查集里的边。回溯上去时，把不在的边删掉，可持久化并查集。

T17 TREE

wqs二分。
二分一个v，给黑边+v，然后求MST，看有多少黑边，如果黑边个数

T24 林克卡特树

寻找k条点不相交的链，一个点可以是一条链。边权和最大。无负权。

证明是凸的，<-可以费用流。
序列：选k个区间，最大和。 模拟费用流。
1、O(nk)->背包。树上维护最长链。
2、wqs二分