Number of different brands

Question

I ran into an interesting problem, and I cannot solve it with good complexity (better than O (qn)):

There are n people in a row. Initially, each person in this line has a certain meaning - let's say that the i-th person has the value a_i. These values ​​are pairwise different. Everyone gets a mark. There are two conditions:

• If a_i <a_j, then the j-th person cannot degrade the score than the i-th person.
• If I <j, then the j-th person cannot degrade the score than the i-th person (this condition tells us that the sequence of labels is a non-decreasing sequence).

There are q operations. In each operation, two people change places (they change their values). After each operation, you report what is the maximum number of different marks that these Russian people can receive.

Do you have any ideas?

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 extends to the right, at least to and including I

Now, if any group from I right of I were whos more than the values ​​in the left segment I to I , this group would not be part of I , but rather its own group or part of another group, indicating a higher mark.

Thus, this type of swap will reduce the number of labels by the number of groups between J and I and unite the groups J to I

Now consider a group swap. The only time a character is added if a_i and a_j ( j < i ) are the minimum and maximum, respectively, of two adjacent segments, which leads to the division of the group into these two segments. Banana123 showed in a comment below that this condition is not enough (for example, 3,6,4,5,1,2 => 3,1,4,5,6,2). We can solve this by also checking before the switch that the second smallest I greater than the second largest J

Banana123 also showed in the comment below that in this case more than one character can be added, for example 6,2,3,4,5,1 . We can handle this by storing the min, max record and the number of groups that correspond to the count of consecutive maxes in the segment tree.

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 

Change 2 and 5. Updates occur in the log (n) at intervals of 2 and 5. To add the number of groups in a larger interval, the left group max must be lower than the right group min. But if this is not the case 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 

Exchange 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 

Change 1 and 6. On the right side, we have two groups, where the left group max is larger than the right group min, (4,4,1) (2,6,2) . To get the exact number of marks, we go down and move 2 to group 4 to get a score of two characters. A similar study is then performed at the level to 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 

Answer 2

Here's the solution O (n log n):

• If n = 0 or n = 1, then there are n distinct labels.
• Otherwise, consider the two "halves" of the list, LEFT = [1, ⁿ / ₂ ] and RIGHT = [ ⁿ sub> 2sub> + 1, & nbsp, N]. (If the list has an odd number of elements, the middle element can go in any half, it does not matter.)
• Find the largest value in LEFT - name it _{LEFT_MAX} - and the lowest value in the second half; name it _{RIGHT_MIN} .
• If _{LEFT_MAX} <a _{RIGHT_MIN} , then there is no need for any labels to overlap between them, so you can simply rewrite each half and return the sum of the two results.
• Otherwise, we know that there is some segment that extends from at least LEFT_MAX to RIGHT_MIN, where all elements must have the same label.
• To find the leftmost part of this segment, we can scan to the left from RIGHT_MIN to 1, tracking the minimum value that we have seen so far, and the position of the leftmost element, which, as we have found, is larger than some of the following - the right. (This can actually be optimized a little more, but I don’t think we can improve the algorithmic complexity by doing this, so I won’t worry about it.) And, conversely, find the extreme edge of the segment.
• Suppose the segment in question extends from LEFTMOST to RIGHTMOST. Then we just need to recursively calculate the number of different labels in [1, LEFTMOST) and in (RIGHTMOST, n] and return the sum of the two results plus 1.

Answer 3

I was not able to get a complete solution, but here are a few ideas about what can and cannot do.

Firstly: it is impossible to find the number of labels in O (log n) only from an array - otherwise you could use your algorithm to check if the array is sorted faster than O (n), and this is clearly impossible.

General idea: spend O (n log n) to create any additional data that will allow you to calculate the number of labels in O (log n), and the indicated data can be updated after exchanging in O (log n) time, Perhaps a useful part for inclusion is the current number of tags (for example, finding the number of tags changed may be easier than calculating what it is). Since the update time is O (log n), you cannot afford to store anything related to the label (for example, “the last person with the same label”) for each person - otherwise, you will take an array 1 2 3 ... n and changing many times first and the last element will require that you update this additional data for each element of the array.

Geometric interpretation: as an example, take your sequence 4 1 3 2 5 7 6 8 , we can draw points (i, a_i):

  |8 +---+- |7 | | 6| +-+---+ |5| -------+-+ 4 | 3 | 2| 1 | 

In other words, you need to cover all points with the maximum number of squares. Corollary: exchanging points from different squares a and b reduces the total number of squares by |ab| .

The method of squares of indices: let n = 2 ^ k (otherwise you can add less than n fictional persons who will never participate in exchanges), let 0 <= a_i <n. We can create objects O (n log n) - "squares index "- which are" responsible "for points (i, a_i): a * 2 ^ b <= i <(a + 1) * 2 ^ b or a * 2 ^ b <= a_i <(a + 1) * 2 ^ b (on our plane this will look like a cross centered on the diagonal line a_i = i). Each swap affects only the squares of the index O (log n).
The problem is that I cannot find what information to store for each square of the index so that it can quickly find the number of labels? all I have is the feeling that such an approach can be effective.

Hope this helps.

Answer 4

First, we normalize the problem first, so that a_i is in the range from 0 to n-1 (can be achieved in O (n * logn) by sorting a, but just need to be done once so that we are fine).

 function normalize(a) { let b = []; for (let i = 0; i < a.length; i++) b[i] = [i, a[i]]; b.sort(function(x, y) { return x[1] < y[1] ? -1 : 1; }); for (let i = 0; i < a.length; i++) a[b[i][0]] = i; return a; } 

To get the maximum number of tags, we can count how many times

i + 1 == mex(a[0..i]) , i integer element [0, n-1]

a[0..1] denotes a submatrix of all values ​​from index 0 to i .

mex() is the minimum exception, which is the smallest value that is not in the sequence 0, 1, 2, 3, ...

This allows us to solve one instance of the problem (ignoring the swaps at the moment) in O (n), for example. using the following algorithm:

 // assuming values are normalized to be element [0,n-1] function maxMarks(a) { let visited = new Array(a.length + 1); let smallestMissing = 0, marks = 0; for (let i = 0; i < a.length; i++) { visited[a[i]] = true; if (a[i] == smallestMissing) { smallestMissing++; while (visited[smallestMissing]) smallestMissing++; if (i + 1 == smallestMissing) marks++; } } return marks; } 

If we change the values ​​to the indices x and y (x <y), then mex for all values ​​of i <x and i> y does not change, although this is an optimization, unfortunately, this does not improve complexity and still O (qn).

We can notice that hits (where the sign is increased) are always at the beginning of an ascending sequence, and all matches within the same sequence must be [i] == i, except for the first, but cann Output the algorithm from it again:

 0 6 2 3 4 5 1 7 *--|-------|*-* 3 0 2 1 4 6 5 7 -|---|*-*--|*-*