When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

mahmud2690's blog

By mahmud2690, history, 7 years ago, In English

Hi, i am faced with the following 2D segment tree (actually title says) problem on SPOJ. Problem link here: link. Basically it says to find the area of union of rectangles. Number of rectangles is up to 10^5. Is it possible to solve this problem using 2D segment tree + lazy propagation?. I read about quadtrees, but it's written complexity of per operation in Quadtrees is O(N). Can you give any hint to solve this problem?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you can solve this task with sweep line method, there are some info about it: topcoder tutor