单调栈：
可以线性预处理：序列前/后缀最大/小值的位置，或者是第 \(i\) 个数下一个更小/大数的位置。
B3666 求数列所有后缀最大值的位置 https://www.luogu.com.cn/problem/B3666
题意：
给一个初始为空的数列 \(a\) ，共 \(n\) 次操作，第 \(i(1 \leq i \leq n)\) 次操作会在 \(a\) 的末尾加入一个正整数 \(x\) 。
每次操作结束后，找到当前 \(a\) 的所有后缀最大值的下标（下标从 \(1\) 开始）。一个下标 \(i\) 是当前 \(a\) 的后缀最大值下标 \(iff\) ：\(\forall j, i < j \leq |a|\) ，都有 \(a_i > a_j\) 。
每次操作结束输出当前数列所有后缀最大值的下标的按位异或和。
题解：
对于某个数列，显然任意元素 \(a_x\) 满足 \(\forall i > x, a_i < x\) ，则是后缀最大值。设所有 \(x\) 得到的序列为 \(\mathbb{P}\) 。
于是 \(\forall x < y \in \mathbb{P}\) ，有 \(a_x > a_y\) 。至少 \(\forall x \in \mathbb{P}\) 属于解集。
否则，至少存在 \(a_y \geq a_x \ s.t.\ y > x\) 。于是 \(\forall x \not \in \mathbb{P}\) 不属于解集。
于是 \(\forall x \in \mathbb{P}\) 为解集。
于是对于滑动的窗口，可以维护严格递减的单调栈，即动态维护序列 \(\mathbb{P}\) 。
现在答案貌似成为了：对每个滑动窗口的 \(x \in \mathbb{P}\) ，计算一遍按位异或和。但这显然是时间不允许的。
注意到按位异或的重要性质： \(x \oplus x = 0\) 。
考虑正难则反，区间的所有下标去除非法下标则是答案。要去除的即当前窗口下，单调栈中会被弹出的下标。维护历史弹出值的按位异或和即可。
窗口是维护前缀 \(pre(1, r)\) 的滑动，所以设 \(ans = \bigoplus_{i = 1}^{r} a_i\) 。然后 \(ans \oplus x \ s.t.\ x \in \mathbb{P}, a_x \leq a_r\) 。
前缀异或可以在线处理 \(ans \oplus r\) 。也存在
\[ans = \begin{cases} r, r \equiv r (\bmod 4) \\ 1, r \equiv 1 (\bmod 4) \\ r + 1, r \equiv 2 (\bmod 4) \\ 0, r \equiv 3 (\bmod 4) \\ \end{cases} \]考虑证明，设 \(a = ???00, b = ???01, c = ???10, d = ???11\) 。
\[\begin{cases} 0 \oplus a = a \\ 0 \oplus a \oplus b = 1 \\ 0 \oplus a \oplus b \oplus c = c + 1 \\ 0 \oplus a \oplus b \oplus c \oplus = 0 \\ \end{cases} \]int n; std::cin >> n;
std::vector<u64> a(n + 1);
std::stack<u64> stk;
auto calc = [&] (int X) -> u64 {
if (X % 4 == 0) return X;
if (X % 4 == 1) return 1;
if (X % 4 == 2) return X + 1;
if (X % 4 == 3) return 0;
return -1;
};
u64 remove = 0;
for (int i = 1; i <= n; i++) {
std::cin >> a[i];
u64 res = 0;
while (!stk.empty() && a[i] >= a[stk.top()]) {
remove ^= stk.top();
stk.pop();
}
stk.push(i);
std::cout << (remove ^ calc(i)) << "\n";
}
P2866 [USACO06NOV] Bad Hair Day S https://www.luogu.com.cn/problem/P2866
题意：