比赛链接

Solved by Potassium.

给一个长度为 $n$ 的排列，每次将一段区间升序或降序排列，求最后中间位置的数。

显然可以对答案进行二分。设当前二分的数为 $x$ ，令 $b[i]=(a[i]\ge x)$，模拟每次操作即是区间置 $0$、区间置 $1$ 和区间求和，线段树维护一下即可。

Solved by nikkukun.

在坐标 $[0, 2000] \times [0, 2000]$ 上给 $n \leq 2000$ 条线段，问有多少大小为 $1$ 的格子被至少一条线段穿过。

枚举 $x \in [0, 2000)$，在 $O(n)$ 时间可以计算出每个线段在 $[x, x + 1]$ 的 $y$ 的范围，用前缀和标记一下即可知道覆盖的 $y$ 的个数。

总时间复杂度 $O(Ln)$，$L = 2000$。

Solved by nikkukun & Potassium.

给一个 $n \leq 10^5$ 个结点的树，每次随机选一个点删去，获得连通块大小的分数，问所有删除方案的总得分模 $10^9 + 7$。

考虑删除 $u$ 时，结点 $v$ 做的贡献。$v$ 能对 $u$ 做贡献，当且仅当 $u$ 是 $(u, v)$ 路径上第一个被删除的点。令 $d(u, v)$ 表示 $(u, v)$ 的距离，由于删除是随机的，因此 $u$ 被第一个删掉的概率是 $\dfrac 1{d(u, v) + 1}$，于是问题变成统计树上点对距离个数。

统计点对距离可以用树分治，将所有到根的距离 FFT 卷一下，减去各自子树重复计算的贡献，即可做到总时间复杂度 $O(n \log ^2 n)$。比赛的时候做傻了，抄了拆系数 FFT 的板子，但由于多项式系数之和不超过 $n$，卷出来的结果不超过 $n^2$，因此直接 FFT 精度也是足够的。

Solved by Potassium.

给一个序列，要打乱顺序，最大化相邻两项差的最小值。

先排序，分奇偶讨论，如果是偶数则直接匹配（如，3142，51627384），然后发现奇数的时候 $[i,i+\frac n2]$ 区间仅会有一个可以不被选到，于是枚举这个最小值然后匹配即可。

Solved by qxforever.

给 $n$ 个数，求所有非空子集的权值和第 $k$ 小。$n\le 2\times 10^5,k\le \min(2^ n-1,10^6)$

二分答案 $x$ 。我们只需要找到 $k$ 个权值和 $\le x$ 的子集即可，或者找不到这么多子集，直接搜索的复杂度是 $O(k)$ 的。总时间复杂度 $O(k\log V)$ 。

这题是 Dreamoon 在 从枚举到 K 短路 中提到的一个例题，里面提到的其他用二分 + 搜索 + 剪枝的题目也蛮巧妙的。

Solved by qxforever.

给在第一象限 $n$ 个顶点的简单多边形，问过原点的一条直线最多能把多边形分为几部分。

只有在经过顶点时才会改变答案。极角排序后扫描，根据被扫的点和其相邻两个点的位置关系分为 $8$ 种情况进行讨论。取最大值作为答案。

看了下其他队的，似乎只用分 $4$ 种情况。

Solved by Potassium.

给一棵树，初始每个边都是白色，每次选择两个路径全白的叶结点将其中路径的边全变成黑色，问最少操作步数使得无法继续操作。

可以转化成二叉树的问题，因为如果三个则必然子树内匹配一对。向上传当前子树贡献二叉、枝条或空树，分类讨论一下即可。

Solved by Potassium & nikkukun.

给一个长度为 $n$ 的 $01$ 序列，一次操作是将某个元素取出并插入到任意位置。$q$ 次询问 $k_i$ 次操作后最长的连续 $0$ 长度。

对 $1$ 的操作相当于删掉 $1$ 也即合并两段连续 $0$，对 $0$ 的操作相当于向最长连续 $0$ 段添加 $0$。

考虑求出答案区间 $[l,r]$ 。设 $0,1$ 的前缀和分别为 $s_0,s_1$，则区间满足 $s_{0,r}-s_{0,l-1}\le k$ 条件，且 $(s_{0,r}-s_{0,l-1})+(k-(s_{1,r}-s_{1,l-1}))$ 最大。式子化为求 $(s_{0,r}-s_{1,r})-(s_{0,l-1}-s_{1,l-1})$ 最大的合法区间。设 $f_i=s_{0,i}-s_{1,i}$ ，维护一个递增的单调队列即可求出答案。