P8873题解

快斗游鹿 · 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)。