By MohammadParsaElahimanesh, history, 7 weeks ago,

Hello,

we have array A[n][n] and q queries. each time we get l r x means we should assign A[i][j] = x (l <= i,j <= r)

at end we want to know sum of elements in A, initially A[i][j] = 0

n <= 200'000

q <= 200'000

How we can solve this problem or what is the best time complexity we can reach?

• +10

 » 7 weeks ago, # | ← Rev. 6 →   +5 Edit: the problem is slightly different, so I don't think divide and conquer works.UPD: idea (I don't know if it works)If you store the main diagonal of the matrix in a segment tree, and you are able to get, for each diagonal, the next diagonal in $O(\log n)$ amortized, you can retrieve the sum of the whole matrix at the end.
•  » » 7 weeks ago, # ^ |   0 yes, it's offline.
 » 7 weeks ago, # | ← Rev. 3 →   +13 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.
 » 7 weeks ago, # |   0 I am not sure, but can we use 2-D segment trees with lazy updates? Each query will be answered in O(log2n).
•  » » 7 weeks ago, # ^ |   0 Generally, you can't use lazy propagation in 2D segment trees.