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

//使用了一个栈来保存下标和值，也可以额外用一个数组来保存值。
//关键点：数列如果保持单调递减，那么所有的数都是后缀极大位置
//如果出现了一个数x>=当前数列最后一个数，那么当前数列后面的数所有<=x的数都要去掉，都不是后缀极大位置了。
//我们去掉这些已经不满足的数，怎么去掉呢？
//可以看出在x出现之前我们的数列一直是单调递减的，那些数我们都用异或记录在ans中
//那么现在我们把不满足的ans去除，就再异或一次就可以，因为ans^x^x=ans
//知道了这些就可以得到答案了
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin>>n;
    stack<pair<int,int>> a;//first存值，second存下标。
    a.push({0,0});
    int cur=0,ans=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        ans^=i;
        while(a.size()&&x>=a.top().first){
            ans^=a.top().second;
            a.pop();
        }
        a.push({x,i});
        cout<<ans<<'\n';
    }
    return 0;
}