For ~30\%~ of the points, one could simply use a 2D array to represent the empire. Updates are trivial, while queries simply involve traversing the row and column that the point is in and manually figuring out the longest contiguous subsequence.

Time Complexity: ~\mathcal O(Q(N + M))~

For the final ~70\%~, we can first break the task down row-by-row and column-by-column. For each row or column, we can have a lazy Range-Maximum Query Segment Tree that supports increments to perform our queries, where each node stores the size of the longest contiguous subsequence in that given row or column, that passes through that given node. Figuring out how to perform the updates on the segment tree is left as an exercise to the reader will be described below.

Firstly, we will need some sort of mechanism that allows us to query the start and ending indices of the longest contiguous subsequence passing through any given element, that lies strictly on one row or column. For example, if a given row has the following layout, where * represents an empty tile and # represents an Alicizer:

**###**####**

Assuming this layout starts at index 1, querying either of the first three Alicizers should result in ~3~ for the start index, and ~5~ for the end index. Querying either of the next four Alicizers should result in ~8~ for the start index, and ~11~ for the end index.

There are several ways which this sub-query can be done, but the one with the best constant by far is using a data structure that supports range queries and point updates, such as the Binary Indexed Tree. Two of these data structures could be used for each row and column, such that start.sum(x) and end.sum(x) would return you the start index or the end index, respectively. Additionally, to further improve the constant, one could make the observation that you don't actually need two binary indexed trees, you would only need one that returns the start index, and a simple array that maps starting indices to ending indices.

For placement updates, you could simply check whether or not there are Alicizers on either side of the chunk that you are placing, and update the new merged chunk accordingly. For deletion queries, you can effectively split the current chunk into three sections and update each section accordingly. Keep in mind that the Range-Maximum Query Segment Tree would also need to be updated accordingly.

There are also several other ways to further improve the constant, such as using an iterative segment tree rather than recursive, or using a single array and partitioning it for each column or row rather than using a(n) BIT/Segment Tree/Array for each column or row. With these techniques, a well-written solution in C++, Java 8, or PyPy 2 should pass well under the time limit.

Time Complexity: ~\mathcal O(Q Z \log(N + M))~