B3666 题解

· · 题解

题目传送门

题意

输入一个数列，每输入一个数后，找到所有它后面的数都比它小的数的下标，并求出这些下标的异或和。

分析

Case 1：如何找到所有后缀最大值

下标 i 不是后缀最大值，当且仅当 a_i 后面有不小于它的数 a_j。那么此后不论输入多少数，都有 a_i \leq a_j，那么 i 就不可能再是后缀最大值了。

如上图，我们把数列中每个数都看作一个人，所有人都向后看，如果看到队尾，就说明这个人的下标是后缀最大值。如果一个人看不到队尾，说明有人把他挡住了，那么他就不可能再看到队尾了，此时我们可以把他移出数列。

每个人进入数列时都会挡住所有比他矮的人，此时，移出所有比他矮的人。那么易知数列总是单调递减的。所以当我们需要移出人的时候，只需要从队尾移出，直到队尾的人比要进来的人高。

这不就是单调栈吗？

Case 2：求异或和

异或运算最重要的性质就是自反性。

也就是 (a \oplus b) \oplus b = a。

我们维护的单调栈中都是当前的后缀最大值，所以当有人被移出或进入时，将答案与他的下标做异或运算即可。

为了方便大家抄代码学习，我就把代码放在这了。

#include<cstdio>
#include<stack>
using namespace std;

struct node{
    unsigned long long val;//存数据，记得开unsigned long long 
    int num;//存下标 
};

stack<node> a;//单调栈 
int n;
node t; 
int ans = 0;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%llu", &t.val);
        t.num = i;
        while(a.empty() == false && a.top().val <= t.val){//出栈直到栈空或栈顶元素大于当前元素，记得判断栈空，用<= 
            ans ^= a.top().num;//消除出栈元素影响 
            a.pop();
        }
        a.push(t);
        ans ^= a.top().num;
        printf("%d\n", ans);
    }
    return 0； 
}