自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:14:16，当前版本为作者最后更新于2022-11-03 15:15:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

Preface

我私心里希望这道题成为单调栈的第一模板题，因为它揭示了单调栈的本质，即维护所有前缀的后缀最值。

但是这题自 10 月 1 日被我造出来起就没人写题解，我只能自己写一份（

Description

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

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

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

$1 \leq n \leq 10^6$，$1 \leq x_i \lt 2^{64}$。

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$ 入栈即可。

写作代码就是

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

#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