Нужно реализовать ДО с запросами:
запрос (pos, x)
Найти
Ближайший к pos элемент, больший либо равный х
Изменить значение элемента в массиве
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | nor | 157 |
6 | maroonrk | 155 |
7 | -is-this-fft- | 152 |
8 | Petr | 146 |
8 | orz | 146 |
10 | BledDest | 145 |
Нужно реализовать ДО с запросами:
запрос (pos, x)
Найти
Ближайший к pos элемент, больший либо равный х
Изменить значение элемента в массиве
Название |
---|
Автокомментарий: текст был обновлен пользователем Tigutor (предыдущая версия, новая версия, сравнить).
Ближайший справа или слева? Или сразу с двух сторон нужно найти такой элемент, что $$$|\text{pos}-i|$$$ минимально и $$$a_i \ge x$$$?
Пусть решаем задачу вправо. Задача влево — зеркальная. Не используя рекурсии, можно подниматься от листа в дереве отрезков, соответствующего отрезку $$$\left[p,p\right]$$$ до тех пор, пока мы не найдем первого предка, левая граница которого не меньше $$$p$$$ и максимум на нем больше $$$x$$$. С этого момента начинаем спускаться от предка, в котором остановились, в другой лист, выбирая каждый раз, пойдем направо или налево. Если максимум слева $$$\ge x$$$, то идем влево, иначе — вправо. Придем в листовую вершину, для которой максимум $$$\ge x$$$, индекс в ней и будет ответом. Если запутались, то нарисуйте на бумаге дерево отрезков для массива из $$$16$$$ элементов, и попробуйте поподниматься от листьев и спускаться к листьям. Асимптотика $$$O(\log(n))$$$ на запрос, так как мы пройдем не больше чем удвоенная высота.
Эта задача, опять же, является древним баяном, и сдать ее можно здесь.