Help needed in Segment Tree question of Pilot Course.

Revision en1, by rajkumar62506, 2021-02-12 15:50:23

Hello, Can anyone provide hint to solve below problem on segment tree.

Problem Link:Problem Link

Problem Description:

A city is a sequence of n cells numbered from 0 to n−1. Initially, all cells are empty. Then m events of one of two types occur sequentially:

a building with the strength h is being constructed in the cell i (if the building already existed in this cell, it is demolished and replaced with a new one),

in the interval from l to r−1 an earthquake of power p happens, it destroys all buildings whose strength is not more than p. Your task is for each earthquake to say how many buildings it will destroy.


The first line contains the numbers n and m, the number of cells and the number of events (1≤n,m≤105). The following m lines describe events. The description of each event is as follows:

1 i h: a building with the strength h is constructed in the cell i (0≤i<n, 1≤h≤10^9).

2 l r p: an earthquake of power p happens on a segment from l to r−1 (0≤l<r≤n, 0≤p≤10^9).


For each event of the second type, print how many buildings were destroyed.


  Rev. Lang. By When Δ Comment
en1 English rajkumar62506 2021-02-12 15:50:23 1244 Initial revision (published)