Array and queries

Правка en2, от RNR, 2017-12-18 21:37:38

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

Теги array, horrible queries

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский RNR 2017-12-18 21:37:38 73
en1 Английский RNR 2017-12-14 07:20:41 577 Initial revision (published)