P13780 「o.OI R2」愿天堂没有分块 题解

namespace lowspeed_song {

inline void init() {
}

int a[N], res[N], root[N];
vector<int> pos[N];
vector<pair<int, int>> seg[N], cand[N];
struct Query { int l, r, id; } Q[N];

int idx;
struct Node {
    int l, r, mi;
} tree[N * 24];

inline int build(int l, int r) {
    int rt = ++idx;
    tree[rt].mi = tree[rt].l = tree[rt].r = 0;
    if (l == r) return rt;
    int mid = l + r >> 1;
    tree[rt].l = build(l, mid);
    tree[rt].r = build(mid + 1, r);
    return rt;
}

inline int mdf(int p, int l, int r, int pos, int val) {
    int rt = ++idx;
    tree[rt] = tree[p];
    if (l == r) return tree[rt].mi = val, rt;
    int mid = l + r >> 1;
    if (pos <= mid) tree[rt].l = mdf(tree[p].l, l, mid, pos, val);
    else tree[rt].r = mdf(tree[p].r, mid + 1, r, pos, val);
    tree[rt].mi = min(tree[tree[rt].l].mi, tree[tree[rt].r].mi);
    return rt;
}

inline int qry(int rt, int l, int r, int lim) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (tree[tree[rt].l].mi < lim) return qry(tree[rt].l, l, mid, lim);
    return qry(tree[rt].r, mid + 1, r, lim);
}

inline void norm(vector<pair<int, int>> &v) {
    sort(v.begin(), v.end(), [&](const pair<int, int> &l, const pair<int, int> &r) {
        if (l.first != r.first) return l.first < r.first;
        return l.second > r.second;
    });
    v.erase(unique(v.begin(), v.end()), v.end());
    vector<pair<int, int>> tmp;
    int m = (int)v.size();
    vector<int> suf(m + 1, 1e9);
    for (int j = m - 1; j >= 0; --j)
        suf[j] = min(suf[j + 1], v[j].second);
    for (int j = 0; j < m; ++j)
        if (suf[j + 1] > v[j].second)
            tmp.emplace_back(v[j]);
    v.swap(tmp);
}

namespace SegTree {
    struct Node {
        int l, r, mx;
        inline void init(int p) { l = r = p, mx = 1e9; }
        inline void push(int v) { mx = min(mx, v); }
    } tree[N << 2];
    inline Node operator+(const Node &l, const Node &r) {
        return {l.l, r.r, max(l.mx, r.mx)};
    }
    inline void build(int l, int r, int rt) {
        if (l == r) return tree[rt].init(l);
        int mid = l + r >> 1;
        build(l, mid, rt << 1), build(mid + 1, r, rt << 1 | 1);
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    inline void mdf(int rt, int pos, int v) {
        int &l = tree[rt].l, &r = tree[rt].r;
        if (l == r) return tree[rt].push(v);
        int mid = l + r >> 1;
        mdf((pos <= mid) ? (rt << 1) : (rt << 1 | 1), pos, v);
        tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];
    }
    inline int find(int rt, int ll, int rr, int v) {
        int &l = tree[rt].l, &r = tree[rt].r;
        if (l == r) return l;
        if (tree[rt << 1].mx > v) return find(rt << 1, ll, rr, v);
        return find(rt << 1 | 1, ll, rr, v);
    }
}

inline void sol() {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i], --a[i], pos[a[i]].emplace_back(i);
    root[0] = build(0, n + 1);
    for (int i = 1; i <= n; ++i) {
        if (a[i] > n + 1) root[i] = root[i - 1];
        else root[i] = mdf(root[i - 1], 0, n + 1, a[i], i);
    }
    for (int i = 1; i <= n; ++i)
        if (a[i]) cand[0].emplace_back(i, i);
        else cand[1].emplace_back(i, i);
    for (int i = 0; i <= n; ++i) {
        norm(cand[i]);
        seg[i].swap(cand[i]);
        if (i == n) continue;
        for (auto &[l, r] : seg[i]) {
            int L = 0, R = (int)pos[i].size() - 1, best = -1;
            while (L <= R) {
                int mid = L + R >> 1;
                if (pos[i][mid] < l) best = mid, L = mid + 1;
                else R = mid - 1;
            }
            if (~best) {
                int xl = pos[i][best], xr = r;
                int mex = qry(root[xr], 0, n + 1, xl);
                if (mex <= n) cand[mex].emplace_back(xl, xr);
            }
            L = 0, R = (int)pos[i].size() - 1, best = -1;
            while (L <= R) {
                int mid = L + R >> 1;
                if (pos[i][mid] > r) best = mid, R = mid - 1;
                else L = mid + 1;
            }
            if (~best) {
                int xl = l, xr = pos[i][best];
                int mex = qry(root[xr], 0, n + 1, xl);
                if (mex <= n) cand[mex].emplace_back(xl, xr);
            }
        }
    }
    for (int i = 1; i <= q; ++i) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
    sort(Q + 1, Q + q + 1, [&](auto &l, auto &r) { return l.l > r.l; });
    vector<tuple<int, int, int>> sweep;
    for (int i = 0; i <= n; ++i)
        for (auto &[l, r] : seg[i]) sweep.emplace_back(l, r, i);
    sort(sweep.begin(), sweep.end(), [&](auto &l, auto &r) { return get<0>(l) > get<0>(r); });
    SegTree::build(0, n + 1, 1);
    int p = 0;
    for (int i = 1; i <= q; ++i) {
        while (p < sweep.size() && get<0>(sweep[p]) >= Q[i].l)
            SegTree::mdf(1, get<2>(sweep[p]), get<1>(sweep[p])), ++p;
        res[Q[i].id] = SegTree::find(1, 0, n + 1, Q[i].r) + 1;
    }
    for (int i = 1; i <= q; ++i) cout << res[i] << '\n';
}

} // namespace lowspeed_song