24.12.20

· · 个人记录

CF1930H

概述：交互库给你一棵树，你需要在所有询问开始前给交互库两个排列 p1,p2，随后交互库每次生成一个排列 a 与两个点 u,v，要让你求树上 u,v 路径间 a_i 的 mex，你可以询问 5 次两个排列上的区间最小值。n\times q\le3\times 10^6。

解法：对于排列，显然有 mex_{i\in S}a_i = \min_{i\not \in S}a_i，因此我们可以将原问题转为询问路径补集的 \min。路径补集刻画为比 lca 的 dfn 还小的点，比 \max(dfn_u,dfn_v) 还大的点，以及路径上所有点左右挂着的点。

先让 p_1 为原 dfn 序，对上述两种点询问，发现第二种点包括了 lca \to v 链上的挂在右边的点。启发我们让 p2 为反着的 dfn，询问 >dfn_u 的点，这样也包括了 lca\to u 链上挂在左边的点。

考虑剩下的点，容易发现 lca\to u 的右边的点显然满足 dfn_u<dfn_i<dfn_p，其中 p 是 lca\to v 链上的第二个点。因此询问一次即可。 lca\to v 同理。

qoj8922

概述：

赛跑场地始终相同，都有 $m$ 个存档点，坐标依次为 $s_i$。最后一个存档点是终点。初始时所有人从 $0$ 出发，每次有人遇到存档点时其他所有人都会传送回自己的上一个存档点（同时则编号小的视为先到）。到终点的人不会被传送。 求问每场比赛的总传送次数。$n,m,s_m\le 1.5\times 10^5,t_i\le 10^9$。 思路： 考虑传送事实上只是某个人前进了一个存档点，每两次传送之间互不影响。 对于两个人 $i,j$，若 $i$ 更快则 $i$ 一定让 $j$ 传送了 $m$ 次。因此我们答案至少是 $\frac {i(i-1)} 2$。 再考虑更多传送的部分，事实上是较慢的 $j$ 由于走的距离短导致了 $i$ 的传送。那么这个时候我们完全可以视为 $i$ 在走最长的一段（总时间消耗最大），而 $j$ 在走某个前缀最大值（前一个时间比后一个长，那么走完前一个后必然会马上走下一个）。再根据上面说的传送互不影响，我们发现最终答案就是所有 $(i,j)$ 传送次数的和。 由此得到一个看似 $O(n^2m)$ 的算法，暴力枚举 $(i,j)$，再根据前缀 $\max$ 们暴力判断 $j$ 会走到哪里。但是发现各段长总和仅有 $1.5\times 10^5$ 种，因此前缀 $\max$ 数量仅 $\sqrt V$ 种。做到 $O(n^2\sqrt V)$。 优化是显然的：考虑每次加入一个人 $i$，对他之前的人与他的快慢关系讨论。$i$ 较快则是枚举前缀 $\max$，分成 $\sqrt V$ 个区间询问。容易想到一个 $\sqrt V\log n$ 做法：区间询问用树状数组维护，而找到区间用二分。前半部分经典平衡规划；后半部分由于前缀 $\max$ 数量少，区间左右端点单增，因此双指针预处理即可。$i$ 较慢时是对偶平衡规划问题，不细讲。至此本题做到 $O(n\sqrt n)$。