spoj上LIS2的实现方法

Question

我在spoj上解决问题LIS2时遇到了2D段树，但我猜它不适合这个问题。我在spoj上读到了misof solution to NICEDAY，根据这篇文章，它类似于这个问题：http://apps.topcoder.com/forums/;jsessionid=F39EBDDC41BEB792536BE044ADC8BA2A?module=Thread&threadID=615154&start=0&mc=2。我也不能理解这两个问题之间的联系，也不能理解misof对NICEDAY的解决方案的复杂性。

PS:我不想要整个解决方案，我也不想要任何通过2D分段树的方法，因为它对这个问题来说太复杂了(我已经尝试过了)

Answer 1

想一想你将如何解决1D问题：

dp[i] = longest increasing subsequence that ends at position i.

对于每个i，我们必须将a[i]附加到j中，使dp[j]为maximum且为a[j] < a[i]。我们可以通过更改dp数组的定义，使用高级数据结构有效地找到这一点：

dp[i] = longest increasing subsequence that ends with the VALUE i

现在，首先对每个位置i执行dp[ a[i] ] = 1。然后，对于每个元素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)，这应该不是太复杂。这涉及到使用分段树，其节点也是分段树。

Answer 2

对我来说，我不认为我们可以使用2D Segment Tree来解决这个问题，因为我们需要一个10^5x10^5的表格来处理2D Segment Tree，这太大了。