鸽子固定器

from AprilGrimoire， 题解 by AprilGrimoire

这次的题目顺序真是十分抱歉QwQ A题可能是三道题中AC人数最少的了……

然而这题std才50行，放B和C显得不太合适哇QwQ

子任务一

$n$的范围只有$10$，所以随便怎么暴力都可以哇QwQ

时间复杂度：$\mathrm{\Omega }(poly(n))$

期望得分：$5$

子任务二

容易发现，如果我们确定了选择的固定器大小的范围，那么一定会选择这些固定器中牢固度最大的至多$m$个。所以我们可以把固定器按大小排序，枚举选择的右端点，然后将左端点向左扫一遍。在扫的过程中，用一个小根堆来维护选择的固定器的牢固度。

时间复杂度：$O(n^{2}logm)$

期望得分：$10$

子任务三

当$d_s=d_v=1$的时候，首先把鸽子固定器按照大小排序。设$f_{i,j}$表示在前$i$个固定器中选择$j$个，且必须选择第$j$个的价值的最大值。则 $$f_{i,1}=v_i$$ $$\begin{gathered} f_{i,j}=\underset{1\le k<j}{max}{f}_{k,j-1}-(s_i-s_k)+v_i \\ =v_i-s_i+\underset{1\le k<j}{max}{f}_{k,j-1}+s_k \end{gathered}$$ 只要记录前缀最大值进行DP，就可以在$O(nm)$的时间内解决子任务三。

时间复杂度：$O(nm)$

期望得分：$10$

结合子任务二的做法可以获得$20$分。

子任务四

考虑子任务二的一个优化：在扫描过程中，如果发现右端点被出堆了就终止扫描。这样做显然是对的，因为右端点被出堆后的方案可以通过简单地左移右端点来使答案变优，一定不是最优值。然而，对于构造的数据，这个优化可能并没有什么用：

200000 50 2 2
1 1
2 2
3 3
...

对于这样的数据，这个优化并没有什么用。然而对于随机数据，它还是跑得挺快的。让我们进行一波有理有据的分析：对于第$i$大的固定器，随机找另一个固定器，有大约$\frac{i}{n}$的概率找到一个比它大的固定器。也就是说，期望扫描$\frac{n\ast m}{i}$个固定器，它就会被出堆。对于所有固定器，扫描所需要的总期望时间是 $$\sum _{i=1}^n\frac{n\ast m}{i}=O(nm\log n)$$

时间复杂度：$O(nm\log n)$

期望得分：$25$

结合前三个子任务的做法可以获得$45$分。

子任务五

假设以$i$为右端点向左扫描时，$j$号点始终没有被入堆，那么以$i+1$为右端点时，它肯定也不会被入堆。这启示我们大胆猜想：对于右端点来说，左端点有决策单调性！取区间上前m大的点可以用主席树在$O(\log n)$的时间内完成，再算上决策单调性二分的$O(\log n)$，我们就可以在$O(n{\log }^{2}n)$的时间内解决

.

.

.

$d_v\ne 2$的情况。为什么当$d_v=2$时没有决策单调性呢？考虑这样的数据：

200000 50 2 2
1 5000
2 1
3 1
...
199999 1
200000 10000000

对于中间的大部分点，最优决策都是选连续的$m$个固定器。而对于最后一个点，最优策略是选择最后一个点，第一个点和中间任意48个点。非线性的东西往往能够破坏决策单调性。

这个做法实际上可以通过前五个子任务，因为小数据不太好卡，对于随机数据正确性又很高。

实际上冷静一下就能发现决策单调性是假的：如果复杂度和$m$无关，为啥$m$这么小呢？

时间复杂度：$O(n{\log }^{2}n)$

期望得分：$70$

子任务六

考虑优化子任务四的做法。这个做法会被价值递增的数据给卡掉。那么，如果我们二分ST表来找下一个会被入堆的点呢？事实上，这个算法是能通过全部数据的。

证明：假设在以$i$为右端点向左扫描时$j$被入堆了，就记录有序对$(j,i)$。我们把有序对$(a,b)$分成两类：$v_b\ge v_a$的叫做第一类有序对，$v_b<v_a$的叫做第二类有序对。 1. 对于第一类有序对$(a,b)$，一个$b$最多对应$m$个$a$。（否则$b$会被出堆） 2. 对于第二类有序对$(a,b)$，一个$a$最多对应$m$个$b$。（否则在扫描到$a$的时候，堆里至少有$m$个比$a$大的数，也就是说，$a$不会被入堆）

