题解 P6011 【[SCOI2006]动态最值】

EternalEpic · 2020-05-21 16:55:20 · 题解

这道题，有删除操作，于是我想到了两种做法。

法1：序列平衡树，对于做过文艺平衡树的人很简单，只要维护一个类似线段树标记，就可以了。这里不着重描述。

法2：有一个很简单暴力的方法——用线段树。一个棘手的问题就是线段树是静态的，怎么支持删除？我们根本不要在结构中删去节点，我们只要将该节点的min设置成INT_MAX，max设置成INT_MIN，就可以消除掉该节点的贡献，从而在形式上“删去”了次节点。

那么，有一个深邃的问题，删的过程中数组下标在变化，所以要用树状数组维护pos之前删去了几个数，从而得到真正的idx。

但是，题目是给你真正的下标idx，你要倒着求pos，这就需要二分了，注意，二分时可能有多个满足值，要取最大的那一个，因为前面的都是已删去的数。

Last but not the least，code is here:

const int Maxn = 1e6 + 5; int n, m, a[Maxn];
struct SegmentTree {
    int tmin[Maxn << 2 | 1], tmax[Maxn << 2 | 1];
    SegmentTree(void) {}
    inline void pushup(int pos) {
        tmin[pos] = min(tmin[pos << 1], tmin[pos << 1 | 1]);
        tmax[pos] = max(tmax[pos << 1], tmax[pos << 1 | 1]);
    }

    inline void build(int pos, int l, int r) {
        if (l == r) { tmin[pos] = tmax[pos] = a[l]; return; }
        int mid = l + r >> 1;
        build(pos << 1, l, mid),
        build(pos << 1 | 1, mid + 1, r);
        pushup(pos);
    }

    inline void remove(int pos, int l, int r, int idx) {
        if (l == r) { tmin[pos] = INT_MAX, tmax[pos] = INT_MIN; return; }
        int mid = l + r >> 1;
        if (idx <= mid) remove(pos << 1, l, mid, idx);
        else remove(pos << 1 | 1, mid + 1, r, idx);
        pushup(pos);
    }

    inline int querymin(int pos, int l, int r, int L, int R) {
        if (L <= l && R >= r) return tmin[pos];
        int mid = l + r >> 1, ret = INT_MAX;
        if (L <= mid) ret = querymin(pos << 1, l, mid, L, R);
        if (R > mid) chkmin(ret, querymin(pos << 1 | 1, mid + 1, r, L, R));
        return ret;
    }

    inline int querymax(int pos, int l, int r, int L, int R) {
        if (L <= l && R >= r) return tmax[pos];
        int mid = l + r >> 1, ret = INT_MIN;
        if (L <= mid) ret = querymax(pos << 1, l, mid, L, R);
        if (R > mid) chkmax(ret, querymax(pos << 1 | 1, mid + 1, r, L, R));
        return ret;
    }
} sgt;

struct BinaryIndexTree {
    int c[Maxn];
    BinaryIndexTree(void) { Ms(c, 0); return; }
    inline void update(int pos) { for (; pos <= n; pos += lowbit(pos)) ++c[pos]; }
    inline int query(int pos) { int ret = 0; for (; pos; pos -= lowbit(pos)) ret += c[pos]; return ret; }
} bit;

inline int Index(int pos) {
    int l = 1, r = n, ans;
    while (l <= r) {
        int mid = l + r >> 1;
        if (mid - bit.query(mid) == pos) ans = mid;
        if (mid - bit.query(mid) > pos) r = mid - 1;
        else l = mid + 1;
    } return ans;
}

signed main(void) {
//  file("");
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i]);
    sgt.build(1, 1, n);
    for (int opt, l, r; m; m--) {
        read(opt), read(l);
        if (opt == 1) { l = Index(l);
            sgt.remove(1, 1, n, l);
            bit.update(l + 1);
        } else {
            read(r); l = Index(l), r = Index(r);
            writeln(sgt.querymin(1, 1, n, l, r), ' ');
            writeln(sgt.querymax(1, 1, n, l, r));
        }
    }
//  fwrite(pf, 1, o1 - pf, stdout);
    return 0;
}