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

void solve(){
    int n;cin>>n;
    vector<int> a(n+1), sk(n+1), ans(n+1), pref(n+1);
//几个数组代表的含义分别是序列 栈，每个下标对应的答案，栈中内容的异或前缀和 
    int tp=0;//栈顶索引
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        while(tp>0&&a[sk[tp]]<=a[i])tp--;
        sk[++tp]=i;
        pref[tp]=pref[tp-1]^sk[tp];
        ans[i]=pref[tp];
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<endl;
    }
}

如果一个数是序列的后缀最大值，那么这个数一定比其右侧的所有值都大，这个数也一定会大于其右侧的后缀最大值，

那么就可以维护一个从大到小的单调栈用来存储后缀最大值的索引，每次加入一个新的值，这个值一定会是后缀最大值，就可以把他加入栈中，那么就可以从栈顶往下遍历，小于这个值的就不再是后缀最大值，

这样我们就维护了一个存储当前序列所有后缀最大值的栈，现在需要求这个栈中所有的值的异或和，我们发现，栈中新压入的这个值的下面的值的异或前缀和都是不变的，用前面的异或和再异或一次新加入的元素就是答案，那么就可以维护一个栈的异或前缀和即可