algorithm - spoj 上的 LIS2 方法

我正在解决 spoj 上的 LIS2 问题 http://www.spoj.com/problems/LIS2/.I 遇到了
2D 段树，但我想它不适合这个问题。我阅读了 misof 解决方案
根据这篇文章，spoj 上的 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) ，这可以很容易地扩展到您的问题，这根本不应该太复杂。这涉及使用其节点也是线段树的线段树。

关于algorithm - spoj 上的 LIS2 方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17378305/