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?
Thanking you.
UPD: Suppose if the query is like find the maximum in [l,r] range etc
One method is to use sqrt-decomposition and create N arrays and then do so that overall complexity reduces to 0(N*sqrt(N))? Are there any other methods?
Could you give the source of the question ?? It will be easier to help.
I was just thinking of this and not from any contest or from any other OJ.
Just save indexes you append element and use them while printing array. Complexity of first query will be O(1). Or, implement some persistent data structure.
I suppose there's some constraint against all the queries being of type 2, because then O(NQ) will be accepted, and with that you can just insert in O(N) using a vector or even just copying the array... Can you link the problem?
I will suggest a treap. You get insertion in logn. Element recovery is logn. So for type 2 it will be nlgn per query but lgn for type 1 query
I was just thinking of a DS which does this type of queries efficiently and hence thought of this question. Thanks.
And type 2 query need not exactly be printing but something like that which need to be processed on the array.I just want to know about some DS which does this type of queries efficiently. Thanks a lot.
For example query 2 can be what is the element at index i or so instead of printing.
Then it can be done in logn itself. I may have seen something similar in some oj, you may try googling
Auto comment: topic has been updated by RNR (previous revision, new revision, compare).