自动搬运

查看原文

来自洛谷，原作者为

	快斗游鹿 /bx

搬运于2025-08-24 22:43:19，当前版本为作者最后更新于2022-12-29 15:16:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

提供一种新的解法。目前是最优解。

我们可以这么给数列分段：$[0],[0,1],[0,-1,0],[0,1,2,1],[0,-1,-2,-1,0]\dots$ 显然，这是有规律可循的。假设它们的编号为 $1,2,3\dots$ 接下来可以发现，第 $i$ 段里正好有 $i$ 个数，那么就可以很方便地找出 $a_k$ 属于第几段了。

再观察每一段。对于编号为偶数的段，可以发现其中的数都不是负数，而对于编号为奇数的段，可以发现其中的数都不是正数。我们称每一段里绝对值最大的数为塔顶，可以发现塔顶所处的位置为每段中的第 $1,2,2,3,3\dots$ 项。现在知道了每段的塔顶位置，假设这是该段中的第 $x$ 项，该项数值为 $v$，接着就可以简单分讨一下：

如果是奇数段，则第 $1\sim x$ 项是从 $0$ 开始依次递减的。而第 $x$ 项往后则是从 $v$ 开始依次递增的。

如果是偶数段，则第 $1\sim x$ 项是从 $0$ 开始依次递增的。而第 $x$ 项往后则是从 $v$ 开始依次递减的。

分讨完后容易发现，$a_k$ 是可以 $O(1)$ 查询的，也就是说，总时间复杂度为 $O(q)$。