MohammadParsaElahimanesh's blog

By MohammadParsaElahimanesh, history, 7 weeks ago, In English

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?

thanks in advance

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 weeks ago, # |
Rev. 6   Vote: I like it +5 Vote: I do not like it

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

UPD:

idea (I don't know if it works)
»
7 weeks ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Generally, you can't use lazy propagation in 2D segment trees.