入堆操作最多会被执行$O(nm)$次，每次需要$\log n$的时间来二分ST表和$\log m$的时间来入堆，因此，这个做法能够在$nm\log n$的时间内通过所有子任务。

时间复杂度：$O(nm\log n)$

期望得分：$100$

神奇的做法

在比赛时，发现了这样一种神奇的做法： 按照坚固度从小到大考虑所有固定器。 1. 如果当前固定器被选中了，那么选中的固定器集合一定是一个区间。（否则可以把当前固定器换掉来获得更优的答案。） 2. 如果当前固定器没被选中，我们可以把它删掉。

用链表维护剩下的固定器。包含当前最小固定器的区间最多只有$m$个，所以这个算法的复杂度是$O(nm)$的。

子任务六的两个优化

1. 用链表维护当前可能被入堆的点集。如果在从右往左扫的过程中一个点没有被入堆，那么我们可以把它从点集里删掉，因为它以后也永远不会入堆。这样就能避免二分ST表，只有$O(nm\log m)$的复杂度。（$\log m$是因为需要用堆维护当前被选的固定器。）
2. 堆也不是必要的，因为每次可能入堆的点只会增加一个，所以可以线性维护当前被选中的点集。这样就能做到$O(nm)$。

To Do Tree

对于大多数OIer来说，这题应该是个大胆猜结论题。

算法零：构造

看过题的同学就知道，subtask3就是送分的，每星期只能肝一个ddl，搞什么都行嘛……只要输出格式没有问题，大家应该都能得到这$6$分。

算法一：搜索

直接枚举每星期肝的ddl集合搜索，期望得分$30$，可以通过subtask1。

结合算法零可以得到$36$分。

算法二：子集dp

设$d{p}_S$表示肝掉集合$S$中的所有ddl所需要的最少的时间，然后枚举下一次肝的集合转移即可。

时间复杂度$O(3^n)$，期望得分$60$分，可以通过subtask1，subtask2。

结合算法零可以得到$66$分。

算法三：构造

这个题看起来不可做又看起来很可做，有哪些选手能证明一下自己的算法是最优的呢？

先说出题人Mike给出的一种构造算法和证明。

首先对把依赖关系翻转一下，对于任意一个任务$i$，执行$i$之前必须先完成$i$的所有子节点。这个问题的最优解把执行顺序反转一下就是原问题的最优解了。

直接说结论：每次选择最深的叶节点执行，若有多个则随意执行一个即可。

证明如下：

考虑答案的两个显然的下界，$t\ge ma{x}_{i\in T}(de{p}_i)$，$t\ge \frac{n}{m}$。

显然前面那个是机器数较多的情况，后面那个是机器数较少的情况。

然后将节点按深度分两块，任取一个深度$\alpha$，有

$$t\ge \alpha -1+\frac{\sum _{i=\alpha }^n{p}_i}{m}$$

显然最早在时刻$\frac{\sum _{i=\alpha }^n{p}_i}{m}$时深度不小于$\alpha$的节点才能被处理完，此时至少会剩下一个深度为$\alpha -1$的节点，至少还需要$\alpha -1$时间才能完成，因此这是总用时的一个下界。(显然对于$\alpha =1$时也成立，但上面的叙述有问题)

下面证明$t\ge ma{x}_{\alpha }(\alpha -1+\frac{\sum _{i=\alpha }^n{p}_i}{m})$是一个紧下界。

考虑最大值时$\alpha$取到的$\beta$，如果有多个则取最小的，则有

$$\mathrm{\forall }d<\beta ,\frac{\sum _{i=d}^{\beta -1}{p}_i}{\beta -d}<m$$

上式显然成立，否则$\alpha$取$d$的函数值不比$\alpha$取$\beta$时小。

根据当前树的深度是否小于$\beta$，我们按时间序将算法分为前半部分和后半部分。

下面证明，假设深度不小于$\beta$的节点全部被完成后，剩下的节点只需要$\beta -1$时间就能完成。

首先归纳证明，算法执行过程中，任意时刻树中深度最大的任意$k$层节点，每层的节点均值都小于$m$。

形式化的表述是，设树的深度为$h$，则有$\frac{\sum _{i=d}^h{p}_i}{h-d+1}<m$。$(1)$

也就是和上面一样的形式。

采用归纳法，反证，假设经过了$1$时间后深度至少为$d$的部分不满足条件，取最大的$d$。

根据假设，显然有$p_d\ge m$，否则深度至少为$d+1$的部分也满足条件，与$d$最大矛盾。

