The 2022 ICPC Asia Nanjing Regional Contest

先求出没有洞的话，最终留下来的袋鼠是哪个矩形。再看洞相对袋鼠是怎么移动的，这个洞会留下来一个移动轨迹。check 一个点是不是答案，就是看这个移动轨迹和袋鼠矩形的交的大小。那么每次是对移动轨迹进行一个二维数点。移动轨迹坐标必须在 \([-n,n]\) 和 \([-m,m]\) 之间，要不然最终一只袋鼠都不剩可以直接特判掉。所以二维前缀和即可。

求出 \(f_i\) 和 \(g_i\) 分别代表考虑 \(i\) 作为断电的前缀 / 后缀，并且选了 \(i\)，最小代价是多少。

答案可以用一个前缀和一个后缀拼起来，那就分为两种：选了 \(p\) 和不选 \(p\) 的。对于 \([p-k,p-1]\) 和 \([p+1,p+k]\) 这两个区间：

• 选了 \(p\)：左边 \(f_{\min}\) 和右边 \(g_{\min}\) 再加 \(v\)；
• 没选 \(p\)：左侧 \(i\) 和右侧 \(j\)，并且 \(j-i\leq k\)，求 \(\min\{f_i+g_j\}\)．

前者直接扫一遍，后者搞个单调栈就行。

二分答案，\(\geq mid\) 的设成 1，\(<mid\) 的设成 0．那么第 \(k\) 大 \(\geq mid\) 当且仅当可以让 \(1\) 的个数 \(\geq k\)．每个数作为 1 的一定是一段区间，这样就能 \(\mathcal{O}(n)\) check 了。

暴力是 \(f_{x,i}\) 为 \(x\) 子树内距离 \(x\) 为 \(i\) 的点全部变黑的代价是啥。\(f_x\) 首先是所有儿子的 \(f\) 加起来，位移一位，前面添个 \(a_0\)，然后再对应位置和 \(a_i\) 取 \(\min\)．

上个长剖，每个位置再记录一个 tag，表示这个东西上次 chkmin 是对 \(a[?]\) chkmin 的就行。

这里这样做是因为长链往前添的时候，后面的不能动。但是这个 chkmin 并不急着求出来，当短链往长链上合并的时候再把短链上延迟的那些给更新掉就行。

由于要对 \(a\) 求区间 \(\min\)，所以需要上 ST 表，复杂度是 \(\mathcal{O}(n\log n)\)．

贪心，发现尽可能选 2 更优。那就能选 2 就选 2，选不了 2 再选 1．如果有一次强制 2 操作不了了，就把之前的一次选 2 反悔成选 1．

看看 \(n^2\) dp：

然后 slope trick，考虑差分数组的变化相当于整体加等差数列，或者把俩差分数组给归并起来。平衡树维护一下，支持打等差数列加的 tag，以及启发式合并。

启发式合并的时候 finger search（splay 自带）复杂度是 \(\mathcal{O}(n\log n)\)．

连边是咋连的？同一条斜率为 1（或 -1） 的直线上的点互相连边。对每个斜率为 1（或 -1） 的直线建个点，对于平面上每个点再把它所在的两个直线对应的点给连起来。

那么原先的完美匹配就是说要找到一个完美的边边匹配方案。这个就是经典问题，如果有连通分量里面如果是奇数条边就无解了，否则随便拉出来一个生成树，在上面自底向上贪心匹配即可。

合法的一定是 NaN 的左右子树都是堆结构，然后 NaN 的子树补是个堆结构。

先考虑计数，\(f_{n,k}\) 表示大小为 \(n\) 的完全二叉树，子树中有个大小为 \(k\) 的 NaN 子树，概率是多少。

注意到本质不同的 \(n,k\) 只有 \(\mathcal{O}(\log n)\) 种，所以记忆化搜索一下就是对的。

学习一下 ymh 老师的写法！\(k\) 之间没啥关系，所以在外面枚举 \(k\)，这样代码能简便很多。

咋都判得比我简洁。