30iq's blog

By 30iq, history, 5 years ago, In Russian

Всем привет. Столкнулся с задачей :
Дан массив чисел длины n, 1 <= a[i] <= n, поступают запросы двух видов.
1) l r X Y ( 1 ≤ l ≤ r ≤ n , 1 ≤ X , Y ≤ n ) всем i, l <= i <= r, если arr[i] == X, то установить в arr[i] значение Y.
2) l r найти K-й порядковый элемент на отрезке с l по r.
n <= 10^5.
Хотел решить сам, но никак не выходит. Уже несколько дней не могу нормально спать)), помогите с решением, пожалуйста. Заранее спасибо.

  • Vote: I like it
  • +11
  • Vote: I do not like it