Editorial for IOI '18 P2 - Seats


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.

Subtask 1

Determine whether a set of squares forms a rectangle or not in \mathcal O(HW) time and deal with each query in \mathcal O(H^2 W^2) time.

Subtask 2

Let the square where the number i is written be (r_i, c_i). The sufficient and necessary condition of (r_0, c_0), \dots, (r_t, c_t) forming a rectangle is:

\displaystyle (\max r_i - \min r_i + 1)(\max c_i - \min c_i + 1) = t+1

Here, i moves between 0 and t.

Check if these conditions hold from t = 0 to t = HW-1 inductively in \mathcal O(HW) time.

Subtask 3

If (\max r_i - \min r_i + 1)(\max c_i - \min c_i + 1) > t+1, the next t satisfying the condition is not less than (\max r_i - \min r_i + 1)(\max c_i - \min c_i + 1)-1.

So it is enough to determine this condition in \mathcal O(H+W) numbers.

This condition is determinable independently in \mathcal O(\log(HW)) time using a segment tree. Then each query is dealt with in \mathcal O((H+W) \log(HW)) time.

Subtask 4

Memorize \max and \min of r_i and c_i for each t and recalculate them for t between the two swapped numbers for each query.

Subtask 5

Take t arbitrarily and color the squares with numbers 0, \dots, t black and the squares with numbers t+1, \dots, W-1 white (and add white squares outside of the rectangle.)

The sufficient and necessary condition of black squares forming a rectangle is that the number of pairs of adjacent two squares with different colors is two.

Manage the numbers of such pairs of squares for all values of t and count the number of ts satisfying the condition efficiently using a lazy propagation segment tree and deal with each query in \mathcal O(\log W) time.

Subtask 6

Like above, take t arbitrarily and color the squares with numbers 0, \dots, t black and the squares with numbers t+1, \dots, HW-1 white (and add white squares outside of the rectangle.)

Pay attention to two-times-two squares (sets of adjacent four squares.)

The sufficient and necessary condition of black squares forming a rectangle is as follows:

  • There are only four two-times-two squares which contain exactly one black square.
  • There are no two-times-two squares which contain exactly three black squares.

Manage the numbers of such two-times-two squares for all values of t and count the number of ts satisfying the condition efficiently using a lazy propagation segment tree and deal with each query in \mathcal O(\log(HW)) time.


Comments

There are no comments at the moment.