题解 | #数列后缀极大位置统计#

题目链接

题目描述

有一个初始为空的数列 $A$ 。需要进行 $Q$ 次操作，每次操作在 $A$ 的末尾添加一个正整数。每次操作结束后，需要找到当前数列 $A$ 中所有后缀最大值的下标（从 1 开始），并输出这些下标的按位异或和。

一个下标 $j$ 是后缀最大值，当且仅当 $A[j]$ 大于其后的所有元素，即对于所有 $k > j$ ， $A[j] > A[k]$ 。

解题思路

本题要求在动态添加元素的过程中，高效地维护一个关于后缀最大值下标的统计量（异或和）。

1. 朴素思想与优化方向

一个简单的想法是，每次添加元素后，都从后往前重新扫描整个数组，找到所有的后缀最大值并计算异或和。设当前数组长度为 $i$ ，此操作需要 $\mathcal{O}(i)$ 时间。 $Q$ 次操作的总时间复杂度将是 $\mathcal{O}(Q^2)$ ，对于 $Q \le 10^6$ 的数据规模来说，这显然会超时。

我们需要一个更高效的动态维护方法。关键在于分析当一个新元素 $x$ 被添加到下标 $i$ 时，后缀最大值的集合是如何变化的：

新元素 $A[i]=x$ 的后面没有其他元素，所以它自身一定是后缀最大值。因此，下标 $i$ 总是新集合的一员。
对于一个旧的后缀最大值下标 $j < i$ ，它要继续保持其地位，就必须大于它后面的所有元素，包括新加入的 $x$ 。因此，旧的后缀最大值 $j$ 能“存活”的条件是 $A[j] > x$ 。

这个特性——新来的元素 $x$ 会淘汰掉所有值小于等于它的旧后缀最大值——是使用单调栈的经典信号。

2. 单调栈解法

我们可以维护一个单调栈，用来存储当前所有后缀最大值的 (下标, 值) 对。这个栈具有以下性质：

栈内元素：只有后缀最大值的 (index, value) 对。
单调性：从栈底到栈顶，元素的值是严格单调递减的。

同时，我们用一个变量 xor_sum 来实时追踪当前栈内所有元素下标的异或和。

算法流程：当第 $i$ 个新元素 $x$ (下标从 1 开始) 到来时：

出栈 (维护单调性): 从栈顶开始，循环判断。如果栈顶元素的值小于或等于新元素 $x$ ，说明它不再是后缀最大值了。将其从栈顶弹出，并将其下标从 xor_sum 中“移除”（通过再次异或操作：xor_sum ^= popped_index）。
入栈: 将新元素的 (i, x) 压入栈中。它现在是后缀最大值集合的一员。将其下标加入 xor_sum（xor_sum ^= i）。
输出: 经过上述操作后，xor_sum 的值就是当前所有后缀最大值下标的异或和。

复杂度分析：每个元素最多入栈一次、出栈一次。因此，对于 $Q$ 次操作，总的时间复杂度为 $\mathcal{O}(Q)$ ，空间复杂度为 $\mathcal{O}(Q)$ （最坏情况下，栈中会存储所有元素）。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct Node {
    int index;
    int value;
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> q;

    vector<int> a(q);
    for (int i = 0; i < q; ++i) {
        cin >> a[i];
    }

    stack<Node> s;
    long long xor_sum = 0;

    for (int i = 0; i < q; ++i) {
        int current_val = a[i];
        int current_idx = i + 1;

        while (!s.empty() && s.top().value <= current_val) {
            xor_sum ^= s.top().index;
            s.pop();
        }

        s.push({current_idx, current_val});
        xor_sum ^= current_idx;

        cout << xor_sum << "\n";
    }

    return 0;
}

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static class Node {
        int index;
        int value;

        Node(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();

        Deque<Node> s = new ArrayDeque<>();
        long xorSum = 0;

        for (int i = 1; i <= q; i++) {
            int currentVal = sc.nextInt();

            while (!s.isEmpty() && s.peekLast().value <= currentVal) {
                xorSum ^= s.pollLast().index;
            }

            s.offerLast(new Node(i, currentVal));
            xorSum ^= i;

            System.out.println(xorSum);
        }
    }
}

import sys

def solve():
    q_str = sys.stdin.readline()
    if not q_str:
        return
    q = int(q_str)
    
    a_str = sys.stdin.readline()
    if not a_str:
        return
    a = list(map(int, a_str.split()))

    s = []  # Monotonic stack: [(index, value)]
    xor_sum = 0

    for i in range(q):
        current_val = a[i]
        current_idx = i + 1

        while s and s[-1][1] <= current_val:
            xor_sum ^= s.pop()[0]
        
        s.append((current_idx, current_val))
        xor_sum ^= current_idx

        sys.stdout.write(str(xor_sum) + '\n')

solve()

算法及复杂度

算法: 单调栈
时间复杂度: 数组中的每个元素最多被压入和弹出栈一次，因此总的时间复杂度是 $\mathcal{O}(Q)$ 。
空间复杂度: 栈中最多存储 $Q$ 个元素，因此空间复杂度为 $\mathcal{O}(Q)$ 。