I was thinking about the following problem (I don't know if it's out there already) and wanted to know how people here would approach it.

You are given a N x M matrix and Q (say these values are <= 1000) transpose operations to execute each of which is a square sub-matrix to be transposed. Print the matrix after executing all operations.

Can we do better than brute force? My thoughts so far are: store the matrix as a list of diagonals. Transposing a sub-matrix is the same as reversing contiguous sub-arrays of some diagonals. The reversing can be done efficiently using lazy propagation but we still have to iterate over the diagonals of the sub-matrix. Can we do better?