Daeshin High School and Queries

Store every discomfort value directly in a $4 \times N$ array.

For a type 1 query, inspect the construction position and its four neighbors. Increase only the positions that lie inside the building. Since at most five positions are inspected, one update takes $O(1)$ time.

For a type 2 query, scan the requested floor from classroom $1$ through classroom $N$. Update the answer only when a strictly larger discomfort value is found. This automatically chooses the smallest classroom number in case of a tie.

After all queries, scan floors $1$ through $4$, and classrooms $1$ through $N$ within each floor. Again, update the answer only for a strictly larger value. The required tie-breaking order is then satisfied automatically.

The time complexity is $O(QN)$, and the space complexity is $O(N)$.

Solution written by GPT5.6