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

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 高效输入输出流，应对大规模数据
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 栈存储后缀最大值的[值, 下标]，维护严格递减序列
        Deque<int[]> stack = new ArrayDeque<>();
        int currentXor = 0; // 存储当前所有后缀最大值下标的异或和

        for (int i = 0; i < n; i++) {
            int x = Integer.parseInt(st.nextToken());
            int index = i + 1; // 下标从1开始

            // 弹出所有小于等于当前元素的栈顶元素（它们不再是后缀最大值）
            while (!stack.isEmpty() && stack.peek()[0] <= x) {
                int[] top = stack.pop();
                currentXor ^= top[1]; // 移除栈顶元素的下标异或
            }

            // 当前元素成为新的后缀最大值，入栈并更新异或和
            stack.push(new int[] {x, index});
            currentXor ^= index;

            // 输出当前异或和
            out.println(currentXor);
        }

        out.flush();
    }
}