Help in Segment Tree, Earthquakes

,
1

I am trying to solve the last question in the EDU lesson on Segment Trees part 1 on Codeforces.
Here is the question.

My approach: Store a map at each node of the segment tree. Instead of using the maps of the two children to get the new map, we can be clever and use the invertibility of the operation. Thus the set operation can be done in O(log^2(n)).

Now the range query is tricky, as I need to modify the tree. In the worst case, I would have to modify the map in every node, which seems too much. I know I can do optimizations like not storing 0 as a key and only changing the map for keys less than p, but still feels like it won’t pass. Is this a lazy-propagation question ( as I can answer queries quickly if I don’t update the segment tree, but the answer for the next query will be wrong)?

Or I am overthinking it and there is a very easy solution? This problem is in the Basic segment tree lectures and shouldn’t use advanced concepts.

2 Likes
2

I have too problem in segment tree
Anyone here who can help in segment tree

3

Managed to do it. The actual answer in very easy. Its just a min segment tree, in which we update everything that changes in a range query. Why doesn’t this give TLE? IS this because the way the queries are processed (i.e. building must be built before destroyed).

Is this why the worst case O(nq) never occurs?

@ssrivastava990 @carre @galencolin What are your thoughts?

1 Like
4

I assume your code is something like:

for each query {
  if (type 1) do update;
  else { // type 2
    // assume query parameter is p
    do {
      query_result result = segtree.query(l, r);
      if (result.value >= p) {
        segtree.update(result.index, 0);
      }
    } while (result.value >= p);
  }
}

Then you can make a complexity analysis like this: consider any value > 0 to contribute 1 “energy” to the array. Each type 1 query, you add either 0 or 1 energy. Each type 2 query, for each RMQ query, you remove 1 energy (plus an extra query to confirm there are no more buildings left to destroy). The total energy over the whole process is O(n + q), so the complexity is O((n + q)\log{n}).

5 Likes
5

Yup. My code is similar to the above example.

Thank you for the reasoning.

Now if we change the question to not destroy buildings in type 2 queries. Just return the number of buildings that will be destroyed (Kind of like simulating an earthquake). Type 1 queries stay the same. Then the problem becomes tougher right?

6

Yes, it would be harder, you’d need something weird like mergesort tree

1 Like
7

we can do the above question with SQRT decomposition also (more formally BIT+SQRT) , but is it solvable by only BIT as it has an update query too?

means if there is no update query then we can process queries offline and give the answer using BIT/fenwick tree, but as it has update too, so I think not solvable only using BIT right? @galencolin @udayan14 @rahulmysuru7