LISこれは標準的な動的プログラミングであるO（NlogN）またはO（Nlog^2N）

Question

の値を座標に質問LIS PROBLEM

Iは、2次元の点のための最長増加サブシーケンスである

、2座標たいです配列内のインデックスiに（X1、Y1）を指し、配列内のインデックスjでB（X2、Y2）が増加するシーケンスの一部とすることができる場合 （X1 < = X2）& &（Y1 < = Y2）& &！ （x1 == x2 & &y1 == y2）& &（J> I）

自分のコードそれ以下O（N^2）標準的な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（NlogN）やO（Nlog^2N）で解くための任意の言い回し？参照用

はここで何かを見つけた：

Longest Increasing Subsequence (LIS) with two numbers

二答えは私の場合のために、より適切であるが、どのように我々はそれを実装することができますか？

より良い回答またはアルゴリズムが必要です。

Answer 1

両方の座標が[0..N-1]の範囲にあると仮定します（そうでない場合は、順序関係を変更せずに「圧縮」できます）。

標準のダイナミックプログラミングソリューションを詳しく見ていきましょう。 f[i]を、i番目の位置で終わる最長増加部分列の長さとする。それを計算する単純な（しかし遅い）方法は、すべての以前の要素に対して繰り返しすぎて、最適なものを選択することです。我々が見つけたいのは、jのmax f[j]がp[j].x <= p[i].xとp[j].y <= p[j].yであることです。矩形内の2-Dクエリのように見えます（p[j] != p[i]という別の条件がありますが、2つの矩形(p[i].x - 1, p[i].y)と(p[i].x, p[i].y - 1)を照会することで回避できます）。

したがって、特定の値を持つポイントを追加し、四角形内の最大値を取得するという2つの操作をサポートするデータ構造が必要です。範囲内のすべての点について平衡二分探索木をy座標で格納するx座標によるセグメントツリーは、クエリごとに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(log N)のレベルがあり、各ポイントはレベルごとに最大で1回発生する可能性があります。

この解決策はすでにお客様の要件を満たしていますが、コード作成はかなり難しいようです。それをやや簡単にすることができます。最初の実行時に、セグメントツリーの各ノードに入るクエリを格納するだけです（これまでの追加情報は保存されません）。今度は、ノード内で発生するすべての数値のベクトルと、同じ長さのバイナリインデックスツリーを保持して、各接頭辞の最小値を追跡し、効率的に取得することができます（大きな図：バイナリ検索の代わりにソートされたベクトルとバイナリインデックスツリーの組み合わせを使用できるように、事前にクエリを実行する必要があります）。時間と空間の複雑さの分析は上記と同じです。

短い要約：私たちは効率的O(N log^2 N)でそれを解決するためにO(N^2)動的なプログラミングソリューションに固定iための最良のjを見つけるスピードアップするために、新たなポイントの長方形および挿入で最大のクエリをサポートするデータ構造を使用していました。