## 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 , the number of new inversions is equal to the number of where . This can be found in time by using a range tree.

Time Complexity:

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 , then the number of new inversions is the number of such that . If , then the number of new inversions is the number of such that .

Time Complexity:

For the final subtask, we note that we can represent every value with the tuple .

One solution is to sort all of the points by their values. The number of new inversions equals the number of points where , and either or .

A memory-optimized 2D data structure can solve this in .

Alternatively, we can use divide and conquer with a 1D range tree, which also yields an solution.

Time Complexity:

## Comments

There are no comments at the moment.