B3666 求数列所有后缀最大值的位置
一扶苏一
·
·
题解
B3666 求数列所有后缀最大值的位置
Preface
我私心里希望这道题成为单调栈的第一模板题，因为它揭示了单调栈的本质，即维护所有前缀的后缀最值。
但是这题自 10 月 1 日被我造出来起就没人写题解，我只能自己写一份（
Description
给定一个数列 a，初始为空。有 n 次操作，每次在 a 的末尾添加一个正整数 x。
每次操作结束后，请你找到当前 a 所有的后缀最大值的下标（下标从 1 开始）。一个下标 i 是当前 a 的后缀最大值下标当且仅当：对于所有的 i < j \leq |a|，都有 a_i > a_j，其中 |a| 表示当前 a 的元素个数。
为了避免输出过大，请你每次操作结束后都输出一个整数，表示当前数列所有后缀最大值的下标的按位异或和。
### Analysis
考虑用一个栈按顺序维护当前数列的所有后缀最大值的位置（下标）。初始时栈是空的。
注意到这个栈里下标对应的数列元素（而不是下标本身）是单调递减的。
举个例子，设当前数列是 $\{a\} = 5, 3, 4, 1, 2$，那么栈中的数列下标（自底向顶）应该是 $1, 3, 5$，对应的在数列里对应的元素是 $a_1 = 5, a_3 = 4, a_5 = 2$。$5,4,2$ 这个数列是单调递减的。
考虑加入一个新数 $a_x$ 时，首先新加入的数显然是当前数列的后缀最大值。我们考虑数列其他后缀最大值如何变化：
1. **如果原有的某个后缀最大值所在的下标 $y$ 满足 $a_y > a_x$，则 $y$ 不受影响，仍是后缀最大值下标**。因为对 $y < z < x$，都有 $a_y > a_z$（否则 $y$ 不可能是原有的后缀最大值下标）；又 $a_y > a_x$，于是对 $y < z \leq x = |a|$，都有 $a_y > a_z$，这符合后缀最大值的定义。
2. **如果原有的某个后缀最大值所在的下标 $y$ 满足 $a_y \leq a_x$，则 $y$ 将不再是数列的后缀最大值下标**。这一点是显然的，因为 $x > y$ 而 $a_x \geq a_y$，故 $y$ 自然不能是后缀最大值下标。
3. **如果某个下标 $y$ 原先不是后缀最大值下标，则插入 $a_x$ 后它仍然不是后缀最大值下标**。这是因为如果 $y$ 不是后缀最大值下标，则一定存在一个 $z > y$ 满足 $a_z > a_y$。插入 $a_x$ 没有导致这个关系的变化，这个关系仍然成立，故而 $y$ 不是后缀最大值下标。
做个总结：插入 $a_x$ 后，会删掉原有后缀最大值下标中那些满足 $a_y \leq a_x$ 的下标 $y$，其他位置不变。然后 $x$ 成为新的后缀最大值下标。
考虑因为这个栈里下标对应的数列元素是单调的，所以要删掉那些不再是后缀最大值下标的 $y$，只需要不断地在这个栈顶部弹出元素（也就是把栈里元素自底向顶写成序列后，不断地从后面删除元素），直到栈为空或栈顶元素 $t$ 满足 $a_t > a_x$。最后将 $x$ 入栈即可。
写作代码就是
```cpp
while (!stk.empty() && a[stk.top()] <= a[x]) stk.pop();
stk.push(x);
```
例如，再上例中，如果新加入一个元素 $a_6 = 4$，我们首先比较栈顶元素 $a_5 = 2 < a_6 = 4$，故将 $5$ 弹出；然后比较栈顶 $a_3 = 4 \leq a_6 = 4$，故将 $3$ 弹出；再比较 $a_1 = 5 > a_6 = 4$，停止弹栈，并将新加入的下标 $6$ 压入栈中。最后栈中的数列下标变为 $1, 6$。
考虑时间复杂度：显然每个元素只会在被插入时压入栈一次，也只会被栈弹出至多一次，所以总的时间复杂度是 $O(n)$，均摊单次插入 $O(1)$。
因为栈里元素的下标对应的数列元素是单调的，所以这一数据结构被称为**单调栈**。
如果把本题的「添加元素」操作改为：本身给定一个长度为 $n$ 的数列 $a$，每次查找 $[1, i]$ 这个前缀的所有后缀最大值，你可以发现这两种叙述完全等价。这就是说，本质上单调栈维护的是**数列所有前缀的后缀最值**。你可以通过调整比较条件里的大于号、小于号、大于等于号、小于等于号来用这一数据结构维护所有前缀的后缀最大、最小、非严格最大、非严格最小值。
以上就是对单调栈的介绍。
---
在本题中，每次操作结束后要求输出所有后缀最大值下标的按位异或和。只需要用一个全局变量 $b$ 维护当前栈内元素的按位异或和，在 pop 和 push 时均令 $b$ 异或上被操作的数即可。
记得开 unsigned long long。
### Code
```cpp
#include <vector>
#include <array>
#include <iostream>
int n, ans;
std::vector<int> stk;
std::array<unsigned long long, 1000005> a;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::cin >> a.at(i);
while (stk.size() && (a.at(i) >= a.at(stk.back()))) {
ans ^= stk.back();
stk.pop_back();
}
stk.push_back(i);
ans ^= i;
std::cout << ans << '\n';
}
}
```
### Note
练习题：
P6510
P6503
CF5E