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

· · 题解

我们要把 x 号箱子放入 y 号箱子的话，就需满足 s_x \leq c_y。这启发我们尝试将 s 中的每个元素 c 中的每个元素配对，并尝试配出最多的对数。

可以把两个数组的配对抽象成一个括号序列的括号配对。将 s 中的元素看成左括号，c 中的元素看成右括号。将两个数组中的元素合并之后按数值为第一标准，左括号放前面为第二标准。这样就可以在已经得出的括号序列中求括号的最大匹配数。再将总数减去匹配数量就是答案。

可以拿样例举例。考虑一下如下输入数据：

6 4
5 1
9 8
2 1

变成括号序列之后变成

[1:]))[2:]([4:])[5:]([6:]([8:])[9:](
))()(()(

总共有 2 个括号，即答案为 4 - 2 = 2。

考虑将 s 和 c 离散化。每次王括号序列中插入括号。可以用值域线段树来维护，维护括号匹配数和剩余的左右括号数量。注意可存在多个括号在同一个值上，所以对于一个长度为 1 的区间括号匹配数是左括号和右括号的最小值。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 7;
int n;
pair<int, int> p[N];
map<int, int> mp;
struct node {
    int l, r, mid, sum, lk, rk;
}tr[N << 2];
void build(int p, int l, int r) {
    tr[p].l = l, tr[p].r = r;
    tr[p].mid = l + r >> 1;
    tr[p].sum = 0; tr[p].lk = 0, tr[p].rk = 0;
    if(l == r) return ;
    build(p << 1, l, tr[p].mid);
    build(p << 1 | 1, tr[p].mid + 1, r);
}
void push_up(node &rt, node lft, node rgt) {
    rt.sum = lft.sum + rgt.sum + min(lft.lk, rgt.rk);
    rt.lk = lft.lk + rgt.lk - min(lft.lk, rgt.rk);
    rt.rk = lft.rk + rgt.rk - min(lft.lk, rgt.rk);
}
void upd(int p, int x, int tp) {
    if(tr[p].l == tr[p].r) {
        if(tp == 1) tr[p].lk ++;
        else tr[p].rk ++;
        if(tr[p].lk && tr[p].rk) {
            tr[p].lk --, tr[p].rk --;
            tr[p].sum ++;
        }
        return ;
    }
    if(x <= tr[p].mid) upd(p << 1, x, tp);
    else upd(p << 1 | 1, x, tp);
    push_up(tr[p], tr[p << 1], tr[p << 1 | 1]);
}
int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> p[i].first >> p[i].second;
        mp[p[i].first] = 1, mp[p[i].second] = 1;
    }
    int cnt = 0;
    for(auto &tmp : mp) tmp.second = ++ cnt;
    build(1, 1, cnt);
    for(int i = 1; i <= n; i ++) {
        p[i].first = mp[p[i].first];
        p[i].second = mp[p[i].second];
        upd(1, p[i].first, 1);
        upd(1, p[i].second, 2);
        cout << i - tr[1].sum << '\n';
    }
    return 0;
}