Solution Set - HYBC #3

答案为 \(\min(c_u,c_d)+\min(c_l,c_r)\)。

Link

简单模拟就行，随便搞搞做到 \(O(n)\)。

Link

设异或和为 \(x\)，总和为 \(y\)，构造 \(x,x+y\) 即可。

Link

设两个相同的数位置为 \(i,j\)，则大小为 \(k\) 的子序列重复的个数为 \(\binom{i-1+n-j}{k}\) 种，减掉就行了。

Link

\((u,v)\) 表示 \(u\) 控制 \(v\)，条件是 \(v\in \text{subtree}(u)\) 和 \(dis_v-dis_u\le a_v\)。

这是一个显然的二维数点，可以使用多种数据结构解决，在此不谈。

代码使用线段树合并。

Link

发现不是很好做，考虑二分，二分一个 \(s\)，接下来变成 check 一个 \(s\) 合不合法。

显然的事情是，在确定了 \(a_i\) 之后，对于所有 \(a_i > b_i\)，\(c_i=r_i\)，否则 \(c_i=r_i\)。

考虑如何确定 \(a_i\)，以 \(a_i=0\) 为起点，考虑增加 \(a_i\)，在 \(b_i\) 前的贡献是 \(l_i\)，在 \(b_i\) 后的贡献是 \(r_i\)，由此每一个 \(\{b_i,l_i,r_i\}\) 的贡献可以被抽象成一个分段函数 \(f_i(x)\)：

问题则转化为选定 \(x\) 使得 \(\sum f_i(x)\) 最大。可以证明的是，\(x\) 只有一个不取 \(0\) 或 \(X\)，枚举这一个是谁即可。

时间复杂度 \(O(n\log \sum b_i)\)。

Link

下文中，称操作一个点 \(i\) 对应原题中的操作 \(p_{i-1},p_i,p_{i+1}\)。

结论一：被操作的点只可能是初始序列中 \(p_i=i\) 的点。

证明：先证明不会操作 \(p_i\not=i\) 的点，如果进行了操作，则操作后 \(p_{i-1}<p_i<p_{i+1}\)，如果 \(p_i<i\)，为了把 \(p_i\) 移前面去，首先得把 \(p_{i-1}\) 移成 \(>p_i\) 的，又必然要以 \(i-2\) 为中心做一次操作，则 \(p_{i-2}<p_{i-1}>p_i\) 无法交换，\(p_i>i\) 同理。

接下来证明不会操作经过若干次操作变成 \(p_i=i\) 的点，首先这个 \(p_i\) 上一次要么和 \(p_{i-2}\) 交换，要么和 \(p_{i+2}\) 交换，交换后要么 \(p_{i-1}<p_i\) 要么 \(p_{i+1}>p_i\)，那其必然不会被操作。

设 \(b_i=[p_i=i]\)，如果有连续的长度超过三的 \(0\)，则无解，否则，考虑每一个 \(01\) 交叉的小段 \([l,r]\)，这是一个子问题，其有解的条件如下：

• 值域首先得在 \([l,r]\) 内部。
• 不存在长度超过 \(2\) 的下降子序列。

第一个条件是显然的，考虑证明一下第二个条件。

首先如果最长下降子序列长度达到三，那么对于 \(a<b<c\) 定有 \(p_a>p_b>p_c\)，这三个无法交换。

其次就是一次交换不会使最长下降子序列增加，因此可以随意操作直到恢复原样。

这个题做完了。

Link