Запросы в массиве

Revision ru1, by Dword, 2018-12-05 21:37:20

Здравствуйте. Хотел бы узнать решение следующей задачи. Дан массив a[0..N-1]. Нужно отвечать на запросы двух типов, желательно за O(log^2(N)) на запрос: 1) L R x — найти кол-во различных элементов отрезка массива a[L..R], меньше либо равных x. 2) i x — изменить элемент a[i] на x. Знаю, как находить кол-во различных элементов на отрезке за O(log^2(N)) на запрос. Думал над применением похожей идеи в данной задаче, но ничего нормального так и не придумал. Какие будут идеи?

Tags структуры данных, запросы

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru1 Russian Dword 2018-12-05 21:37:20 551 Первая редакция (опубликовано)