c++ - 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] 中范围(如果不是这种情况，我们可以在不改变它们的排序关系的情况下“压缩”它们)。

让我们仔细看看标准的动态规划解决方案。让f[i]是以i结尾的最长递增子序列的长度-th 位置。一种简单(但缓慢)的计算方法是迭代所有先前的元素并选择最佳元素。我们要找的是 max f[j]对于所有这些j那p[j].x <= p[i].x和 p[j].y <= p[j].y .它看起来像是矩形中的某种二维查询(我知道还有另一个条件 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) .空间复杂度为O(N log N)因为有 O(log N)树中的级别，每个点在每个级别的某处最多出现一次。

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

简短回顾:我们使用了一种支持矩形最大查询和有效插入新点的数据结构，以加快找到最佳 j 的速度。对于固定 i在O(N^2)动态规划解决方案O(N log^2 N) .