1>【模板】单调栈

题目描述

给出项数为 \(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

提示

对于 \(100\%\) 的数据，\(1 \le n\leq 3\times 10^6\)，\(1\leq a_i\leq 10^9\)。

思路

设当前数为a ₂
a ₂ 之后第一个比a ₂ 大的数 $<=> $反转这串数，a ₂ 之前且离a ₂ 最近的比a ₂ 大的数
栈顶元素刚好满足这一要求，如果该栈是单调递减的
由于要输出下标，所以就将下标存入栈中

代码

#include <iostream>
#include <stack>
#include <vector>

using namespace std;
const int N = 3e6 + 10;
stack<int> a;
int b[N];
vector<int> c;

int main()
{
	int n; cin >> n;
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = n; i > 0; i--)  //起到反转的效果
	{
		while(!a.empty() && b[a.top()] <= b[i]) a.pop();  //不符合单调递减的条件就会一直出栈
		c.push_back(a.empty() ? 0 : a.top());  //若栈为空，则没有元素比它大；若非空，则栈顶元素就是第一个大于它的
		a.push(i);
	}
	for(int i = c.size() - 1; i >= 0; i--) cout << c[i] << ' ';
}

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

题目描述

给定一个数列 \(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}\)。

思路

后缀最大值 单调递减栈的栈底元素

代码

#include <iostream>
#include <stack>

using namespace std;
typedef unsigned long long llu;
const int N = 1e6 + 10;
stack<llu> a;
llu b[N], count;

int main()
{
	llu n; scanf("%llu", &n);
	for(llu i = 1; i <= n; i++)
	{
		scanf("%llu", &b[i]);
		while(!a.empty() && b[a.top()] <= b[i]) count ^= a.top(), a.pop();
		count ^= i, a.push(i);
		printf("%llu\n", count);
	}
}