我正在解决LIS2spoj http://www.spoj.com/problems/LIS2/上的问题。我遇到了 2D 段树，但我想它不适合这个问题。我阅读了与这个问题类似的关于 spoj 的misof解决方案
NICEDAY根据这篇文章：
http ://apps.topcoder.com/forums/;jsessionid=F39EBDDC41BEB792536BE044ADC8BA2A?module=Thread&threadID=615154&start=0&mc=2 。我也无法理解这两个问题之间的联系，我也无法理解 misof 解决方案的复杂性NICEDAY。
PS：我不想要整个解决方案，我也不想要通过 2D 段树的任何方法，因为它对于这个问题来说太复杂了（我已经尝试过）
想想你将如何解决一维问题：
dp[i] = longest increasing subsequence that ends at position i.
对于每个i，我们必须附加a[i]到一个j最大dp[j]的 和a[j] < a[i]。dp通过更改数组的定义，我们可以使用高级数据结构有效地找到这一点：
dp[i] = longest increasing subsequence that ends with the VALUE i
现在，最初dp[ a[i] ] = 1对于每个位置i。然后对于每个元素a[i]，您需要最大值dp[0], dp[1], ..., dp[ a[i] - 1 ]. 那么你有dp[ a[i] ] = mx + 1.
您可以通过规范化数组值来找到此最大值（确保它们都在区间内[1, n]）。你可以用排序来做到这一点。例如，如果您的数组是42 562 13，那么n = 3您的新数组将是2 3 1。
这可以通过支持查询和更新最大值的分段树轻松实现。时间复杂度将为O(n log n)。
通过使用 2D 线段树，这可以很容易地扩展到您的问题，获得时间复杂度O(n log^2 n)，这根本不应该太复杂。这涉及使用其节点也是线段树的线段树。
对我来说，我认为我们不能使用 2D Segment Tree 来解决这个问题，因为 2D Segment Tree 需要多达 10^5 x 10^5 的表，这太大了。