Editorial for DMOPC '19 Contest 7 P5 - Soriya's Programming Project - Olympiads Online Judge

Editorial for DMOPC '19 Contest 7 P5 - Soriya's Programming Project

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

The first subtask is very similar to the classic inversion counting problem.

For every $i$ $i$ , the number of new inversions is equal to the number of $j < i$ $j < i$ where $a_j < a_i$ $a_{j} < a_{i}$ . This can be found in $\mathcal O(N \log N)$ $O (N \log N)$ time by using a range tree.

Time Complexity: $\mathcal O(N \log N)$ $O (N \log N)$

For the second subtask, we can maintain a range tree to count the number of 1's in a given range, and a second range tree to count the number of 2's in a given range.

If $a_{p_i} = 1$ $a_{p_{i}} = 1$ , then the number of new inversions is the number of $j < p_i$ $j < p_{i}$ such that $a_j = 2$ $a_{j} = 2$ . If $a_{p_i} = 2$ $a_{p_{i}} = 2$ , then the number of new inversions is the number of $j > p_i$ $j > p_{i}$ such that $a_j = 1$ $a_{j} = 1$ .

Time Complexity: $\mathcal O(N \log N)$ $O (N \log N)$

For the final subtask, we note that we can represent every value with the tuple $(p_i, a_i, i)$ $(p_{i}, a_{i}, i)$ .

One solution is to sort all of the points by their $p_i$ $p_{i}$ values. The number of new inversions equals the number of points where $p_j < p_i$ $p_{j} < p_{i}$ , and either $a_i < a_j \land j < i$ $a_{i} < a_{j} \land j < i$ or $a_i > a_j \land j > i$ $a_{i} > a_{j} \land j > i$ .

A memory-optimized 2D data structure can solve this in $\mathcal O(N \log^2 N)$ $O (N \log^{2} N)$ .

Alternatively, we can use divide and conquer with a 1D range tree, which also yields an $\mathcal O(N \log^2 N)$ $O (N \log^{2} N)$ solution.

Time Complexity: $\mathcal O(N \log^2 N)$ $O (N \log^{2} N)$

Comments

There are no comments at the moment.