【模板】单调栈
题目描述
给出项数为 \(n\) 的整数数列 \(a_{1 \dots n}\)。
定义函数 \(f(i)\) 代表数列中第 \(i\) 个元素之后第一个大于 \(a_i\) 的元素的下标，即 \(f(i)=\min_{i<j\leq n, a_j > a_i} \{j\}\)。若不存在，则 \(f(i)=0\)。
试求出 \(f(1\dots n)\)。
输入格式
第一行一个正整数 \(n\)。
第二行 \(n\) 个正整数 \(a_{1\dots n}\)。
输出格式
一行 \(n\) 个整数表示 \(f(1), f(2), \dots, f(n)\) 的值。
样例
样例输入
5
1 4 2 3 5
样例输出
2 5 4 5 0
提示
【数据规模与约定】
对于 \(30\%\) 的数据，\(n\leq 100\)；
对于 \(60\%\) 的数据，\(n\leq 5 \times 10^3\) ；
对于 \(100\%\) 的数据，\(1 \le n\leq 3\times 10^6\)，\(1\leq a_i\leq 10^9\)。
[!NOTE]
单调栈原理：把无用数据及时去除（在需要快速找到元素的相对关系（如左右边界、最大/最小值）时特别有用）
典型的使用场景：下一个更大元素问题、区间最值问题、直方图最大矩形问题和滑动窗口问题
单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈
栈中保留的都是比当前入栈元素大的值，并且从栈顶到栈底的元素值是单调递增的
单调递减栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。
栈中保留的都是比当前入栈元素小的值，并且从栈顶到栈底的元素值是单调递减的
[!TIP]
从后往前扫
对于每个点：
①弹出栈顶比其更小的元素
②此时栈顶就是答案
③加入这个元素
#include<cstdio>
#include<stack>
using namespace std;
const int N = 3e6 + 10;
int n, a[N], f[N];//a是需要判断的数组,f是存储答案的数组
stack<int>baka;//创建空栈s来存储数组a中的索引值
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = n; i >= 1; i--)//从数组的末尾开始向前遍历确保在处理某个元素时，栈中存储的是该元素右侧的所有元素的索引
{
while (!baka.empty()&&a[baka.top()]<=a[i])
baka.pop();//栈顶元素存在并大于当前元素，栈顶元素出栈（移除栈中所有小于或等于当前元素a[i]的索引，这些元素不可能成为a[i]右侧的第一个更大元素）
if (baka.empty())
f[i] = 0;//栈为空，说明当前元素a[i]右侧没有更大的元素，则将f[i]设置为0
else f[i] = baka.top();//否则栈顶的元素就是a[i]右侧第一个比它大的元素的索引（赋值给f[i]）
baka.push(i);//当前元素入栈
}
for (int i = 1; i <= n; i++)
printf("%d ", f[i]);
return 0;
}
求数列所有后缀最大值的位置
题目描述
给定一个数列 \(a\)，初始为空。有 \(n\) 次操作，每次在 \(a\) 的末尾添加一个正整数 \(x\)
每次操作结束后，请你找到当前 \(a\) 所有的后缀最大值的下标（下标从 1 开始）。一个下标 \(i\) 是当前 \(a\) 的后缀最大值下标当且仅当：对于所有的 \(i < j \leq |a|\)，都有 \(a_i > a_j\)，其中 \(|a|\) 表示当前 \(a\) 的元素个数
为了避免输出过大，请你每次操作结束后都输出一个整数，表示当前数列所有后缀最大值的下标的按位异或和
输入格式
第一行是一个整数，表示操作次数 \(n\)
第二行有 \(n\) 个整数，依次表示 \(n\) 次操作所添加的整数 \(x_i\)
输出格式
每次操作后请输出一行一个整数，表示当前数列所有后缀最大值下标的按位异或和
样例
样例输入
5
2 1 3 5 4
样例输出
1
3
3
4
1
提示
数据规模与约定
对于全部的测试点，保证 \(1 \leq n \leq 10^6\)，\(1 \leq x_i \lt 2^{64}\)(好大)
[!TIP]
数列a按顺序入单调栈，单调栈里的元素从大到小排序，计算每次每个元素入栈时，栈内元素下标的异或和
模板是找单调递增的栈，本题是找单调递减的栈（栈中每个数字的后缀(第几个出现的数)的 按位异或^和）
单调栈中是当前的后缀最大值，当有数据被移出或进入时，将答案与其下标做异或运算
[!NOTE]
按位异或运算符“^”是双目运算符，其功能是参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为1，参与运算数仍以补码出现
例如 9^5可写成算式如下： 00001001^00000101 00001100 (十进制为12)
异或运算最重要的性质就是自反性 → (a^b) ^ b=a
x ^ x = 0：任何数与自身异或结果为0x ^ 0 = x：任何数与0异或结果为自身
#include <iostream>
#include <stack>
using namespace std;
typedef unsigned long long qwq;
const int N = 1e6 + 10;
qwq a[N]; // 存储输入值
int n, baka = 0; // 存储输入值的下标异或和
stack<int> b; //单调栈存储下标
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%llu", &a[i]);
while (!b.empty() && a[b.top()] <= a[i]) //移除栈中所有<=当a[i] 的下标
{
baka ^= b.top(); // 消除出栈元素影响(出栈前将栈顶元素的下标与baka异或)
b.pop();//栈顶元素出栈
}
b.push(i);//入栈
baka ^= b.top();//更新
printf("%d\n", baka);
}
return 0;
}
