remidinishanth's blog

By remidinishanth, history, 6 months ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • -19
  • Vote: I do not like it  

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Could you give the source of the question ?? It will be easier to help.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was just thinking of this and not from any contest or from any other OJ.

»
6 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
6 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was just thinking of a DS which does this type of queries efficiently and hence thought of this question. Thanks.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For example query 2 can be what is the element at index i or so instead of printing.

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Then it can be done in logn itself. I may have seen something similar in some oj, you may try googling

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by remidinishanth (previous revision, new revision, compare).