Блог пользователя RNR

Автор RNR, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • -19
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 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?

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится +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.

»
6 лет назад, # |
  Проголосовать: нравится 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?

»
6 лет назад, # |
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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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