题目链接：LOJ 2056

佳媛姐姐过生日的时候，她的小伙伴从某宝上买了一个有趣的玩具送给他。

玩具上有一个长度为 $n​$ 的数列 $a_i​$，数列中某些项的值可能会变化，但同一个时刻最多只有一个值发生变化。现在佳媛姐姐已经研究出了所有 $m​$ 种变化的可能性，她想请教你，能否选出一个子序列，使得在任意一种变化中，这个子序列都是不降的。请你告诉她这个子序列的最长长度即可。

数据范围：$1\le n,m,a_i\le 10^5​$。

Solution

我们设第 $i$ 个数为 $a_i$，他能变成的最大值为 $r_i$，最小值为 $l_i$（最大值和最小值包括本身）。定义 $\text{DP}$ 方程 $f_i$ 表示以第 $i$ 个数结尾的满足条件的序列的最长长度。

考虑第 $j$ 个数能放在 $i$ 前面当且仅当 $r_j\le a_i$ 且 $a_j\le l_i$ 且 $j\le i$。转移方程为 $f_i=\max\{f_j+1\}$。发现这就是一个三维偏序问题，可以直接套用 $\text{CDQ}$ 分治来优化 $\text{DP}$。

具体转移方法和「HDU 4742」Pinball Game 3D 类似。

时间复杂度：$\mathcal O(n\log^2 n)$。

Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5;

int n, m, f[N];

struct Data {
    int v, l, r, idx;
    Data(int _v = 0, int _l = 0, int _r = 0,int _idx = 0) {
        l = _l, r = _r, idx = _idx;
    }
} a[N];

struct BIT {
    int b[N];
    void modify(int x, int v) {
        for (; x < N; x += x & -x) b[x] = std::max(b[x], v);
    }
    int query(int x) {
        int ans = 0;
        for (; x; x ^= x & -x) ans = std::max(ans, b[x]);
        return ans;
    }
    void clear(int x) {
        for (; x < N; x += x & -x) b[x] = 0;
    }
} bit;

bool cmpR(Data a, Data b) {
    return a.r < b.r;
}
bool cmpV(Data a, Data b) {
    return a.v < b.v;
}
bool cmpI(Data a, Data b) {
    return a.idx < b.idx;
}
void CDQ(int l, int r) {
    if (l == r) {
        return;
    }
    int m = (l + r) >> 1;
    CDQ(l, m);
    std::sort(a + l, a + m + 1, cmpR);
    std::sort(a + m + 1, a + r + 1, cmpV);
    int j = l;
    for (int i = m + 1; i <= r; i++) {
        for (; j <= m && a[j].r <= a[i].v; j++) {
            bit.modify(a[j].v, f[a[j].idx]);
        }
        f[a[i].idx] = std::max(f[a[i].idx], bit.query(a[i].l) + 1);
    }
    for (int i = l; i < j; i++) {
        bit.clear(a[i].v);
    }
    std::sort(a + m + 1, a + r + 1, cmpI);
    CDQ(m + 1, r);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].v);
        a[i].l = a[i].r = a[i].v;
        a[i].idx = i;
        f[i] = 1;
    }
    for (int i = 1; i <= m; i++) {
        int x, v;
        scanf("%d%d", &x, &v);
        a[x].l = std::min(a[x].l, v);
        a[x].r = std::max(a[x].r, v);
    }
    CDQ(1, n);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = std::max(ans, f[i]);
    }
    printf("%d\n", ans);
    return 0;
}