Problem
给定两个长度均为 \(n\) 的排列 \(p,q\) 。对一个初始为空的集合 \(s\) 进行如下操作：对于每个 \(i\) ，将 \(p_i\) 放入集合；如果 \(i\) 被标记了，则此时再将集合中最大的数删除。求 \(n\) 次操作后集合中最大的数。
排列 \(q\) 的意义是，对于每个 \(i\) ，询问将 \(q_1,q_2\cdots q_{i-1}\) 都标记之后的上述操作的结果。
\(1\leq n\leq 3\times 10^5，1 \leq p_i,q_i \leq n\)。
Input
第一行输入一个整数 \(n\)。
第二行输入 \(n\) 个数 \(p_1,p_2\cdots p_n\)。
第三行输入 \(n\) 个数 \(q_1,q_2\cdots q_n\)。
Output
输出一行 \(n\) 个整数表示答案。
Sample
Input 1
3
3 2 1
1 2 3
Output 1
3 2 1
Input 2
6
2 3 6 1 5 4
5 2 1 4 6 3
Output 2
6 5 5 5 4 1
Solution
容易看出答案是单调不增的。
考虑当前答案为 \(res\)，我们发现答案变小当且仅当不存在任意一个下标满足它右边不小于 \(res\) 的数比它右边的炸弹数多。
然后就很好做了，把添加炸弹当作 \(-1\) 的贡献，把删数更新答案当作 \(+1\) 的贡献，线段树维护下即可。
代码：
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 3e5 + 3;
struct T {
int s, laz;
} t[kmax << 2];
int n, a[kmax], b[kmax];
int p[kmax];
int res;
void Pushup(int x) {
t[x].s = max(t[x << 1].s, t[x << 1 | 1].s);
}
void Pushdown(int x) {
if (!t[x].laz) return;
t[x << 1].laz += t[x].laz, t[x << 1 | 1].laz += t[x].laz;
t[x << 1].s += t[x].laz, t[x << 1 | 1].s += t[x].laz;
t[x].laz = 0;
}
void Modify(int x, int l, int r, int _l, int _r, int v) { // 线段树区间修改
if (_l <= l && r <= _r) {
t[x].s += v;
t[x].laz += v;
return;
}
Pushdown(x);
int mid = (l + r) >> 1;
if (_l <= mid) Modify(x << 1, l, mid, _l, _r, v);
if (_r > mid) Modify(x << 1 | 1, mid + 1, r, _l, _r, v);
Pushup(x);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
res = n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[a[i]] = i; // 记录下每个值所在的位置
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
cout << n << ' '; // 最开始答案显然为n
Modify(1, 1, n, 1, p[n], 1); // 修改
for (int i = 1; i < n; i++) {
for (Modify(1, 1, n, 1, b[i], -1); t[1].s <= 0; Modify(1, 1, n, 1, p[--res], 1)) { // 添加炸弹，如果不存在符合要求的，更新答案
}
cout << res << ' ';
}
return 0;
}