Codeforces

分析

设 $f_{i, j}$ 表示前 $i$ 个数、LIS 长度为 $j$ 时末尾元素的最小值。

考虑转移。假设当前区间为 $[l, r]$，那么

• 不加：$f_{i, j} \gets f_{i - 1, j}$。
• 对于 $f_{i - 1, j -1} < l$，有 $f_{i, j} \gets l$。
• 对于 $l \leq f_{i - 1, j - 1} < r$，有 $f_{i, j} \gets f_{i - 1, j -1} + 1$。

并且可以发现这个 DP 满足 $f_{i, j} \geq f_{i, j - 1} + 1$。

考虑使用数据结构维护整个 DP 数组。由上面的性质，$l \leq f_{i - 1, j - 1} < r$ 的转移肯定优于不加，因此我们可以把这些 DP 值加上 $1$ 后向右平移一位；而 $f_{i - 1, j - 1} < l$ 的转移只在最大的满足这个的 $j$ 处优于不加，所以只需要找到这个位置并修改即可。

可以使用平衡树维护，每次只需要找到找到 $\geq r - 1$ 的最小元素删去，把 $[l, r)$ 中的元素加 $1$，再插入一个 $l$ 即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

mt19937 R(chrono::system_clock::now().time_since_epoch().count());
int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 300000 + 10;

int n, l[N], r[N];

#define ls(o) ch[o][0]
#define rs(o) ch[o][1]
int rt, tot = 0;
int ch[N][2], sz[N], val[N], rnd[N], tag[N];

int newnode(int w) {
    ++tot, sz[tot] = 1, val[tot] = w, rnd[tot] = R();
    return tot;
}

void update(int o, int w) { tag[o] += w, val[o] += w; }
void pushup(int o) { sz[o] = sz[ls(o)] + sz[rs(o)] + 1; }
void pushdown(int o) {
    if (tag[o]) {
        if (ls(o)) update(ls(o), tag[o]);
        if (rs(o)) update(rs(o), tag[o]);
        tag[o] = 0;
    }
}

void split(int o, int k, int &x, int &y) {
    if (!o) { x = y = 0; return; }
    pushdown(o);
    if (val[o] <= k) x = o, split(rs(o), k, rs(o), y);
    else y = o, split(ls(o), k, x, ls(o));
    pushup(o);
}
int merge(int x, int y) {
    if (!x || !y) return x | y;
    pushdown(x), pushdown(y);
    if (rnd[x] < rnd[y]) { rs(x) = merge(rs(x), y); pushup(x); return x; }
    else { ls(y) = merge(x, ls(y)); pushup(y); return y; }
}

int kth(int o, int k) {
    while (1) {
        if (k <= sz[ls(o)]) o = ls(o);
        else if (k == sz[ls(o)] + 1) return o;
        else k -= sz[ls(o)] + 1, o = rs(o);
    }
}
void insert(int w) {
    int x, y; split(rt, w, x, y);
    rt = merge(merge(x, newnode(w)), y);
}
void erase(int w) {
    int x, y, z; split(rt, w - 1, x, y), split(y, w, y, z);
    y = merge(ls(y), rs(y)), rt = merge(merge(x, y), z);
}
int findnext(int w) {
    int x, y; split(rt, w, x, y);
    int z = kth(y, 1);
    rt = merge(x, y);
    return z;
}
void add(int l, int r, int w) {
    int x, y, z; split(rt, l - 1, x, y), split(y, r, y, z);
    update(y, w);
    rt = merge(merge(x, y), z);
}
#undef ls
#undef rs

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) l[i] = read(), r[i] = read();
    for (int i = 1; i <= n; ++i) {
        if (i == 1) { insert(l[i]); continue; }
        int nxt = findnext(r[i] - 1);
        if (nxt) erase(val[nxt]);
        add(l[i], r[i] - 1, 1);
        insert(l[i]);
    }
    printf("%d\n", sz[rt]);
    return 0;
}