redcoder23's blog

Segment Tree | Help Needed
By redcoder23, history, 4 years ago, In English

An array is given (indexing starts with 1) of size S and N number of queries is given by user Ni=(M P R); 1<=i<=N. Print the Rth minimum element from the array after updating Mth index. Example :- Array : [2, 4, 6, 1, 7] S=5

Queries : N=3

2 5 3

5 3 2

4 8 4

Output :- 5

2

6

How to solve this question.

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 7   Vote: I like it +11 Vote: I do not like it

Use this https://codeforces.com/blog/entry/11080. Or maintain a segtree where a_x = no of elements equal to x then slightly modify technique from this article https://cp-algorithms.com/data_structures/segment_tree.html (Counting the number of zeros, searching for the k -th zero section) to find k-th element or just binary search.

→ Reply