题解：P13520 [KOI 2025 #2] 存放箱子

· · 题解

最小链覆盖转成最长反链。

问题相当于选出一些盒子，两两无法嵌套。

这意味着我们只需要关注最大的 b_i。设 \max b_i = v，那么只有 a_i > v 的 i 才可以被选上。

因此答案为 \max\limits_{v} \#[a_i > v \land b_i \le v]。

离散化后实时维护所有 v 的答案，相当于对 [b_i, a_i - 1] 区间加一，查询全局 \max。线段树即可，时间复杂度 \mathcal O(n\log n)。

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
template <class T>
using Ve = vector<T>;
#define ALL(v) (v).begin(), (v).end()
#define pii pair<ll, ll>
#define rep(i, a, b) for(ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define pb push_back
bool Mbe;
ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
void write(ll x) {
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const ll N = 4e5 + 9;
ll n, a[N], b[N], tmp[N], tot, tr[N << 2], tag[N << 2];
void Pushtag(ll x, ll k) {
    tr[x] += k, tag[x] += k;
}
void Pushdown(ll x) {
    if(!tag[x]) return ;
    Pushtag(x << 1, tag[x]);
    Pushtag(x << 1 | 1, tag[x]);
    tag[x] = 0;
}
void Pushup(ll x) {
    tr[x] = max(tr[x << 1], tr[x << 1 | 1]);
}
void Upd(ll x, ll l, ll r, ll ql, ll qr, ll k) {
    if(ql <= l && r <= qr) return Pushtag(x, k), void();
    ll mid = (l + r) >> 1;
    Pushdown(x);
    if(ql <= mid) Upd(x << 1, l, mid, ql, qr, k);
    if(qr > mid) Upd(x << 1 | 1, mid + 1, r, ql, qr, k);
    Pushup(x);
}
bool Med;
int main() {
    cerr << fabs(&Med - &Mbe) / 1048576.0 << "MB\n";
    n = read();
    rep(i, 1, n) a[i] = read(), b[i] = read();
    rep(i, 1, n) tmp[++tot] = a[i], tmp[++tot] = b[i];
    sort(tmp + 1, tmp + tot + 1); tot = unique(tmp + 1, tmp + tot + 1) - tmp - 1;
    rep(i, 1, n) {
        a[i] = lower_bound(tmp + 1, tmp + tot + 1, a[i]) - tmp;
        b[i] = lower_bound(tmp + 1, tmp + tot + 1, b[i]) - tmp;
        Upd(1, 1, tot, b[i], a[i] - 1, 1);
        write(tr[1]), putchar('\n');
    }
    cerr << "\n" << clock() * 1.0 / CLOCKS_PER_SEC * 1000 << "ms\n";
    return 0;
}