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

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

题目链接

题目描述

初始数列为空，依次在末尾追加 $q$ 个正整数。每次追加后，设当前长度为 $i$ ，若下标 $p$ 满足对所有 $p\le j\le i$ 均有 $a_j\le a_p$ ，则称 $p$ 为“后缀极大”的位置。请在每次操作后输出所有“后缀极大”下标的按位异或值。

解题思路

维护一个“后缀极大位置”的单调栈（下标递增，值非降）。当在位置 $i$ 追加值 $x$ ：

不断弹出所有值 $<x$ 的栈顶位置（它们不再是后缀极大），同时把这些下标从答案按位异或中移除；
将新位置 $i$ 入栈，并把 $i$ 与答案按位异或；
注意当 $x$ 与栈顶值相等时，旧位置仍是后缀极大（允许相等），不弹出。

每个下标最多进栈出栈一次，总复杂度 $\mathcal{O}(q)$ 。

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q; if (!(cin >> q)) return 0;
    vector<pair<int,long long>> st; st.reserve(q); // (index, value)
    int ans = 0;
    for (int i = 1; i <= q; ++i) {
        long long x; cin >> x;
        while (!st.empty() && st.back().second < x) {
            ans ^= st.back().first;
            st.pop_back();
        }
        st.emplace_back(i, x);
        ans ^= i;
        cout << ans << '\n';
    }
    return 0;
}

import java.io.*;

public class Main {
    static class FastScanner {
        private final InputStream in; private final byte[] buf = new byte[1<<16];
        private int p=0,l=0; FastScanner(InputStream is){in=is;}
        private int read() throws IOException { if(p>=l){ l=in.read(buf); p=0; if(l<=0) return -1; } return buf[p++]; }
        int nextInt() throws IOException { int c; int s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
        long nextLong() throws IOException { int c; long s=1,x=0; do{c=read();}while(c<=32); if(c=='-'){s=-1;c=read();} while(c>32){ x=x*10+(c-'0'); c=read(); } return x*s; }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int q = fs.nextInt();
        int[] idx = new int[q];
        long[] val = new long[q];
        int top = 0; // stack size
        int ans = 0;
        for (int i = 1; i <= q; i++) {
            long x = fs.nextLong();
            while (top > 0 && val[top-1] < x) {
                ans ^= idx[top-1];
                top--;
            }
            idx[top] = i; val[top] = x; top++;
            ans ^= i;
            System.out.println(ans);
        }
    }
}

import sys

data = sys.stdin.buffer.read().split()
it = iter(data)
q = int(next(it))

stack_idx = [0]*q
stack_val = [0]*q
top = 0
ans = 0

out_lines = []
for i in range(1, q+1):
    x = int(next(it))
    while top > 0 and stack_val[top-1] < x:
        ans ^= stack_idx[top-1]
        top -= 1
    stack_idx[top] = i
    stack_val[top] = x
    top += 1
    ans ^= i
    out_lines.append(str(ans))

sys.stdout.write('\n'.join(out_lines))

算法及复杂度

算法：单调栈（值非降）维护后缀极大位置，异或值增量更新
时间复杂度： $\mathcal{O}(q)$
空间复杂度： $\mathcal{O}(q)$