Problems：https://codeforces.com/contest/1651
D. Nearest Excluded Points
题目
给定平面上$n$个点，第i个点坐标为整数$(x_i, y_i)$。定义两个点之间的距离为 $|x1-x2|+|y1-y2|$，也就是曼哈顿距离。
对这n个点中的每个点，输出一个距离它最近的整数坐标点$P_i$，并且$P_i$不能在输入的$n$个点里。
$1\le n\le 2\times10^5$，$1\le x_i,y_i\le10^9$
题解
发现很难直接求。但我们可以发现，“可能成为答案的点”一定是紧挨着某个输入的点！一共$4\times n$个可能成为答案的点，将它们全都放到队列中开始BFS。BFS过程中只能走输入的点，同时记录答案即可。时间复杂度O($n$)。
另一种做法
考场上写了一种智障解法，但感觉也是值得一提的。
首先考虑曼哈顿距离最近的点，距离一定不超过$\sqrt n$。因为最坏情况就是$n$个点聚成一坨，成为一个边长为$\sqrt n$的正方形。
对于每个点，如果我们能确定答案距离是多少，那么就可以在O($\sqrt n$)点时间里找到这个答案。因为距离每个点距离为$d$的点总共有O($d$)个，依次枚举判断即可。
同时，曼哈顿距离与切比雪夫距离是可以相互转换的。将$(x,y)$转化为$(x-y,x+y)$，两个点的曼哈顿距离等于新坐标下的切比雪夫距离 $\max(|x1-x2|, |y1-y2|)$。那么距离点$P$距离不超过$d$的点，都在以点$P$为中心，边长为$2\times d+1$的正方形中。
先转化为切比雪夫距离，对每个点，二分这个$d$，用树套树求这个正方形内点的个数（或者用可持久化线段树，少一个log）。找到$d$之后，O($\sqrt n$)求答案点。
如果用可持久化线段树的话，总时间复杂度 O($n\sqrt n+n\log^2n$)，应该也可以过。但考场上没时间了，就写了个O($n\sqrt n\log n$)的，超时。
E. Sum of Matchings
题意
给定一个二分图。左边是节点1到n，右边是节点n+1到2n。并且，每个节点的度数都为2。不会有重边。
定义 $G(l,r,L,R)$ 表示左边选$l$到$r$，右边选$L$到$R$，这些点选出来形成的子图。对于所有的子图 $1\le l\le r\le n$，$n+1\le L\le R\le 2n$，求它们的最大匹配之和。
$n \le 1500$。
题解
因为每个点的度数都为2，整个图就是由一个个环组成的。
考虑每一条路径，统计它在多少个 $G(l,r,L,R)$ 中出现过即可。
如何统计？需要这条路径在子图中没有延伸出去，只需要两端点之外的两个点不在区间范围内即可。乘一乘就可以了。
时间复杂度O($n^2$)，为枚举所有路径的复杂度。
F. Tower Defense
题意
不想翻译了 https://codeforces.com/contest/1651/problem/F
题解
首先，塔的位置其实可以认为都在0点（但顺序仍要保持）。因为对于第$i$个塔，第$j$个怪会在$t_j+i$秒到达它，下一个怪会在$t_{j+1}+i$秒到达，相当于它在0点。
如果某个怪$j$打穿了所有塔，那么相当于所有塔从$t_j$时刻从0开始恢复。
如果某个怪$j$没有打穿所有塔，在第$k$个塔停下来了，那么第1到$k-1$个会从$t_j$时刻从0开始恢复。第$k$个塔会剩一些血，然后$k+1$到$n$还是按之前的恢复进度。
相当于一个怪，最多会将塔变的多两段。对于每一段，如果我们能用某种数据结构维护，那么就解决问题了。
残血的塔每次最多1个，暴力维护即可。我们需要考虑的是，对于从$from$到$to$这一段连续的塔，都从$t$时刻开始从0恢复，如何维护。最开始所有塔都满血，也可以认为所有塔是从-inf时刻开始从0恢复。
如何维护呢？我们注意到，一段塔能打掉的血，取决于当前时间$now$与$t$之间的差值，记为$dt$。如果$dt\ge c_i/r_i$，记录这些塔的$c_i$之和即可，否则记录塔的$r_i$之和，乘以$dt$即可。
可以用线段树套平衡树维护。线段树维护1到n（用来请求$from$到$to$），每个节点上的平衡树（也可以线段树）按$c_i/r_i$作为key，维护$\sum c_i$和$\sum r_i$。当然考虑一下可以发现，我们没有插入删除塔的操作，所以可以按$c_i/r_i$排序，用可持久化线段树维护。对每个$dt$二分查找root。
如果怪不能通过某一段塔，直接在线段树上二分查找$k$。总时间复杂度O($n\log n$)。