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

import java.util.*;

import java.io.*;

// 优先队列存的是满足条件得值和下标 小根堆 单调减
// 遇到一个元素就对比队尾元素
// 比该元素小的全部出队
// 输出剩余元素下标亦或和
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int n = in.nextInt();
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] - b[0];
            }
        });
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 1 ; i <= n; i++) {
            int tmp = in.nextInt();
            while (!queue.isEmpty() && tmp >= queue.peek()[0]) {
                map.remove(queue.poll()[0]);
            }
            queue.offer(new int[] {tmp, i});
            map.put(tmp,i);
            Collection<Integer> set = map.values();
            int ans = 0 ;
            for(Integer item :set){
                ans ^= item;
            }
            out.println(ans);
        }
        out.flush();
    }
}