比赛地址：http://jzoj.net/senior/#contest/home/2825
Attack
题面
考场
点开发现第一题就是一个数据结构。然后既是二维的还是一个求第 $k$ 小还是一个待修改的，那岂不是要一个四维的数据结构来弄。？
先想了想用二维线段树套树，然后发现以前连二维线段树都没写过瞬间放弃了。
然后打了个暴力。
出分：我暴力打错了挂成一个小数。//出题人手抖把时限开成了 $10s$ 让暴力能 $A$ 当然要优美一些的暴力。。
正解
其实就用暴力吧。一个优化就是不是每次询问的时候根据值排序，而是预先排好序之后去顺序选，就能保证递增了。这个可以做到严格 $O(nm)$ 但是修改可能做不到 $O(1)$ 了。
标准复杂度的东西题解上是划分树可以学学。或者是一个什么整体二分加树套树。。//有时间的话。。
$code: $
暴力：https://paste.ubuntu.com/p/trfdZHK8YY/
Bomb
题面
考场
主要写这题了。还花了几乎所有时间在一个很简单的问题上。。
先考虑三个点的曼哈顿距离是什么。可以发现就是包住他们的一个矩形的周长。而一定有一个点在定点上。（另一个点可能也在，但是没关系。。）然后记录一个横纵坐标的前后缀最大最小值就可以了。（有 $8$ 个。。）
最小值参考平面最近点对。但是正确性有问题。因为不能用前后 $6$ 个数的优化了。这个直接用答案框范围的话直接 $T$ 。然后卡时限吧。最多就能卡到 $70pt.$了。
出分：$70/100$ $WA$ 了 $30$ 的是正确性。（是有人用分治 $A$ 掉的，后面具体说。）
为了纪念这里贴一下最大值的代码：（自动忽略最小值部分就好）
$code:$ https://paste.ubuntu.com/p/PMbm6Pknm3/
正解
首先看最大值。最大值可以有正确的贪心。考虑 $8$ 个特殊点，就是八个角上的点。（类似一个正八边形）
但是我不会证。所以还是用我上面那个 $O(n)$ 的贪心做也是可以的。虽然很麻烦。
然后是最小值。有两一种方法：线段树。乱搞贪心
贪心
分别以 $x+y$ 和 $|x - y|$ 为关键字排序，取后 $10$ 个来查找。但是会被一个算法卡掉：网格图。一个转了 $45^{\circ} $ 的正方形。
怎么办呢。可以以 $x$ 为第一关键字，$y$ 为第二关键字排一遍做一遍就可以了。
但其实还是只有 $95pt.$ 因为出题人可能真的故意卡了。可能就只能拿到这么多分了吧。先面向数据过了它再说。
其实有一种万全的策略：以这个点为中心的一个转了 $45^{\circ} $ 的正方形。但是查出来它可能复杂度高了。
$code: $ https://paste.ubuntu.com/p/tqbRYFPjHV/
线段树
这个是正解了。
题解里面的就是。和第一题一样有时间打吧。
优秀的分治
这里其实就是我考场上的类似做法。但是更优秀。
首先我们拿出来保证 $|p[i].x-p[mid].x|<ans$ 的所有 $i$ 然后考虑怎么优化一个顺序能够更快速的求值？
因为一个点还有 $y$ 的一维，所以就可以给 $y$ 排个序，然后每一次保证选的点的 $y$ 值在 $[p[i].y - ans, p[i].y]$ 里面就好了，其中 $p[i].y$ 是最右边的那个点。
就可以 $A$ 了！
$code: $ https://paste.ubuntu.com/p/sMfKgftmdd/
Contra
题面
考场
想了想这个 $p$ 可以二分答案啊。然后概率 $dp$？然后想了一会没想出方程来，就放弃掉了。
主要原因其实是第二题看起来很可做就去肝它了
出分：没提交。
正解
$aaa…$就是二分答案。没事，然后就是一个普通的 $dp$ 吧。这里首先想到的是可以用期望直接 $dp$ 的。但是可以发现他求的是一个分数和，这个就可以不用做一个部分的期望了，就可以直接把每一步的累加到最后的答案里面。具体就是：
$\Large dp_{i + 1, j + 1, k + 1} += p \times dp_{i, j, k}$
$\Large dp_{i + 1, j - 1, 0}+=(1 - p) \times dp_{i, j, k}$
$\Large Ans += dp_{i, j, k} \times p \times (j + 1)$
然后我调了近乎3，4个小时没跳出来。$orz…$我不调了我直接上矩乘。。
这个东西就是一个直接从第 $i$ 层转移到第 $i + 1$ 层的方程了，考虑建一个转移矩阵。
先把状态压起来压成一列（$Q \times R+1$，最后一列存答案）。
然后考虑转移方程。这个肯定就是一个 $(Q \times R+1) \times (Q \times R+1)$ 的矩阵了。这个玩意里面就是上面的方程，然后就是在 $dp_{i, j, k}$ 的地方换成 $1$ 就好了。因为是要矩乘的。就可以直接快速幂了。 然后其实初始状态所在的那一行的答案了。(整个矩阵 $Matrix_{S1, S2}$ 的意思就是从 状态 $S1$ 转移乘出来的多少步之后到达 $S2$的概率，然后最后一行也就是期望) 就差不多了。
这里需要注意以下几个细节点：
- 初始化的时候在注意 $Matrix_{i,i}=1.$ 因为这个状态转化成自己本身的概率就是 $1.$
- 最开始的初始矩阵需要注意 $Matrix_{cnt, cnt} = 1.$ 因为所有的答案是要累加在一起的，所以 $cnt$ 的地方应该每次继承。
- 时间优化：
- 忽略到一些不存在的答案的转移。比如 $Matrix_{i, j} = 0$ 的时候就不要去算了。
- 考虑 $ikj$ 优化，就是先枚举 $i$ 再 $k$ 再 $j$ 这样可以顺便把 $a_{i, k}=0$ 的时候过滤掉（上面那个）可以拿掉一层循环的复杂度。
- 精度问题。必须开到 $1e-11$ 才能过所有点。实际上可以卡时限开满。
然后就终于可以 $A$ 了。