Number of different marks

Question

I came across an interesting problem and I can't solve it in a good complexity (better than O(qn)):

There are n persons in a row. Initially every person in this row has some value - lets say that i-th person has value a_i. These values are pairwise distinct. Every person gets a mark. There are two conditions:

1. If a_i < a_j then j-th person cant get worse mark than i-th person.
2. If i < j then j-th person can't get worse mark than i-th person (this condition tells us that sequence of marks is non-decreasing sequence).

There are q operations. In every operation two person are swapped (they swap their values). After each operation you have tell what is maximal number of diffrent marks that these n persons can get.

Do you have any idea?

Answer 1

Consider any two groups, J and I (j < i and a_j < a_i for all j and i). In any swap scenario, a_i is the new max for J and a_j is the new min for I, and J gets extended to the right at least up to and including i.

Now if there was any group of is to the right of i whos values were all greater than the values in the left segment of I up to i, this group would not have been part of I, but rather its own group or part of another group denoting a higher mark.

So this kind of swap would reduce the mark count by the count of groups between J and I and merge groups J up to I.

Now consider an in-group swap. The only time a mark would be added is if a_i and a_j (j < i), are the minimum and maximum respectively of two adjacent segments, leading to the group splitting into those two segments. Banana123 showed in a comment below that this condition is not sufficient (e.g., 3,6,4,5,1,2 => 3,1,4,5,6,2). We can address this by also checking before the switch that the second smallest i is greater than the second largest j.

Banana123 also showed in a comment below that more than one mark could be added in this instance, for example 6,2,3,4,5,1. We can handle this by keeping in a segment tree a record of min,max and number of groups, which correspond with a count of sequential maxes.

Example 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

Swap 2 and 5. Updates happen in log(n) along the intervals containing 2 and 5. To add group counts in a larger interval the left group's max must be lower than the right group's min. But if it's not, as in the second example, we must check one level down in the tree.

                      (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

Swap 1 and 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

Example 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

Swap 1 and 6. On the right side, we have two groups where the left group's max is greater than the right group's min, (4,4,1) (2,6,2). To get an accurate mark count, we go down a level and move 2 into 4's group to arrive at a count of two marks. A similar examination is then done in the level before the top.

                      (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