xht37 的洛谷博客

xht37's blog:https://www.xht37.com/

题解 CF1326E 【Bombs】

首先有答案是递减的。

对于当前答案 $x$,我们如何判断它时候能被保留下来呢?

可以发现, $x$ 能留下当且仅当存在一个位置满足它右边 $\ge x$ 的数大于它右边的炸弹数。

于是线段树维护全局 $\max$ 和区间修改即可,时间复杂度 $\mathcal O(n \log n)$。

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;
}

2020-03-22 04:14:10 in 题解