似乎大家反映觉得是 UOJ Extremely Hard Round? 其实出题的时候是觉得没有 UR 难所以叫 UER，不过得分分布好像打出了 UR 风范（

打雪仗

出题人 matthew99, whzzt, vfleaking

数据和题解 whzzt

咦为什么有三个出题人呢？其实是 myy 在群里扔了个 idea 我们觉得太简单了就稍微改了改，vfk为了方便选手通信又改了改，就变成现在这样了。看起来大家做这题还是很开心的。

算法零

提交样例程序，似乎通过了第一个测试点。

期望得分 $0$ 分。

算法一

咦我们有很多雪球！那我们直接让小 $A$ 把整个串 $S$ 传给小 $B$ 就好啦！

通信次数 $2n$，期望得分 $20$ 分。

算法二

小 $A$ 和小 $B$ 商量了一下，小 $B$ 倾向于算法一——自己连雪球都不用扔。小 $A$ 不服：你闲着也是闲着，不如给我点有用的信息？

小 $B$ 想了想觉得小 $A$ 没必要在那些混淆视听的位置上浪费雪球，于是他告诉小 $A$：“你扔第 $i$ 个雪球给我时，我告诉你下一次是扔第 $i+1$ 个雪球还是第 $i+2$ 个雪球！”小 $A$ 一想觉得有理：你和我扔一样多的雪球，随后还要和小 $C$ 大战，这账怎么算都是赚了。于是小 $A$ 也爽快地同意了。

这样做要通信多少次呢？

咦我们发现这个方案非常优！容易发现，如果最后不被选择的段中有 $a$ 个长度为奇数的段，我们花费的通信次数就是 $\frac{3n-a}{2}$。

不幸的是，小 $C$ 可能恰好选择了 $n+1$ 至 $2n$ 这 $n$ 个下标，这时我们就得花 $\frac{3}{2}n$ 轮通信才能解决问题了。

算法三

小 $A$ 和小 $B$ 很快感受到了被小 $C$ 支配的恐惧，为了摆脱这样的恐惧，小 $A$ 和小 $B$ 决定先约定好一个随机种子，然后将整个序列按照这个随机种子随机打乱！这样小 $C$ 的编号顺序就不会影响到我们的通信次数了。

这时的期望通信次数是 $\frac{4n}{3}$ 的，因为奇数段差不多有 $\frac{n}{3}$ 个。实现时我们可以让 $B$ 找到一个合适的随机种子传给 $A$，由于不会严谨证明这个方法并没有作为 std 。期望得分 $100$ 分。

算法四

from vfleaking

考虑将原本的01串等分成三份长度约为 $\frac{2}{3}n$ 的段，那么必然有一段中对小 $B$ 有用的元素不少于一半。我们让小 $B$ 告诉小 $A$ 在另两段中自己需要知道的位置，小 $A$ 将这一段整段和其他段中小 $B$ 需要的元素扔给 $B$ 就可以了！

显然这样做小 $A$ 和小 $B$ 都不会传递超过 $\frac{4}{3}n$ 位的信息，期望得分 100 分。

算法五

from vfleaking, WuHongxun

不妨考虑只进行一次通信，若小 $B$ 给小 $A$ 发送了 $x$ 个 bit，那么必定有 $(\genfrac{}{}{0ex}{}{2n}{n})2^{-x}$ 个下标集合是无法被区分的，于是小 $A$ 只能将这些下标集合的并集发给小 $B$ ，我们不允许消耗超过 $x$ 个 bit，不妨设 $x=\alpha n$ ，于是有

$$(\genfrac{}{}{0ex}{}{\alpha n}{n})2^{\alpha n}\ge (\genfrac{}{}{0ex}{}{2n}{n})$$

即有

$$\alpha \ln \alpha -(\alpha -1)\ln (\alpha -1)+\alpha \ln 2\ge 2\ln 2+o(1)$$

我们发现满足条件的最小 $\alpha =1.20559733891046+o(1)$ ，于是我们得到在只有一次传输时确定性算法的下界。

