原题

【洛谷】B3666 求数列所有后缀最大值的位置

求数列所有后缀最大值的位置

题目描述

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

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

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

输入格式

第一行是一个整数，表示操作次数 ​n。
第二行有 ​n 个整数，依次表示 ​n 次操作所添加的整数 ​x_i。

输出格式

每次操作后请输出一行一个整数，表示当前数列所有后缀最大值下标的按位异或和。

样例 #1

样例输入 #1

5
2 1 3 5 4

样例输出 #1

1
3
3
4
1

提示

数据规模与约定

对于全部的测试点，保证 ​1 \leq n \leq 10^6，​1 \leq x_i \lt 2^{64}。

按位异或和

例：

按位异或和：
在数列 1,1,4,5,1,4中,她们的异或和即 1⨁1⨁4⨁5⨁1⨁4。

同时有：
由于对某数而言，对它按位异或两次就等于没有对它按位异或。

所以对这题而言，我们可以在每个数进栈与出栈是都进行一次按位异或，最后得到的就是栈中数的按位异或和。

计算下标

该题的另一个重点在于要求计算的是目标数据的下标。

为了将键值和对应下标绑定，这里可以使用结构体处理（其实用pair也行，方法有很多）

struct ele {
    int num;//下标
    unsigned long long var;//值
};

使用结构体数组模拟栈

ele stk[MAX];

模拟单调栈

这里为了速度，我们选择数组模拟单调栈，使得栈内是严格递增序列。

每次输入时都用while循环比较新数据与栈顶数据，若栈顶数据小于等于新数据，则弹出栈顶，最后将新数据压入栈内。

注意数据范围

不开unsigned long long原地爆炸

AC代码参考

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <iostream>

using namespace std;

const int MAX = 1e6 + 10;

int tt;

struct ele {
   int num;//下标
   unsigned long long var;//值
};

ele stk[MAX];

int main()
{
   int n;
   cin >> n;
   unsigned long long ans = 0;
   for(int i = 1; i <= n; i++)
   {
       ele x;
       scanf("%llu", &x.var);
       x.num = i;//读入数据
       while (tt && stk[tt].var <= x.var)
       {
           ans ^= stk[tt].num;
           tt--;
       }//判断栈顶与新数据关系
       {
           tt++;
           stk[tt].var = x.var;
           stk[tt].num = x.num;
           ans ^= x.num;
       }//更新栈顶和答案
       printf("%llu\n", ans);
   }
   return 0;
}