题解：P14394 [JOISC 2016] 俄罗斯套娃 / Matryoshka

WASETL · 2026-07-22 20:54:44 · 题解

把每一个套娃变成坐标系内的点 (R_i, H_i)。就可以把题目变成，每次给定平面内的一个区域，满足横坐标不小于 A_i，纵坐标不大于 B_i。要求每次可以从区域内选出一些横坐标单调递增，纵坐标也单调递增的点。求最少把区域内的点全部选完的次数。根据 Dilworth 定理，上面的问题就可以转化为选一些点，满足横坐标单调不递增，纵坐标单调不递增，求选的点数的最大值。

询问离线下来。离散化之后将询问按照 A 递减排序。将所有点按照 R 递减为第一标准，H 递增为第二标准排序。按照横坐标递减处理加点和询问。考虑动态规划。设 f_i 为选一连串点，以 i 为最靠左上的点的选的数量的最大值。转移方程其实就是求最长不下降子序列。

可以用前缀最大值树状数组维护。每次查询就是查询 \max_{1 \leq j \leq B_i} f_j。这个问题本质就是 LIS 和二维数点的融合，复杂度为 O((N + Q) \log (N + Q))。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
int n, q, m, ans[N];
pair<int, int> pt[N];
map<int, int> mp;
struct query {
    int x, y, pos;
}q1[N];
struct BIT {
    int c[N << 2] = {0};
    void add(int x, int k) {
        for(; x <= m; x += x & -x) c[x] = max(c[x], k);
    }
    int ask(int x) {
        int mx = 0;
        for(; x; x -= x & -x) mx = max(mx, c[x]);
        return mx;
    }
}tr;
signed main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) {
        cin >> pt[i].first >> pt[i].second;
        mp[pt[i].first] = 1, mp[pt[i].second] = 1;
    }
    sort(pt + 1, pt + 1 + n, [](pair<int, int> pa, pair<int, int> pb) {
        if(pa.first != pb.first) return pa.first > pb.first;
        return pa.second < pb.second;
    });
    for(int i = 1; i <= q; i ++) {
        cin >> q1[i].x >> q1[i].y;
        mp[q1[i].x] = 1, mp[q1[i].y] = 1;
        q1[i].pos = i;
    }
    sort(q1 + 1, q1 + 1 + q, [](query qa, query qb) {
        return qa.x > qb.x;
    });
    for(auto &tmp : mp) tmp.second = ++ m;
    int t = 1;
    for(int i = 1; i <= n; i ++) 
        pt[i].first = mp[pt[i].first], pt[i].second = mp[pt[i].second];
    for(int i = 1; i <= q; i ++) {
        q1[i].x = mp[q1[i].x], q1[i].y = mp[q1[i].y];
        while(t <= n && pt[t].first >= q1[i].x) 
            tr.add(pt[t].second, tr.ask(pt[t].second) + 1), t ++;
        ans[q1[i].pos] = tr.ask(q1[i].y);
    }
    for(int i = 1; i <= q; i ++) cout << ans[i] << '\n';
    return 0;
}