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

**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:

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