题解：AT_arc159_d [ARC159D] LIS 2

· · 题解

提供一个避开分类讨论的小结论没什么用。

令 f_i 表示以 i 结尾的 LIS 长度，则添加线段时对于每个 i \in [l,r],f_i=\max\limits_{j<i}f_j+1。

实际上可以强化成 f_i=\max\limits_{j<l}f_j+i-l+1。

证明显然：令 g_i=\max\limits_{j=1}^if_j，则 \forall i>0,g_i \le g_{i-1}+1。则可得 \forall i \in [l,r], g_i \le g_{l-1}+i-l+1，i 对 f_x(x>i,x \in [l,r]) 的贡献为：

f_i+1 \le g_i+1 \le g_{l-1}+i-l+2\le g_{l-1}+x-l+1

得证。

问题变成区间加一次函数和查询区间内单点最值。线段树维护即可。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
const int LGN = 50;

int n;
struct Segment {
    int ls, rs;
    int max, maxb;
    Segment() { maxb = -1e9; }
} a[MAXN * LGN];
int idx, root;

#define Max(x, y) x = max(x, y)
#define mid ((L + R) >> 1)
void maxit(int p, int b, int L, int R) {
    if (!p) return;
    a[p].maxb = max(a[p].maxb, b);
    a[p].max = max({a[p].maxb + R, a[a[p].ls].max, a[a[p].rs].max});
    return;
}
void pushdown(int p, int L, int R) {
    if (!a[p].ls) a[p].ls = ++idx;
    if (!a[p].rs) a[p].rs = ++idx;
    maxit(a[p].ls, a[p].maxb, L, mid);
    maxit(a[p].rs, a[p].maxb, mid + 1, R);
    return;
}
void pushup(int p, int L, int R) {
    a[p].max = max({a[p].maxb + R, a[a[p].ls].max, a[a[p].rs].max});
    return;
}
void add(int &p, int l, int r, int b, int L = 1, int R = 1e9) {
    if (!p) p = ++idx;
    if (l <= L && R <= r) { maxit(p, b, L, R); return; }
    pushdown(p, L, R);
    if (l <= mid) add(a[p].ls, l, r, b, L, mid);
    if (mid < r) add(a[p].rs, l, r, b, mid + 1, R);
    pushup(p, L, R);
    return;
}
int query(int p, int l, int r, int L = 1, int R = 1e9) {
    if (!p || l > r) return 0;
    if (l <= L && R <= r) return a[p].max;
    pushdown(p, L, R);
    int res = 0;
    if (l <= mid) Max(res, query(a[p].ls, l, r, L, mid));
    if (mid < r) Max(res, query(a[p].rs, l, r, mid + 1, R));
    return res;
}

signed main() {
    ios:: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    while (n--) {
        int l, r; cin >> l >> r;
        int t = query(root, 1, l - 1);
        add(root, l, r, t + 1 - l);
    }
    cout << query(root, 1, 1e9) << endl;
    return 0;
}