Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### remidinishanth's blog

By remidinishanth, history, 12 months ago, ,

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 )

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

•
• -19
•

 » 12 months ago, # |   0 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?
 » 12 months ago, # |   +5 Could you give the source of the question ?? It will be easier to help.
•  » » 12 months ago, # ^ |   0 I was just thinking of this and not from any contest or from any other OJ.
 » 12 months ago, # |   +13 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.
 » 12 months ago, # |   0 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?
 » 12 months ago, # | ← Rev. 3 →   0 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
•  » » 12 months ago, # ^ |   0 I was just thinking of a DS which does this type of queries efficiently and hence thought of this question. Thanks.
•  » » 12 months ago, # ^ |   0 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.
•  » » 12 months ago, # ^ |   0 For example query 2 can be what is the element at index i or so instead of printing.
•  » » » 12 months ago, # ^ |   0 Then it can be done in logn itself. I may have seen something similar in some oj, you may try googling
 » 12 months ago, # |   0 Auto comment: topic has been updated by remidinishanth (previous revision, new revision, compare).