题解 SP2371 【LIS2 - Another Longest Increasing Subsequence Problem】

yingjz · 2019-07-24 19:43:06 · 题解

听说此题还没有题解，所以蒟蒻我来一发题解。

这道题是一道三维偏序（i < j, x_i < x_j, y_i < y_j），考虑使用 cdq分治。

cdq分治 x_i < x_j 这一维，然后用树状数组维护 y_i < y_j。

需要注意的是，在递归处理 [mid + 1, r] 这一段之前需要先处理 [l, mid] 对 [mid + 1, r] 的影响，因为这会影响 [mid + 1, r] 内部的更新操作。

所以过程大概是这样的：

void cdq(int l, int r) {
    if (l == r) return; //基本情况
    int mid = (l + r) >> 1;
    cdq(l, mid);
    处理[l, mid]对[mid+1, r]的影响
    cdq(mid + 1, r);
}

至于如何处理 [l, mid] 对 [mid + 1, r] 的影响我们只需要对 [l, r] 区间内的数按照 x_i 排序（保证 x_i < x_j）然后从头往后扫描，一边扫描一遍用树状数组/线段树来维护 y_i 就可以了。需要注意的是 x_i = x_j 是不符合题目要求的。过程如下：

//计算[l,mid]对(mid,r]的影响 
    for (int i = l; i <= r; ++i) id[i] = i;
    sort(id + l, id + r + 1, cmpa); //排序
    for (int i = l; i <= r; ++i)
        if (id[i] <= mid) BIT.add(b[id[i]], dp[id[i]]);
        else dp[id[i]] = max(dp[id[i]], BIT.query(b[id[i]] - 1) + 1);
    for (int i = l; i <= r; ++i)
        if (id[i] <= mid) BIT.clr(b[id[i]]); //清理BIT

有不懂的地方可以看下面的代码（含注释）

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 200007;
int n, n_, ans, a[N], b[N], c[N], dp[N], id[N];

bool cmpa(int i, int j) {
    return a[i] < a[j] || a[i] == a[j] && i > j; //避免x[i]=x[j]的影响，使得x[i]=x[j]的时候查询操作在前
}

struct BinaryIndexTree { //树状数组
    int mx[N];
    void add(int i, int x) {
        for (; i <= n_; i += i & -i)
            mx[i] = max(mx[i], x);
    }
    int query(int i) {
        int res = 0;
        for (; i >= 1; i -= i & -i)
            res = max(res, mx[i]);
        return res;
    }
    void clr(int i) {
        for (; i <= n_; i += i & -i)
            mx[i] = 0;
    }
} BIT;

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    //计算[l,mid]对(mid,r]的影响 
    for (int i = l; i <= r; ++i) id[i] = i;
    sort(id + l, id + r + 1, cmpa);
    for (int i = l; i <= r; ++i)
        if (id[i] <= mid) BIT.add(b[id[i]], dp[id[i]]);
        else dp[id[i]] = max(dp[id[i]], BIT.query(b[id[i]] - 1) + 1);
    for (int i = l; i <= r; ++i)
        if (id[i] <= mid) BIT.clr(b[id[i]]);
    cdq(mid + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d%d", &a[i], &b[i]), dp[i] = 1, c[i] = b[i];
    //离散化
    sort(c + 1, c + n + 1); 
    n_ = unique(c + 1, c + n + 1) - c - 1;
    for (int i = 1; i <= n; ++i) b[i] = lower_bound(c + 1, c + n_ + 1, b[i]) - c;
    cdq(1, n);
    for (int i = 1; i <= n; ++i) ans = max(ans, dp[i]);
    printf("%d\n", ans);
    return 0;
}