BZOJ 1852 [MexicoOI06] 最长不下降序列

https://darkbzoj.cc/problem/1852

首先解决初始排序的问题：

先把 \(i,j\) 对应的两组数 \((a_i,b_i),(a_j,b_j)\) 分为“必要”，“非必要”两类。

1. “必要”，指 \(i\) 必须在 \(j\) 前面（\(j\) 在 \(i\) 前面同理），满足 \(i\to j\) 是可以配对的，\(j\to i\) 不行，便可以得到 \(a_i>b_j,a_j\le b_i\)，换方向 \(a_i>b_j,b_i\ge a_j\)，两式相加得 \(a_i+b_i>a_j+b_j\)。

2. “非必要”，则又分为两种：\(i\to j,j\to i\) 都可配对，\(i\to j, j\to i\) 都不可配对。
   显而易见，交换这两组不影响答案。

所以先离散化一下（设还剩 \(m\) 个数）按照 \(a_i+b_i\) 从大到小绝对是最优解。

分析柿子，发现 \(i\) 这一组能接在后面取决于 \(\min\{a\}>b_i\)，于是状态就出来了：

设 \(dp_{i,j}\) 是到第 \(i\) 组选了这一组，\(\min\{a\}=j\) 最多的组数。

转移方程又要分类讨论：

1. \(a_i\le b_i\)，需满足 \(b_i< \min\{a\}\)，且因 \(a_i\le b_i\)，\(\min\{a\}\) 会变为 \(a_i\)，转移方程即为 \(dp_{i,a_i}=\max\{dp_{i-1,j}\}+1(b_i< j\le m)\)。

2. \(a_i>b_i\)，则 \(\min\{a\}=(b_i,a_i]\)，这部分又有两种：

   1. \(\min\{a\}=a_i\)，与第 1 种差不多，\(dp_{i,a_i}=\max\{dp_{i-1,j}\}+1(a_i\le j\le m)\)。
   2. \(b_i<\min\{a\}< a_i\)，则这一部分只会多一组，\(dp_{i,j}=dp_{i-1,j}+1(b_i< j< a_i)\)。

发现需要的操作即为区间最大值和区间加（区间赋值可以看作加上要变为的数减去现在的数的差），用线段树维护即可。

进一步也能发现第一维的 \(i\) 其实是可以滚掉的，就成了裸的线段树模板了。

# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
pair <int, int> a [N];
struct seg_node {
    int l, r, Max, tag;
} t [N << 3];
void build (int k, int l, int r) {
    t [k] .l = l;
    t [k] .r = r;
    t [k]. Max = 0;
    t [k] .tag = 0;
    if (l == r) {
        return ;
    }
    int mid = (l + r) >> 1;
    build (k << 1, l, mid);
    build (k << 1 | 1, mid + 1, r);
    return ;
}
void pushup (int k) {
    t [k] .Max = max (t [k << 1] .Max, t [k << 1 | 1] .Max);
    return ;
}
void pushdown (int k) {
    t [k << 1] .Max += t [k] .tag;
    t [k << 1] .tag += t [k] .tag;
    t [k << 1 | 1] .Max += t [k] .tag;
    t [k << 1 | 1] .tag += t [k] .tag;
    t [k] .tag = 0;
    return ;
}
void update (int k, int l, int r, int x) {
    if (r < t [k] .l || t [k] .r < l) {
        return ;
    }
    if (l <= t [k] .l && t [k] .r <= r) {
        t [k] .Max += x;
        t [k] .tag += x;
        return ;
    }
    pushdown (k);
    update (k << 1, l, r, x);
    update (k << 1 | 1, l, r, x);
    pushup (k);
    return ;
}
int query (int k, int l, int r) {
    if (r < t [k] .l || t [k] .r < l) {
        return 0;
    }
    if (l <= t [k] .l && t [k] .r <= r) {
        return t [k] .Max;
    }
    pushdown (k);
    return max (query (k << 1, l, r), query (k << 1 | 1, l, r));
}
int main () {
    int n;
    scanf ("%d", & n);
    vector <int> v;
    v .push_back (INT_MIN);
    for (int i = 1; i <= n; ++ i) {
        scanf ("%d %d", & a [i] .first, & a [i] .second);
        v .push_back (a [i] .first);
        v .push_back (a [i] .second);
    }
    sort (v .begin (), v .end ());
    v .erase (unique (v .begin (), v .end ()), v .end ());
    int m = v .size ();
    build (1, 1, m);
    for (int i = 1; i <= n; ++ i) {
        a [i] .first = lower_bound (v .begin (), v .end (), a [i] .first) - v .begin ();
        a [i] .second = lower_bound (v .begin (), v .end (), a [i] .second) - v .begin ();
    }
    sort (a + 1, a + n + 1, [] (pair <int, int> a, pair <int, int> b) {
        return a .first + a .second > b .first + b .second;
    });
    int ans = 0;
    for (int i = 1; i <= n; ++ i) {
        if (a [i] .first <= a [i] .second) {
            int x = query (1, a [i] .second + 1, m) + 1;
            int y = query (1, a [i] .first, a [i] .first);
            update (1, a [i] .first, a [i] .first, x - y);
        }
        else {
            int x = query (1, a [i] .first, m) + 1;
            int y = query (1, a [i] .first, a [i] .first);
            update (1, a [i] .first, a [i] .first, x - y);
            update (1, a [i] .second + 1, a [i] .first - 1, 1);
        }
    }
    printf ("%d", query (1, 1, m));// 最后答案即为整个区间最大值
    return 0;
}