我们有一个概率算法可以达到这个界：考虑随机选择这样的 $2^{\alpha n}$ 个大小为 $\alpha n$ 的集合，小 $B$ 将包含当前下标集合的最小集合发给小 $A$ ，那么我们有极高的概率能够使得小 $B$ 得到想要的答案。

不过在本题中由于时间复杂度太高，无法实现。

雪灾与外卖

出题人 laofu

数据 whzzt

题解 laofu

算法一

爆搜，没啥好说的。

算法二

这是一个二分图匹配的模型。

可以发现一个显然的性质，餐馆和送餐员的匹配是不会相交的，即对于任意 $1\le a_1<a_2\le n$,$1\le b_1<b_2\le m$ 我们有 $$|x_{a_1}-y_{b_1}|+|x_{a_2}-y_{b_2}|\le |x_{a_1}-y_{b_2}|+|x_{a_2}-y_{b_1}|$$

这样就给我们提供了一个DP的顺序。

用$f_{i,j}$表示把标号$1\dots i$的送餐员匹配标号$1\dots j$的餐馆的最小总代价。转移时枚举第$j$个餐馆匹配了几名送餐员，则转移式为：$f_{i,j}=\underset{k=0}{\overset{min(c_j,i)}{min}}{f}_{i-k,j-1}+w_j\times k+\sum _{t=1}^k|x_{i+1-t}-y_j|$。复杂度$O(n^{2}m)$。

算法三

使用单调队列优化上述DP即可在$O(nm)$内完成。

算法四

保证了餐馆的总容量，且 $w_i=0$ ，我们可以看成若干个容量为$1$的餐馆。

把餐馆和送餐员放在一起按照坐标排序，从前往后考虑，当考虑到一名送餐员$i$时，我们先让它与前面的一个空的餐馆$j$匹配。费用为$x_i-y_j$，那么我们就是要找一个最小的$-y_j$。(如果没有空的餐馆我们可以视为在$-\mathrm{\infty }$处有无穷个餐馆)。

匹配完之后，我们可能进行调整，把这名送餐员改为匹配后面的餐馆。那么我们就可以撤销这次操作，然后把这名送餐员当做没有使用过，那么往堆中丢入$-(x_i-y_j)-x_i$，即减去之前这组匹配的贡献，然后寻找新匹配。 扫到餐馆时也类似，先可以匹配一名送餐员，然后可以撤销这组匹配，寻找新匹配。

对所有餐馆和送餐员分别建一个堆来维护这个操作。复杂度$O((n+\sum c_i)\log (n+\sum c_i))$ 。

算法五

咋一看，是不是直接套之前的模型就好了呢？然而有一个问题：如果送餐员$a$匹配了餐馆$b(x_a<y_b)$，

那么，接下来$a$可能反悔去匹配餐馆$c(x_a<y_c)$，$b$也可能反悔去匹配送餐员$d(y_b<x_d)$。

比如，如果送餐员在坐标$1$处，两个餐馆在坐标$2,3$处，$w$分别为$100,0$，则，扫到第一个餐馆时，会把送餐员和第一个餐馆进行匹配。之后扫到第二个餐馆时，会把之前的匹配给撤销，增加一组送餐员和第二个餐馆的匹配。

所以我们既要能够支持$a$的反悔，也要能够支持$b$的反悔。那么每进行一组匹配时，要往两个堆中分别添加反悔的操作。

复杂度仍然是$O((n+\sum c_i)\log (n+\sum c_i))$

算法六

当餐馆的总容量无限制时，不能再把每个餐馆拆成一个一个单位容量的了。

考虑这样一个简化版的问题：

1.每名送餐员只能匹配在它左边的餐馆。我们求出最佳匹配的餐馆集合$S$。

2.每名送餐员只能匹配在它右边的餐馆。我们求出最佳匹配的餐馆集合$T$。

然后有一个结论：当 $w_i=0$ 时，原问题的最优解$U$满足$U\subseteq S\cup T$

