LIS для значений координат в O (NlogN) или O (Nlog^2N)

Question

Это стандартный Динамическое программирование Вопрос LIS PROBLEM

Я хочу самую длинную возрастающую подпоследовательность для точек в 2D координаты

, то есть 2 Точки A (x1, y1) с индексом I в массиве, в (х2, у2) с индексом J в массиве может быть частью возрастающей последовательности, если (x1 < = х2) & & (у1 < = у2) & &! (x1 == x2 & & y1 == y2) & & (J> я)

мой код, как показано ниже, который является O (N^2) с использованием стандартного DP: -

#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-й позиции. Простой (но медленный) способ его вычисления слишком перебирает все предыдущие элементы и выбирает оптимальный. То, что мы хотим найти, это max f[j] для всех таких j, что p[j].x <= p[i].x и p[j].y <= p[j].y. Это похоже на какой-то двухмерный запрос в прямоугольнике (я знаю, что есть другое условие, которое p[j] != p[i], но мы можем обойти его, запросив два прямоугольника и (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) уровней, и каждая точка может встречаться где-то не более одного раза за уровень.

Это решение уже удовлетворяет вашим требованиям, но оно довольно сложно кодировать. Мы можем немного упростить его. Мы можем выполнить два «прогона»: во время первого запуска мы просто сохраняем запросы, которые входят в каждый узел дерева сегментов (мы пока не храним никакой дополнительной информации).Теперь мы можем сохранить вектор всех чисел, которые когда-либо встречаются в узле, и двоичное дерево индексов одинаковой длины для отслеживания минимума для каждого префикса и эффективного его использования (общая картина: мы использовали тот факт, что мы знаем все запросы заранее, поэтому мы можем использовать комбинацию отсортированного вектора и двоичного дерева индексов вместо двоичного поиска). Анализ сложности времени и пространства такой же, как и выше.

Короткое резюме: мы использовали структуру данных, которая поддерживает максимальный запрос в виде прямоугольника и вставки новых точек эффективно ускорить поиск наилучшего j для фиксированного i в O(N^2) динамического программирования решения для ее решения в O(N log^2 N).