题解 CF1326E 【Bombs】

首先有答案是递减的。 对于当前答案 $x$，我们如何判断它时候能被保留下来呢？ 可以发现，$x$ 能留下当且仅当存在一个位置满足它右边 $\ge x$ 的数大于它右边的炸弹数。 于是线段树维护全局 $\max$ 和区间修改即可，时间复杂度 $\mathcal O(n \log n)$。 ```cpp const int N = 3e5 + 7; int n, a[N], b[N], p[N], ans; struct T { int l, r, x, z; } t[N<<2]; void build(int p, int l, int r) { t[p].l = l, t[p].r = r; if (l == r) return; build(ls, l, md), build(rs, md + 1, r); t[p].x = max(t[ls].x, t[rs].x); } void spd(int p) { if (t[p].z) { t[ls].x += t[p].z; t[ls].z += t[p].z; t[rs].x += t[p].z; t[rs].z += t[p].z; t[p].z = 0; } } void add(int p, int l, int r, int k) { if (t[p].l >= l && t[p].r <= r) return t[p].x += k, t[p].z += k, void(); spd(p); if (l <= md) add(ls, l, r, k); if (r > md) add(rs, l, r, k); t[p].x = max(t[ls].x, t[rs].x); } int main() { rd(n); for (int i = 1; i <= n; i++) rd(a[i]), p[a[i]] = i; for (int i = 1; i <= n; i++) rd(b[i]); build(1, 1, n), ans = n, print(n, ' '); add(1, 1, p[n], 1); for (int i = 1; i < n; i++) { add(1, 1, b[i], -1); while (t[1].x <= 0) add(1, 1, p[--ans], 1); print(ans, ' '); } return 0; } ```