algorithm - 不同标记的数量

Question

我遇到了一个有趣的问题，但我无法很好地解决它(比 O(qn) 更好):

一排有n个人。最初，这一行中的每个人都有一些值(value) - 假设 i-th 人有值(value) a_i。这些值成对不同。每个人都会得到一个标记。有两个条件:

1. 如果 a_i <a_j 那么 j-th 人的分数不可能比 i-th 人差。
2. 如果 i <j 那么 j-th 人的分数不会比 i-th 差人(这个条件告诉我们标记序列是非递减序列)。

有 q 个操作。在每个操作中，都会交换两个人(他们交换他们的值)。每次操作后，你都知道这 n 个人可以获得的不同标记的最大数量是多少。

你有什么想法吗？

Answer 1

考虑任意两组，J和 I (j < i and a_j < a_i for all j and i)。在任何交换场景中，a_i是 J 的新最大值和 a_j是 I 的新最小值, 和 J至少向右扩展到并包括 i .

现在如果有任何一组i s 在 i 的右边谁的值都大于 I 左段中的值最多 i , 这个组不会是 I 的一部分, 而不是它自己的组或另一个组的一部分，表示更高的分数。

所以这种交换会减少 J 之间的组数来标记计数。和 I并合并组 J最多 I .

现在考虑组内交换。添加标记的唯一时间是如果 a_i和 a_j ( j < i )，分别是两个相邻段的最小值和最大值，导致该组 split 成这两个段。 Banana123 在下面的评论中表明此条件不充分(例如，3,6,4,5,1,2 => 3,1,4,5,6,2)。我们可以通过在开关之前检查第二小的i来解决这个问题。大于第二大j .

Banana123 还在下面的评论中表示，在这种情况下可以添加多个标记，例如 6,2,3,4,5,1 .我们可以通过在线段树中保留最小值、最大值和组数的记录来处理这个问题，这些记录对应于连续最大值的计数。

示例 1:

                     (1,6,1)  // (min, max, group_count)
       (3,6,1)                      (1,4,1)

  (6,6,1)   (3,5,1)            (4,4,1)   (1,2,1)

6         5        3         4         2         1

交换 2 和 5。更新发生在 log(n) 中，沿着包含 2 和 5 的间隔。 要在更大的间隔中添加组计数，左组的最大值必须低于右组的最小值。但如果不是，就像在第二个示例中那样，我们必须检查树中的下一层。

                      (1,6,1)
       (2,6,1)                       (1,5,1)

  (6,6,1)   (2,3,2)             (4,4,1)   (1,5,1)

6         2         3         4         5         1

交换 1 和 6:

                      (1,6,6)
       (1,3,3)                       (4,6,3)

  (1,1,1)   (2,3,2)            (4,4,1)    (5,6,2)

1         2         3         4         5         6

示例 2:

                      (1,6,1)
       (3,6,1)                       (1,4,1)

  (6,6,1)   (3,5,1)             (4,4,1)   (1,2,1)

6         5         3         4         2         1

交换 1 和 6。在右侧，我们有两组，其中左侧组的最大值大于右侧组的最小值，(4,4,1) (2,6,2) .为了获得准确的标记计数，我们下一级并移动 2进入4的小组数到两分。然后在顶部之前的级别进行类似的检查。

                      (1,6,3)
       (1,5,2)                       (2,6,2)

  (1,1,1)   (3,5,1)             (4,4,1)   (2,6,2)

1         5         3         4         2         6