证明：我们对于数轴上任意一条边$e$，令匹配$T$下从左向右经过这条边的送餐员数量减去从右到左经过这条边的送餐员数量为$f(T,e)$，匹配$U$下从左向右经过这条边的送餐员数量减去从右到左经过这条边的送餐员数量为$f(U,e)$。则$f(U,e)\le f(T,e)$。（如果$f(U,e)>f(T,e)$对于子问题$2$而言，送餐员只能往右走，所以$f(T,e)$可以调整到$f(U,e)$，$U$是无限制的，那么$f(U,e)$也可以调整到$f(T,e)$，那么显然两种方案可以都变成代价小的方案）。那么，对于一个餐馆而言，从$S$到$U$，左边匹配它的送餐员不会变多，从$T$到$U$，右边匹配它的送餐员也不会变多，所以上述结论成立。

而$|S\cup T|\le 2n$，套用算法四解决即可。

算法七

我们试想，能不能继续沿用subtask6的那个贪心，从而把问题从subtask7转化为subtask5呢？

然而有这样一个反例：两名送餐员中间夹着两个餐馆，其中一个餐馆$w$很小，容量为$1$，另一个$w$很大。在subtask6的两个子问题中，$S\cup T$都只会包含那一个$w$小的餐馆。这样我们转化之后就从有解变成了无解。

为什么呢？因为我们在subtask6中证明的时候，在子问题$2$中，对于任意一个餐馆$i$（这里是把餐馆和送餐员按坐标排序放在一起考虑）如果$g(T,i-1\to i)\ge c_i$，则$S\cup T$会包含第$i$个云的所有容量，否则这$g(T,i-1\to i)$名送餐员肯定都会匹配餐馆$i$。而现在不一定了，因为餐馆带了权，可能左边的送餐员会选择在$i$右边的权值更小的餐馆。

不过我们可以加一点小技巧：

1.在子任务六的子问题$1$的基础上，把已经匹配的那些餐馆$S$的容量给扣除，然后求一遍子问题$2$的解$S^{\prime }$。

2.在子任务六的子问题$2$的基础上，把已经匹配的那些餐馆$T$的容量给扣除，然后求一遍子问题$1$的解$T^{\prime }$。

猜想：原问题的最优解$U\subseteq S\cup S^{\prime }\cup T\cup T^{\prime }$

关于该猜想，我们并没能给出证明或反例(基于对拍认为该猜想有较大概率正确)。如果能在WC之前证明做法的正确性或者举出反例的同学可以在WC中获得出题人提供的小礼品一份。

算法八

考虑算法五的过程。在过程中我们维护了两个堆，一个维护待匹配的送餐员，一个维护待匹配的餐馆。之前复杂度不对的原因是送餐员堆的复杂度没有保证，因为一个餐馆匹配了一名送餐员之后，这名送餐员可能反悔，所以这名送餐员又会重新丢入送餐员堆中。

但是注意到，对于送餐员 $x,y$ 和餐馆 $a,b$ 来说，若 $x<y<a<b$ ，那么当送餐员x和送餐员y现在匹配了餐馆$a$时，题它们两个往堆中丢的元素都是$-x_a-w_a$，因为$match(y,b)-match(y,a)=match(x,b)-match(x,a)$，也就是说每次餐馆匹配了若干名送餐员之后，往送餐员堆中丢的东西都是等权的。因此我们只要丢一次就好了，这样复杂度就是正确的了，时间复杂度为 $O(n\log n)$。

插播小广告：欢迎大家来听WC2019清新小课堂：模拟费用流问题。

许愿树和圣诞树

出题人、数据和题解 zx2003

算法一

直接模拟题意，每次有操作三的时候暴力dfs整棵树。

时间复杂度为$O(n^2)$，可以通过第一个数据集。

算法二

每次有操作三的重新dfs获得先序遍历太暴力了，考虑一些简单的优化。

我们在修改操作的时候顺便维护一下子树大小，然后每次操作三时就在树上二分。

这样单次复杂度就是$O(\mathrm{深}\mathrm{度})$。

当数据随机时平均复杂度为$O(n\log n)$，可以通过前两个数据集。

算法三

