B3666题解

continueOI · 2022-11-20 11:09:42 · 题解

题目描述

给定一个数列 a，初始为空。有 n 次操作，每次在 a 的末尾添加一个正整数 x。

每次操作结束后，请你找到当前 a 所有的后缀最大值的下标（下标从 1 开始）。一个下标 i 是当前 a 的后缀最大值下标当且仅当：对于所有的 i < j \leq |a|，都有 a_i > a_j，其中 |a| 表示当前 a 的元素个数。

为了避免输出过大，请你每次操作结束后都输出一个整数，表示当前数列所有后缀最大值的下标的按位异或和。

解析

很容易就可以想到，用暴力方法求解：每输入一个数，将其与之前的所有后缀最大值的数遍历，如果比那个数大，那么就将那个数删除。

利用栈这个数据结构，将当时的后缀最大值入栈，如果遍历后不是后缀最大值了，那么便出栈。便可以得到一下核心代码：

while(top&&(stk[i]>=stk[ans[top]]))
    temp^=ans[top--];

解释一下，这里的 top 是头指针，用数组模拟栈，top 既可以反映出栈内总共的元素数量，也可以用 ans[top] 反映栈空间内最上面的元素值，若要弹出元素只用将 top-- 即可，压入一个元素只要 ans[++top]=i 即可。

显然，每个元素至多只会压入栈中一次，也至多只会弹出一次，所以时间复杂度为 O(n)。因为共有 n 个数，所以单次输入比较输出结果的时间复杂度均摊大概是 O(1) 的。

注意，由于对于全部的测试点，保证 1 \leq n \leq 10^6，1 \leq x_i \lt 2^{64}，所以需要开 unsigned long long。

最后上代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,top,temp;
unsigned long long stk[N],ans[N];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);//输入输出加速
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>stk[i];
        while(top&&(stk[i]>=stk[ans[top]]))
            temp^=ans[top--];
        ans[++top]=i;
        temp^=i;
        cout<<temp<<'\n';
    }
    return 0;
}