Given an array of N integers, you are given two types of queries:-
Type 1 ::: x y
Append y after index x (array size increases by 1 after every type 1 operation )
Type 2 ::: print
Print the array
What is the efficient way to solve this problem?
Type 2 query takes O(n) time.
So the problem can be solved in O(n^2).
If we are given information that there are many many operations of Type 1 than Type 2 can we reduce the complexity?
For example, if we are given that Type 2 operations are <= sqrt(N) or so?
UPD: Suppose if the query is like find the maximum in [l,r] range etc