Edit: the problem is slightly different, so I don't think divide and conquer works.

UPD:

You can do this in n^2, start from reverse,i.e., last query to first query , created horizonal and vertical jump pointer so that you can act like it's dp and never visit already colored
I guess parent pointer thing might get the complexity to $$$n^2 log^*n$$$ or $$$n^2 logn$$$, if we use path compression using dsu or might be some binary lifting kind of stuff.

For N log N , you can work construct how will final diagonal look like after all the queries , this you can do with same previous algorithm, with this you also have to store the query index which the diagonal cell is part of., And then iterate on diagonal cells and sum up the height accordingly depending upon what query it is part of.

I am not sure, but can we use 2-D segment trees with lazy updates? Each query will be answered in O(log²n).