Mini March Coding Challenge 2014
Kirito is facing a large field of ~N~ rows by ~M~ columns of monsters to the east. Each monster is either powerful or weak. Things may look grim for the Black Swordsman, but luckily he has the powerful skill «Starburst Stream» — a skill that can instantly kill a rectangle of monsters. However, there is a restriction — Kirito can only use this skill if all monsters in every column of the attack rectangle are all either powerful or weak. Also, since Kirito is on the western side of the field of monsters, one of the sides of the rectangle must be on the first column.
Kirito is watching the monsters for ~Q~ minutes. Every minute, two rows ~i~ and ~j~ catches his eye, and he wants to know the largest number of monsters he can kill if he uses «Starburst Stream» on an attack rectangle that has its top side on row ~i~, its bottom side on row ~j~, and its left side on column ~1~. These are merely queries, and Kirito does not actually kill the monsters in that rectangle. Help Kirito find the answer to his query for every pair of rows ~i~ and ~j~. Additionally, once Kirito learns of the answer, the monsters in rows ~i~ and ~j~ feel uneasy because of a mysterious killing intent, and so will switch places one-for-one (i.e. the rows are swapped). You should consider the new configuration of monsters for subsequent queries.
The first line of input has two integers, ~N~ (~1 \le N \le 2000~), the number of rows of monsters, and ~M~ (~1 \le M \le 5000~), the number of columns of monsters.
The next ~N~ lines will contain ~M~ characters each, each of which is either
0, to denote a weak monster or
1, to denote a powerful monster.
The next line of input has one integer, ~Q~ (~1 \le Q \le 50\,000~), the number of minutes Kirito is observing.
The next ~Q~ lines each contain a pair of integers, ~i~ and ~j~ (~1 \le i \le j \le N~), the pair of rows that catch Kirito's interest.
The following additional constraints will apply.
- At least 5% of the marks will be for test cases where ~N \le 100~, ~M \le 100~, and ~Q \le 100~;
- At least 25% of the marks will be for test cases where ~N \le 2000~, ~M \le 2000~, and ~Q \le 20\,000~;
- The remaining marks will be for test cases where ~N \le 2000~, ~M \le 5000~, and ~Q \le 50\,000~.
Warning: Be careful when reading the input, which may exceed 10 megabytes.
For each of the ~Q~ pairs of rows in the input, output a single integer on a line: the largest number of monsters Kirito could kill while satisfying the constraints as described above, or ~0~ if Kirito cannot use the skill «Starburst Stream».
5 8 01000100 01000100 00100111 00100110 00100000 4 1 2 3 5 3 4 2 2
16 15 10 8
For the first pair of rows, ~(1, 2)~, Kirito could use «Starburst Stream» on the entirety of both rows (16 monsters).
The configuration is effectively unchanged, because those rows had the same types monsters in the same positions.
For the second pair of rows, ~(3, 5)~, Kirito could use «Starburst Stream» on a 5 by 3 rectangle (15 monsters).
00100 00100 00100
The configuration changes to:
01000100 01000100 00100000 00100110 00100111
For the third pair of rows, ~(3, 4)~, Kirito could use «Starburst Stream» on a 5 by 2 rectangle (10 monsters).
The configuration changes to:
01000100 01000100 00100110 00100000 00100111
For the last pair of rows, ~(2, 2)~, Kirito could use «Starburst Stream» on the whole row (8 monsters). If there were more queries, this would not change the configuration.