BISHI121　数列后缀极大位置统计¶

简单通过率 51.16%python3样例通过牛客 AC

牛客原题　源码

讲解章节：单调栈与单调队列、DP 优化

一句话

每次尾部加数后，输出所有后缀最大值下标的异或和。

解题思路¶

这题考什么¶

一个漂亮的等价刻画：「后缀最大值下标的集合」就是单调递减栈本身。

为什么？栈内保持严格递减，意味着栈里每个元素都严格大于它右边所有还在栈里的元素；而一旦某个元素被弹出，说明它右边出现了一个 >= 它的数，「对所有 i<j 都有 a_i > a_j」立刻不成立。两边正好互为充要。

于是每次操作只需：弹掉栈顶所有 a[top] <= x 的下标，再把当前下标压栈。

数据规模与复杂度¶

n <= 1e5。每个下标最多进栈一次、出栈一次，总复杂度 O(n)。

坑在哪¶

弹栈条件必须是 <=（相等也弹）。因为题目要求「严格大于」右边所有元素，相等时条件不成立。写成 < 就 WA——这题唯一的思维点就在这个等号上；
异或和要增量维护：弹出时异或一次、压入时异或一次。异或的自反性（x^x=0）保证了「再异或一次 = 移除」。每次重新 reduce 整个栈是 O(n^2)，1e5 会挂；
下标从 1 开始。

参考实现¶

solutions/BISHI121.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    st = []                                  # 存下标（1-indexed），对应值严格递减
    xor = 0                                  # 栈内全部下标的异或和，随栈同步维护
    out = []
    push = out.append
    for i in range(1, n + 1):
        x = a[i - 1]                         # 栈存 1-indexed 下标，取值时要减 1
        # 被 x 挡住的元素永远不再是后缀最大值，出栈的同时把它从异或和里剔除
        while st and a[st[-1] - 1] <= x:     # 相等也要弹（条件是严格大于）
            xor ^= st.pop()                  # 异或的自反性：再异或一次即移除
        st.append(i)
        xor ^= i                             # 新下标入栈，计入异或和
        push(xor)                            # 此刻栈内容 = 当前所有后缀最大值下标
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

BISHI121 数列后缀极大位置统计¶