让我们思考一下，对于一棵二叉搜索树，在中序遍历已知的时候，我们还知道哪些信息，就可以唯一地确定它的形态呢？

根据操作三的提示，我们容易想到直接维护树的先序遍历。

通过简单的观察，我们可以发现，当一个点$x$单旋到根的时候，所有权值比它小的点都在它的左子树，权值比它大的点都在右子树。

并且对于任意两个小于$x$的点，它们的在先序遍历里的相对位置保持不变。

根据这个性质，我们可以定义“段”为权值为区间$[l,r]$的节点，按照原树中先序遍历的相对顺序，所构成的新树。

对于子任务三，我们考虑对时间分块，每过一段时间就暴力重构整棵树的先序遍历。

然后我们暴力维护“段”构成的树结构即可。

复杂度$O(n\sqrt{n})$

这个做法可拓展性有点差。

如果一定要拓展，那么就要用到后面的性质，然后效果相当于给后面的做法强行套上对时间分块。

算法四

让我们再思考一下，对于二叉搜索树，还有哪些信息可以用来辅助确定它的形态呢？

我们联想到了treap，或者说笛卡尔树。

我们可以给每一个节点赋一个键值，这样，上旋操作就等价于将键值调大至一个合适的值。

对于子任务三，由于每次都是上旋为根节点的儿子，所以每次可以轻易计算键值应该调为多少。

最后求遍序列的笛卡尔树即可。

时间复杂度为$O(n)$，可以通过子任务三。

算法五

让我们思考一下一个点在笛卡尔树里的父亲是什么。

或者更一般化，一个点在笛卡尔树里的祖先是什么。

冷静分析一下，可以证明，一个点在笛卡尔树里的祖先就是这个位置对应的前缀单调栈和后缀单调缀。

然后，对于子任务四，我们只要使用线段树简单维护每个点每个时刻的键值。

然后每次查询一个点的父亲时，就找出在序列中该点的前面第一个和后面第一个键值比它大的点，取键值较小者即可。

时间复杂度为$O(n\log n)$。

算法六

首先，由于每次不一定单旋到根，所以我们需要一个动态标号法，具体可以参考2013年陈立杰的集训队论文。

当然，由于本题不强在，所以我们可以离线后用个链表来维护。

然后对于前后缀单调栈的维护，这是个经典问题。

具体方法是对于线段树的某个节点，update的时候，用右儿子的最大值在左儿子的子树里二分，以计算左儿子的单调栈有多少被弹掉了。

这样就可以维护前后缀单调栈的长度。

至于询问第$k$级祖先，我们可以二分答案后再在前后缀的单调栈上查询。

直接写时$O(n{\log }^{3}n)$的，实际上可以用点小技巧优化到$O(n{\log }^{2}n)$的。

这样就可以通过子任务五了。

算法七

借助外界信息来维护树形态都不够优美。

实际上树的形态是可以直接维护的。

观察到如果是连续的三点共线的单旋，树的形态改变是很小的，直接把旋转的点提根即可。(HNOI2017单旋)

继续观察，发现一个点上旋的时候，树的形态变化大概是把这个点到根的左链和右链分别合并后作为点$x$的左右儿子。

并且，((这个点，该点的父亲，该点的祖先)三点不共线)的单旋次数是很少的。

可以证明是均摊$O(\log n)$。

证明思路是，在splay的复杂度证明里，每次如果((这个点，该点的父亲，该点的祖先)三点共线)，那么把单旋代价(1+势能变化)中的1给扔掉。

现在问题就变成了，如何$O(\mathrm{拐}\mathrm{点}\mathrm{次}\mathrm{数}\ast poly(\log n))$来维护。

考虑直接用LCT维护整棵树，上旋x->y的时候，就提取出$x$到$y$的路径。

然后通过在splay上二分来将x到y的路径分割成若干个权值单调的连续段。

将这些连续段分别拆开来后，按照一定顺序合并起来即可。

询问的时候在上LCT简单二分就行了。

复杂度直接算是$O(n{\log }^{2}n)$的。 但实验表明更像是$O(n\log n)$，可能可以通过一些高超的技巧来分析吧。