考虑此时深度为$d$的这些点构成的子树，显然每个子树至少有一个叶节点，因此当前深度不小于$d$的叶节点有至少$m$个。

删掉一个节点后，深度不小于$d$的节点个数单调不减，因此上一次深度不小于$d$的叶节点个数不小于$m$，根据算法流程可知上次删掉的节点深度至少为$d$。

则上次深度不小于$d$的节点有$\sum _{i=d}^h{p}_i+m$个，$h$是当前树的深度，$p_i$是当前树中深度为$i$的节点个数。

$$\sum _{i=d}^h{p}_i\ge m(h-d+1)$$

$$\sum _{i=d}^h{p}_i+m\ge m(h-d+2)$$

即上次深度不小于$d$的部分也不满足条件，与归纳条件矛盾，因此命题$(1)$得证。

由命题$(1)$可得，算法执行后半部分的任意时刻，深度最大的节点个数不超过$m$，因此只需要树的深度时间就能够执行完所有深度小于$\beta$的节点。

下面证明删掉深度不小于$\beta$的节点只需要$\lceil \frac{\sum _{i=\beta }^n{p}_i}{m}\rceil$时间。

由$\beta$的定义，可以得到如下结论：

$$\mathrm{\forall }d\ge \beta ,\frac{\sum _{i=\beta }^d{p}_i}{d-\beta +1}\ge m$$

否则$\alpha$取$d$的函数值比$\alpha$取$\beta$时大。

下面证明，算法执行前半部分的任意时刻，设当前树的高度为$h$，深度为$i$的节点有$p_i$个，则对于任意的$\beta \le d<h$，满足上述条件

$$\mathrm{\forall }\beta \le d<h\frac{\sum _{i=\beta }^d{p}_i}{d-\beta +1}\ge m(2)$$

使用归纳法，反证，假设经过$1$时间后深度为$\beta$到$d$的部分不满足条件，取满足条件最小的$d$。

这个单位时间内显然删掉了至少一个深度为$d$的节点。(上一时刻时这一部分还满足条件)

这说明之前深度大于$d$的部分叶节点不足$m$个。

若$d\ge h$，则当前的$d$不在定义域中，自然不影响成立性。

若$d<h$，则此时这一时刻内一定删掉了所有深度为$h+1$的点。

由于深度大于$d$的叶节点个数随时间单调不减，且上一时刻深度大于$d$叶节点个数不足$m$，所以只需要$h-d$时间就能将所有深度大于$d$的部分删去，因此在上一时刻有

$$\sum _{i=\beta }^d{p}_i<(d-\beta +1)m+D$$

其中$D$为删掉的深度为$d$的节点个数。

深度不少于$d+1$的叶节点至少有$p_{d+1}$个，因此$D\le m-p_{d+1}$。

因此得到

$$\sum _{i=\beta }^{d+1}{p}_i<(d-\beta +2)m$$

又$d<h$，因此上一时刻取$d=d+1$时条件不满足，与归纳基础矛盾，因此命题$(2)$得证。

因此当深度大于$\beta$时恒有$p_{\beta }\ge m$，即深度不小于$\beta$的叶节点个数$\ge m$，每次都能取满$m$个。在深度为$\beta$处至多一次取不满$m$，因此前半部分可以在$\lceil \frac{\sum _{i=\beta }^n{p}_i}{m}\rceil$内完成。

综上，算法正确性和用时下界都得到了证明。

这个算法可以做到$O(n)$的，想必大家都会，也不是重点，于是就没设分。

按深度贪心也是正确的，证明主要思路采用调整法；按大小贪心也是正确的，证明主要思路采用反证法。证明繁杂赛后我在uoj博客发一下证明。

配对树

from C_SUNSHINE， 题解 by C_SUNSHINE

子任务 1

我们可以暴力枚举ddl区间，然后在树上做树形DP来计算最小匹配的大小，如何DP呢？

令 $f_{i,j}$ 表示 $i$ 的子树内还有 $j$ 个点没匹配的匹配大小，然后计算转移边需要被覆盖几次。这个想法明显太傻了，我们不可能让子树内的点拉到子树外面配对的，如果存在两个点 $x,y$ 他们在子树内都没有配对，那么假设他们分别和 $x^{\prime },y^{\prime }$ 配对，显然 改为 $x,y$ 配对 $x^{\prime },y^{\prime }$ 配对更优，所以 $j$ 只能是 $0$ 或1。

接着发现其实 $j$ 的奇偶性和子树内ddl数目的奇偶性相同，于是直接dp即可。

