Recently I have seen this question in coding Kaze organised by coding Ninja . Can anyone help with the approach .
Amaira is telling a fairy tale to her grandmother . In her tale ,
There are N students denoted with numbers from 1 to N by their age (from the youngest denoted with 1, to oldest with N) , embarked on a train ride. The train leaves from the station 0 and stops in order at stations 1,2,3,.....upto infinity .
Each of the following Amaira statements is of the form " M X A means at stop X child A got out" , where the order of these statements is completely arbitrary. In other words, it doesnot depend on the station order . Her grandmother sometimes asks a question of the form: "D Y B means based on the statements so far, of the children denoted with the number greater than or equal to B, who is the youngest child that rode for Y or less stops ?" If at the moment the grandmother asks the question it hasn't been said so far that a child is getting off the train we assume that the child is riding for an infinite amount of stops.
For each grandmother's question output index of the required child in its own line. If no such child exists output "-1" .
Constraints
2 <= N,Q <=200000
1 <= X,Y <= 1e9 ; 1 <= A,B <=N
Input:
3 4
M 10 3
M 5 1
D 20 2
D 5 1
Output:
3
1
I solved it using Fenwick tree with
std::setin each node.Compress the positions of stations.
For each update, insert $$$A$$$ at the $$$\log n$$$ nodes corresponding to $$$X$$$.
For query, use
lower_bound(B)in each of the $$$\log n$$$ nodes belonging to $$$[1, Y]$$$ prefix and minimize the answer.You can binary search over the answer. Build a min segment tree, where the index is the age and the value is the stop number from which he gets down (Initially all have value inf). Now when you have a query Y, B see what is the nearest index to Y (to the right) that has value less than or equal to B. This can be done using binary search. But the complexity becomes $$$O(q * log^2(n))$$$. To make it $$$O(q * log(n))$$$ do a descent over the segment tree to the index and get the answer. Updates are just point update.
can you tell how you reduced from O (q * log^2(n))) to O(q*log())
It is a common trick known as descending the segment tree. You can look into the section "Searching for the first element greater than a given amount" here