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

心灵震荡 · 2025-12-02 20:07:55 · 题解

简要题意：给定 n 个点 (r_i, h_i)（1 \le r_i, h_i \le 10^9），q 次询问，问只考虑 r_i \ge R, h_i \le H 的点，把这些点划分成若干严格上升子序列，能划分出的最小数量。

这里的严格上升指 r_j < r_i, h_j < h_i。

由 Dilworth 定理，这个东西等价于最长非严格下降子序列长度。

由于有左边界无右边界，我们考虑将 r_i 从大到小排序后倒着做，求一个最长非严格上升子序列长度。定义 f_i 表示以 (r_i, h_i) 结尾的非严格下降子序列长度的最大值，树状数组优化转移即可。

每次询问实际上是在查一个矩形范围内最大的 f_i，不强于二维数点，可以倒着扫描线离线处理掉。

#include <bits/stdc++.h>
using namespace std;

const int N = 6e5 + 5;

int n, q, f[N], b[N], c[N], m, ans[N];
vector<pair<int, int> > g[N];

struct node
{
    int r, h;

    bool operator < (const node &nd) const
    {
        if(r == nd.r) return h > nd.h;
        return r < nd.r;
    }
} a[N];

struct Qur
{
    int r, h, id;

    bool operator < (const Qur &nd) const
    {
        return r < nd.r;
    }
} qs[N];

inline int lowbit(int x)
{
    return x & (-x);
}

void update(int x, int k)
{
    while(x <= m) c[x] = max(c[x], k), x += lowbit(x);
}

int query(int x)
{
    int res = 0;
    while(x) res = max(res, c[x]), x -= lowbit(x);
    return res;
}

int main()
{
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> a[i].r >> a[i].h, b[i] = a[i].h, b[i + n] = a[i].h - 1;
    for(int i = 1; i <= q; i++)
        cin >> qs[i].r >> qs[i].h, qs[i].id = i, b[i + n * 2] = qs[i].h;
    sort(b + 1, b + n * 2 + q + 1);
    m = unique(b + 1, b + n * 2 + q + 1) - b - 1;
    for(int i = 1; i <= n; i++)
        a[i].h = lower_bound(b + 1, b + m + 1, a[i].h) - b;
    for(int i = 1; i <= q; i++)
        qs[i].h = lower_bound(b + 1, b + m + 1, qs[i].h) - b;
    sort(a + 1, a + n + 1);
    for(int i = n; i >= 1; i--)
    {
        f[i] = query(a[i].h) + 1;
        update(a[i].h, f[i]);
    }
    for(int i = 0; i <= m; i++) c[i] = 0;
    sort(qs + 1, qs + q + 1);
    for(int i = q, j = n; i >= 1; i--)
    {
        while(j >= 1 && a[j].r >= qs[i].r) update(a[j].h, f[j]), j--;
        ans[qs[i].id] = query(qs[i].h);
    }
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}