时间复杂度 $O(m^{2}n)$。

子任务 2

我们接着观察，对于一个确定的ddl区间，一条树边被匹配包含了当且仅当把它删去后树被分成两个包含奇数个ddl的块。若我们令 $1$ 为根做dfs，则一个非根点父向边被包含当且仅当其子树内有奇数个ddl。

我们可以换一种方式思考，计算一条树边被多少个偶区间覆盖。

枚举一条树边，把它子树内的ddl全部在序列上标为 $1$ 其余标为 $0$，来把序列转成 $01$ 串，于是问题变成了统计 $01$ 串中包含偶数个 $1$ 的子串数目。

对 $01$ 串做前缀和得到 $s_i$，则一个区间 $[l,r]$ 要被统计当且仅当 $s_r-s_{l-1}\equiv 1(\mathrm{mod}2)$ 由于 $l-1\equiv r(\mathrm{mod}2)$，我们可以对 $s_i(0\le i\le m)$ 按照下标奇偶性分别维护，维护对 $i\mathrm{mod}2=k=0$ 或 $1$ 分别计算 $s_i$ 中奇数的数目 $cn{t}_{k,1}$ 和偶数的数目 $cn{t}_{k,0}$。那么包含这条树边的区间数目就是 $cn{t}_{0,0}\cdot cn{t}_{0,1}+cn{t}_{1,0}\cdot cn{t}_{1,1}$。

把序列转化成 $01$ 串需要 $n+m$ 的时间，统计 $cnt$ 需要 $O(m)$ 的时间，于是时间复杂度为 $O(n^2+nm)$。

子任务 3

这个直接把不超过 $100$ 个点的虚树建出来之后暴力即可。

子任务 4

我们可以考虑使用线段树来维护序列转化成的 $01$ 串，可以发现，我们只需要在线段树区间上维护区间内的 $cn{t}_{k,0/1}$，通过左半边内 $1$ 的数目来决定是否对右边进行反转，就可以 $O(1)$ 时间合并左右区间，最终需要的 $cnt$ 的值会统计在根节点上。

既然单次修改 $01$ 序列是 $O(\log m)$ 的，我们可以枚举每条边，然后只加入其子树，总修改次数为 $O(n^2)$，于是复杂度为 $O(n^2\log m)$。

子任务 5

这条件其实没什么特别的用处，只是让点的分步均匀一些。

子任务 6

树是随机的，我们依旧暴力枚举树边然后只添加子树，可以发现每个点会被添加恰好深度次，而深度的期望是 $O(\log n)$ 的，所以总修改次数的期望也是 $O(m\log n)$ 的，总复杂度就是 $O(m\log n\log m)$ 的。

子任务 7

在本来的做法中，我们对子树做完后，清空线段树再吧子树内的 ddl 重新加入，可以发现这个过程中有重复计算。考虑对于每个点 $x$ 我们在 dfs 完其最后一个孩子之后，不清空 dfs 时的修改，而是把其他孩子子树内的 ddl 直接补上，令 $x$ 的最后一个孩子为 $so{n}_x$， $x$ 到 $so{n}_x$ 的边称为特殊边，可以发现，一个 ddl 被添加次数为其到跟的路径上非特殊边的数目。

到这里其实算法已经很显然了，对树轻重链剖分，$so{n}_x$ 就是 $x$ 的重孩子，一个 ddl 被添加的次数就是其到根的路径上轻边的数目是 $O(\log n)$ 的，采用线段树维护的话复杂度就是 $O(m\log n\log m)$，这个算法可以通过本题。提交记录点这里

因为NOI之前信心赛大家开心就好，所以两个 $\log$ 是可以通过的。

这题我本来出出来准备当个前两题的难度的，但不知道哪个管理员就把它挂到 C 题上了，我给他题解的时候还把这段话删了，所以两个 $\log$ 是可以通过的。

想到用线段树维护后，本题有个较为直接的做法即采用线段树合并，每个点的线段树可以看成其所有子树并起来再插入其上的 ddl，我们知道 $m$ 个只有一个元素的线段树合并的复杂度为 $m\log m$，所以直接采用线段树合并可以做到 $O(n+m\log m)$ 的复杂度，只不过空间是 $\mathrm{\Theta }(m\log m)$ 的。提交记录点这里 不过采用 Splay 做合并的话，空间可以做到 $O(n)$。

你要问我为啥就是个 Splay 合并却写这么长题解，我只能说……既然管理员钦点了，得装的像个 C 题的样子（逃