「2025ECFinal」H. Staircase Museum题解

[题目链接](https://qoj.ac/contest/1894/problem/9982)

看题解看了半天还是一脸懵逼

后来发现感性理解一下很容易想通！

两个点如果无法相互看见，就一定有一个类似台阶的东西（如图中的红点和蓝边）把他们挡住了

![](https://konny.eu.org/usr/uploads/2026/01/979912399.jpeg)

那么，想象按照顺序把每个点移动到某个红点（遮挡住视线的红点）旁边后，原先可以遮挡视线的点依旧可以

想让最多的红点附近的点互相被遮挡，一定需要满足严格二维偏序！

最大二维偏序也一定可以构造出来，也就是最大数量！

```cpp
#include <bits/stdc++.h>

using namespace std;

const int N=1e6+10;
int T, n, l[N], r[N], a[N];

struct fenwick {
    int n, c[N];

void init(int _n) {
        n=_n;
        fill(c+1, c+n+1, 0);
    }

void upd(int x, int y) {
        while (x<=n) {
            c[x]=max(c[x], y);
            x+=x&-x;
        }
    }

int ask(int x) {
        int r=0;
        while (x) {
            r=max(r, c[x]);
            x-=x&-x;
        }
        return r;
    }
} C;

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        for (int i=1; i<=n; i++) scanf("%d%d", &l[i], &r[i]);
        vector<pair<int, int> > v;
        for (int i=1; i<=n; i++) {
            if (i>1 && l[i]!=l[i-1]) v.emplace_back(i-1, l[i]-1);
            if (i<n && r[i]!=r[i+1]) v.emplace_back(i, r[i]);
        }
        sort(v.begin(), v.end(), [](pair<int, int> a, pair<int, int> b){return a.first<b.first || a.first==b.first && a.second>b.second;});
        int len=0;
        for (auto [x, y]:v) a[++len]=y;
        sort(a+1, a+len+1);
        len=unique(a+1, a+len+1)-(a+1);
        C.init(len);
        for (auto [x, y]:v) {
            y=lower_bound(a+1, a+len+1, y)-a;
            C.upd(y, C.ask(y-1)+1);
        }
        printf("%d\n", C.ask(len)+1);
    }
    return 0;
}
```

最后修改：2026 年 01 月 04 日