自动搬运

查看原文

来自洛谷，原作者为

	Kingna We live and die in the shadows for those we hold close and for those we never meet.

搬运于2025-08-24 23:09:54，当前版本为作者最后更新于2025-02-14 22:34:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Subtask #1~2

考虑 $O(Qn^2\log n)$ 的暴力，期望得分 $20$ 分。

Subtask #7

$0\leq x\leq 1$ 答案为区间总数。且所有询问答案相等，求异或值时，如果 $Q$ 为偶数，答案就是 $0$。实际上在数据中 $Q$ 确实是偶数。

Subtask #4~5

询问的是一个后缀，直接预处理。考虑第 $k$ 大值至多 $n$ 种，那么对每一个 $a_i$ 处理出有多少个区间的第 $m$ 大值为 $a_i$，则等于 $a_i$ 的区间个数就可以求解。查询的时候，直接二分寻找答案。

考虑到区间 $[l,r]$ 用 $a_i$ 作为第 $m$ 大值，那么区间 $[l,r]$ 中就恰好有 $m-1$ 个数大于 $a_i$。那么我们找到比 $a_i$ 大的位置。可能有下列 $m$ 种情况：

• 左边有 $m-1$ 个比 $a_i$ 大，右边有 $0$ 个比 $a_i$ 大。
• 左边有 $m-2$ 个比 $a_i$ 大，右边有 $1$ 个比 $a_i$ 大。
• 以此类推。左边有 $0$ 个比 $a_i$ 大，右边有 $m-1$ 个比 $a_i$ 大。

不难发现，还需要解决区间长度大于等于 $K$ 的问题。这等价于左端点从 $[L_1,R_1]$ 中选择，右端点从 $[L_2,R_2]$ 中选择，区间长度大于等于 $K$ 的选择方案数。可以用数学方法在 $O(1)$ 时间内求解。

现在只需要找到比 $a_i$ 大的位置。如果花费 $O(\log n)$ 时间去找每一个位置，比如 ST 表或线段树，则总复杂度为 $O(nm\log n)$。期望得分 $56$。

Subtask #8

用链表存储所有数字。按照 $a_i$ 从小到大扫的顺序，如果当前 $a_i$ 计算完毕，直接从链表中删除。此时链表中剩余的数字就是大于 $a_i$ 的数。

查找比 $a_i$ 大的位置时，只需要左跳右跳就行。复杂度 $O(nm)$。

期望得分 $100$。