分治算法浅谈与杂题选讲

分治

分治：一种经典的设计算法的思想，即将原本规模较大的问题拆解为多个相似的小规模子问题从而解决。

核心：跨越mid的时候发生了什么？

CDQ分治

陈丹琦：从《Cash》谈一类分治算法的应用

许昊然，2013年集训队论文答辩：对时间进行分治

本质：通过归并维护偏序关系，从而实现问题的离线与快速解答。

二、三、四维数点

矩形加，矩形求和

可以很容易找到一些模板题

线段树对时间分治

分治问题选讲

2020ICPC小米邀请赛决赛 B Rikka with Maximum Segment Sum

给一个长度为n的序列，求所有区间的 最大连续子段和 的和。
$n \leq 10^5$

XXI Open Cup, Grand Prix of Belarus F Border Similarity Undertakin

给一个矩形，求所有边界字符相同的子矩形的个数。
$n,m \leq 2000$

codeforces 364E
[Ynoi2016]镜中的昆虫
LOJ 534