16791번 - Bubble Sort 2 서브태스크다국어

Bubble sort is an algorithm to sort a sequence. Let’s say we are going to sort a sequence A₀, A₁, . . . , A_N−1 of length N in non-decreasing order. Bubble sort swaps two adjacent numbers when they are not in the correct order. Swaps are done by repeatedly passing through the sequence. Precisely speaking, in a pass, we swap A_i and A_i+1 if A_i > A_i+1, for i = 0, 1, . . . , N − 2 in this order. It is known that any sequence can be sorted in non-decreasing order by some passes. For a sequence A, we define the number of passes by bubble sort as the number of passes needed to sort A using the above algorithm.

JOI-kun has a sequence A of length N. He is going to process Q queries of modifying values of A. To be specific, in the (j + 1)-th query (0 ≤ j ≤ Q − 1), the value of A_Xj is changed into V_j.

JOI-kun wants to know the number of passes by bubble sort for the sequence after processing each query.

• line 1: N Q
• line 2: A₀ A₁ . . . A_N−1
• line 3 + j (0 ≤ j ≤ Q − 1): X_j V_j

• line 1 + j (0 ≤ j ≤ Q − 1): the number of passes by bubble sort for the sequence right after processing (j + 1)-th query.

• 1 ≤ N ≤ 2 000
• 1 ≤ Q ≤ 2 000
• 1 ≤ A_i, V_j ≤ 1 000 000 000

• 1 ≤ N ≤ 8 000
• 1 ≤ Q ≤ 8 000
• 1 ≤ A_i, V_j ≤ 1 000 000 000

• 1 ≤ N ≤ 50 000
• 1 ≤ Q ≤ 50 000
• 1 ≤ A_i, V_j ≤ 100

• 1 ≤ N ≤ 500 000
• 1 ≤ Q ≤ 500 000
• 1 ≤ A_i, V_j ≤ 1 000 000 000

Given a sequence A = {1, 2, 3, 4} of length N = 4 and Q = 2 queries: X = {0, 2}, V = {3, 1}.

1. For the first query, the value of A₀ is changed into 3. We obtain A = {3, 2, 3, 4}.
2. For the second query, the value of A₂ is changed into 1. We obtain A = {3, 2, 1, 4}.

Bubble sort for A = {3, 2, 3, 4}:

• A is not sorted, so the first pass starts. Since A₀ > A₁, we swap them to get A = {2, 3, 3, 4}. Since A₁ ≤ A₂, we don’t swap them. Since A₂ ≤ A₃, we don’t swap them.
• Now A is sorted, so the bubble sort ends.

Hence, the number of passes by bubble sort is 1 for A = {3, 2, 3, 4}.

Bubble sort for A = {3, 2, 1, 4}:

• A is not sorted, so the first pass starts. Since A₀ > A₁, we swap them to get A = {2, 3, 1, 4}. Since A₁ > A₂, we swap them to get A = {2, 1, 3, 4}. Since A₂ ≤ A₃, we don’t swap them.
• A is not sorted yet, so the second pass starts. Since A₀ > A₁, we swap them to get A = {1, 2, 3, 4}. Since A₁ ≤ A₂, we don’t swap them. Since A₂ ≤ A₃, we don’t swap them.
• Now A is sorted, so the bubble sort ends.

Hence, then number of passes by bubble sort is 2 for A = {3, 2, 1, 4}.