刷题日记day10(单调栈+异或运算)-程序员充电站

简介

本篇介绍一道单调栈的模板题，为洛谷黄题目，希望读者阅读完本篇之后可以阅读一下刷题日记day10(单调队列)配合食用效果更佳

前置知识

异或运算的性质

本题的运算中只运用到了这三种性质，剩余的性质我们放在该篇的末尾

题目描述

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

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

题目描述

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

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

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

输入格式

第一行是一个整数，表示操作次数n nn。
第二行有n nn个整数，依次表示n nn次操作所添加的整数x i x_ixi。

输出格式

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

输入输出样例 #1

输入 #1

5 2 1 3 5 4

输出 #1

1 3 3 4 1

说明/提示

数据规模与约定

对于全部的测试点，保证1 ≤ n ≤ 1 0 6 1 \leq n \leq 10^61≤n≤106，1 ≤ x i < 2 64 1 \leq x_i \lt 2^{64}1≤xi<264。请注意大规模数据输入输出对程序效率产生的影响。

思路分析

由题意可知，我们要维护这样一个单调递减的序列，并存储它的下标进行异或运算，需要注意的是，我们每一个输出的ans，都是在考虑完第i个元素后，当前栈中下标的异或总和，有些数字可能后续会被弹出栈中，为了简化运算，避免每次都要将栈中的元素计算一遍(这样就会超时)，所以我们采用如下计算方法。

异或和的计算
我们在弹出元素前进行一次异或操作，在加入元素后进行一次异或操作。为了保持单调栈的结构，我们后续会将一些之前压入栈的元素弹出，此时为了保证，我们要输出的答案是考虑第i个元素后，完整的单调栈元素的异或和，我们就要进行ans^=stk.top();这个操作，请大家仔细想想，这个元素是不是第二次乘到ans当中(这个非常重要)，联系到我们前面的性质，这个stk.top()的下标是不是就从异或总和中剔除了，讲到这里大家应该就明白了，通过这个操作，我们每次只需要o(1)就能算出答案。

代码展示

#include<iostream>#include<algorithm>#include<stack>usingnamespacestd;typedefunsignedlonglongll;constintN=1e6+10;intn,ans;stack<int>stk;ll a[N];intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%llu",&a[i]);for(inti=1;i<=n;i++){while(!stk.empty()&&a[stk.top()]<=a[i]){ans^=stk.top();stk.pop();}stk.push(i);ans^=i;printf("%d\n",ans);}return0;}

细节问题

注意严格单调递减

与B3667的联系(在简介提到的那篇题解当中)

在P3667中我们是需要保证区间的长度恒定为k，所以在后续我们不断加入元素的过程中，假设我们此时已经把第i个元素加入容器当中，且容器的首元素值小于i-k+1(即小于左边界)，(B3666为栈，B3667为队列)，我们需要把超出容器长度的部分删掉，但是我们的栈是没有弹出容器头部元素操作的，所以我们采用双端队列deque。~~我感觉这样的解释其实更符合B3667题目的思路~~

AI注释后的代码

#include<iostream>#include<algorithm>#include<stack>usingnamespacestd;typedefunsignedlonglongll;// 重定义无符号长整型，存储输入的大数x，避免溢出constintN=1e6+10;// 数组最大长度，适配1e6次操作intn,ans;// n：操作次数；ans：当前后缀最大值下标的异或和（初始默认为0，异或的单位元）stack<int>stk;// 单调栈，存储后缀最大值下标（栈内下标对应a值严格递减）ll a[N];// 存储每次添加的正整数xintmain(){// 输入操作次数nscanf("%d",&n);// 输入n次操作的x值，存入数组a（下标从1开始）for(inti=1;i<=n;i++)scanf("%llu",&a[i]);// 遍历每次操作，维护单调栈并计算异或和for(inti=1;i<=n;i++){// 维护单调栈：移除不再是后缀最大值的下标// 若栈顶下标对应的值 ≤ 当前值a[i]，则栈顶下标失去后缀最大值资格while(!stk.empty()&&a[stk.top()]<=a[i]){ans^=stk.top();// 异或自反性（x^x=0）：将栈顶下标从异或和中移除stk.pop();// 弹出栈顶无效下标}stk.push(i);// 新下标i加入栈（i一定是后缀最大值下标）ans^=i;// 将i加入异或和（0^i=i，非0则累加）printf("%d\n",ans);// 输出当前所有后缀最大值下标的异或和}return0;}