RNR's blog

Array and queries
By RNR, history, 7 years 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

»
7 years 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?

→ Reply
»
7 years 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.

→ Reply
  • »
    »
    7 years 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.

    → Reply
»
7 years 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.

→ Reply
»
7 years 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?

→ Reply
»
7 years 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

→ Reply
  • »
    »
    7 years 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.

    → Reply
  • »
    »
    7 years 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.

    → Reply
  • »
    »
    7 years 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.

    → Reply
    • »
      »
      »
      7 years 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

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply