O(NlogN) 或 O(Nlog^2N) 中坐标值的 LIS

Question

这是一个标准的动态规划问题LIS PROBLEM

我想要二维坐标中点的最长递增子序列

即数组中索引 i 处的 2 个点 A(x1,y1) 和数组中索引 j 处的 B(x2,y2) 可以是递增序列的一部分，如果 (x1<=x2) && (y1 <=y2) && !(x1==x2 && y1==y2) && (j>i)

我的代码如下，使用标准 DP 的 O(N^2) :-

#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;


struct Pair
{
    int x;
    int y;
};



int main()
{

    int n;
    cin>>n;

    vector<Pair> arr;
    int L[1000000];

    Pair a;

    int i;int Maxchain=0;
    for(i=0;i<n;i++)
    {

        cin>>a.x>>a.y;
        arr.push_back(a);

        L[i]=0;
        for (int j = i-1; j >=0; j--)
        {

            if ((L[j]>(Maxchain-1))&&(L[j]>=L[i])&&(arr[j].x <= arr[i].x) && (arr[j].y <= arr[i].y) && !(arr[j].x == arr[i].x && arr[j].y == arr[i].y))
                L[i] = L[j]+1;


        }

                Maxchain = L[i]>Maxchain ?L[i]:Maxchain ;

    }
    cout<<Maxchain;

    return 0;
}

这是一个复杂度为 O(N^2) 的解决方案，能否进一步简化或使用任何算法在复杂度 O(NlogN) 或复杂度 O(Nlog^2N) 中求解？

参考在这里找到了一些东西：

Longest Increasing Subsequence (LIS) with two numbers

第二个答案更适合我的情况，但我们如何实施呢？

需要更好的答案或算法。

Answer 1

我假设两个坐标都在[0..N-1]范围内（如果不是这样，我们可以"compress"它们而不改变它们的顺序关系）。

让我们仔细看看标准的动态规划解决方案。设 f[i] 为在第 i 位置结束的最长递增子序列的长度。一种简单（但缓慢）的计算方法是迭代所有先前的元素并选择最佳元素。我们想要找到的是 max f[j] 对于 p[j].x <= p[i].x 和 p[j].y <= p[j].y 这样的所有 j。它看起来像是矩形中的某种二维查询（我知道还有另一个条件 p[j] != p[i]，但我们可以通过查询两个矩形 (p[i].x - 1, p[i].y) 和 (p[i].x, p[i].y - 1) 来解决它.).

所以我们需要一个支持两种操作的数据结构：添加具有特定值的点和获取矩形中的最大值。按 x 坐标存储平衡二叉搜索树按 y 坐标为其范围内的所有点存储的线段树可以在每个查询 O(log^2 N) 中完成。每个查询范围被分解为树中最多 O(log N) 个节点。如果是插入查询，我们需要将当前点 (p[i].x, p[i].y) 的值 f[i] 插入到每个节点的二叉搜索树中。如果是获取最大值查询，我们需要获取每棵树的某个前缀的最大值。无论哪种方式，我们对每个查询执行 O(log N) 个二叉搜索树的 O(log N) 操作。因此，总时间复杂度为(N * log^2 N)。 space 复杂度为 O(N log N)，因为树中有 O(log N) 个级别，每个点在每个级别最多可以出现一次。

此解决方案已经满足您的要求，但看起来很难编码。我们可以稍微简化一下。我们可以做两个 "runs"：在第一个运行期间，我们只存储进入线段树每个节点的查询（到目前为止我们不存储任何额外信息）。现在我们可以保留节点中出现的所有数字的向量和相同长度的二叉索引树以跟踪每个前缀的最小值并有效地获取它（大图：我们使用了我们知道所有的事实预先查询，因此我们可以使用排序向量和二叉索引树的组合而不是二叉搜索）。时间和space复杂度分析同上

简短回顾：我们使用了一种数据结构，该数据结构支持矩形中的最大查询和有效插入新点，以加快为 i 中的固定 i 找到最佳 j =31=] 动态规划求解O(N log^2 N)。

O(NlogN) 或 O(Nlog^2N) 中坐标值的 LIS

LIS for coordinate values in O(NlogN) or O(Nlog^2N)

c++

algorithm

dynamic-programming

c++11

lis