Day2上午

一、基本分治

例题一、归并排序

如题…基础排序之一。

二、树分治

①点分治

原则上要尽量减小递归层，而考虑删去当前某节点之后，剩余节点数量最多的联通块尽量少，此时递归层数一定是最小的。这个节点就是“重心”。
重心可以$O(n)$DP求得

例题一、IOI2011 Race

给定一颗$n$个点的带边权的树，求一条路径使得权值和为$K$且边数量最少。
$1\le n \le10^5,K\le10^6$

思路

点分治，记录到根路径长为dist[i]的最小边数即可

②边分治

选择一条边删去，得到两颗不相交的子树，统计这条边的信息。
选边方法与点分治的选点几乎一致。

一个优化

我们发现菊花图可以轻松卡掉边分，于是我们考虑重构这颗树，使得度数最大的点度数最小，采用的策略是加虚点（个人喜欢左孩子右兄弟）关键是两点间路径经过的实边不能变。

例题二、bzoj2870

题面见bzoj2870

思路

采用边分治。考虑删去一条边以后这条边的两端$a,b$，考虑将a端子树和b端子树中的链按点权最小值排序，对a端来说，每条链选b端中点权最小值不小于这条链且最长的链，b端同理，如此就可以做出这道题。

③链分治（树链剖分）

略（太过于模板）

三、CDQ分治

普通分治：将区间分成两部分递归求解后合并。
CDQ分治：在普通分治基础上需要加上左半区间对右半区间对贡献得到答案

例题一、二维偏序

（上一篇好像有一样的题）

思路

首先进行双关键字排序
根据CDQ分治，不断递归至区间长度为1
关键在于计算贡献
考虑到子区间贡已经求出，我们将两个区间按第二维进行排序，如果左区间的一个有序对$(u,v)$对右区间的一个有序对$(a,b)$产生贡献，那么就等价于$v<b$，双指针扫一遍即可。
又考虑到我们按b排序，显然用归并复杂度比较优秀。

四、整体二分

整体二分需要满足五个性质：
①询问的答案具有可二分性（单调性）
②修改对询问是独立互不影响的。
③不同的修改贡献可叠加，不用重复计算
④贡献满足交换律、结合律，有可加性
⑤题目允许离线
实现起来就是将所有询问一起二分

例题一、Meteors

题面见SP10264

二分答案，线段树模拟当前区间的修改

五、三分

用于求解凸函数（单峰函数）

六、分块

整块整体做，边角暴力做

七、莫队

将询问离线排序，优化暴力过程。

八、树上莫队

借助欧拉序（括号序）将树上问题转换成区间问题，其余与莫队大致相同。

九、块状链表

略

Day2下午

今天下午是考试，结果…
T1文件名写错，T2感觉没问题莫名wa掉，T3空间开小——
完美爆0（解决上述问题后拿到60分暴力分）
然后发现T2逆序对求错。。。
总之以后细心更重要。
题目暂时就不贴了。。。打完再来发