Задача на Persistent Segment Tree

Информатика
1

Дан массив a из n чисел. Массив изначально состоит из нулей.
С ним происходит q модификаций. Каждая модификация состоит из тройки чисел (l, r, x). На
i-той модификации числа на индексах j (l<= j <= r) увеличиваются на x.
После всех модификаций будет m запросов. Каждый запрос состоит из пары чисел (pos, x). Ответ
на запрос минимальный по номеру запрос, после которого a[pos] стал больше либо равен x. Если
такого не случилось, то вывести −1.
Первая строка содержит три целых числа n, q, m (1<= n, q, m <= 3e5) размер массива,
количество модификаций, количество запросов.
Следующие q строк описывают ряд модификаций. i-ая модификация, где i (1<= i <= q), будет
содержать три целых числа l[i], r[i], x[i] (1<= l[i] <= r[i] <= n, 1 <= x[i] <= 1e9).
Следующие m строк описывают запросы. i-ый запрос, где i (1<= i <= m), будет содержать два
целых числа pos[i], x[i] (1<= pos[i] <= n, 1 <= x[i] <= 1e9).
Вы можете найти задачу в сайте olymp.krsu.edu.kg под номером 2233
input:
5 3 4
1 2 3
2 3 3
1 1 5
2 3
2 5
1 8
1 9

output:
1
2
3
-1

2

Как можно его решить?

3

Бинпоиском по версиям данного дерева отрезков(в названии темы написано).
Сам бинпоиск за logn, запрос на дереве logn в итоге log²n.

3 лайка
4

Я так и делаю. Вот Мой код hyMNpe - Online C++0x Compiler & Debugging Tool - Ideone.com. RunTime Error

5
подсказка 1

пусть a[pos[i]] в k - тый момент времени стал >= x[i]. Будет ли это верно в моменты времени k + 1, k + 2, k + 3?

подсказка 2

Да, это верно. Значит функция монотонна

подсказка 3

Давай для каждого запроса второго вида бинарить минимальное х

фулл решение

Давай для каждого запроса второго вида бинарить минимальное х и допустим сейчас мы смотрим значение y = (l + r) / 2, то теперь нам нужно узнать значение a[pos[i]] в момент времени y. Это можно делать с помощью persistent segment tree.

Как делать это с помощью persistent segment tree?

  1. Можно в тупую делать пуши
  2. Можно реализовать префиксные сумму. То есть как работает первая операция l[i], r[i], x[i]?
    На самом деле она просто добавляет х ко всем элементам от l до r.
    Можно заметить, что если мы будем в persistent segment tree обновлять l добавляя х и отнимая x от r + 1. То тогда значение для y-того элемента будет запрос от 1 до y + изначальное значение

То теперь мы можем с легкостью узнавать значение a[pos], в момент времени y.

3 лайка
6

N = 5e6 сделал но тоже runtime error.

7

Персистента nlogn памяти, так что N > 5e6, а учитывая что у тебя ещё пуши то N ещё больше будет(у тебя в итоге даже в запросах get появляются новые вершины N > 1e7 может быть даже). Попробуй подобрать нужное значение N, мб в этом дело? Можешь добавить в коде условия такие что при создании вершины с номером \geq N ты выводишь неправильный ответ, и так будет легко определить в этом ли дело.

Ну и на самом деле есть более простое решение с помощью обычной ДОшки и параллельного бин. поиска, которое тратит всего O(n + q) памяти.

Давай закинем все запросы в один массив и запустим функции func(l, r, Q), где Q-это все запросы, а l, r - границы в которых мы ищем ответ.

Изначально l = 0, а r = n, теперь нам нужно разделить запросы из Q на два множества запросов Q_l и Q_r те кто лежат левее m = (r + l) / 2 и те кто лежат правее m.

Как это быстро делать?

Активируем изменения которые лежат на отрезке от l...m, теперь для каждого запроса проверяем стало ли значением на его позиции \geq x, если да то перекидываем этот запрос в Q_l, иначе перекидываем его в Q_r.

Теперь запускаем func(m + 1, r, Q_r)(не убирая те обновления которые мы сделали в дошке), после того как мы возвращаемся обратно, мы должны откатить последние m - l + 1 изменений в ДОшке, это можно сделать обратными операциями(тип если было обновление [l, r, x] то делаем [l, r, -x], и запускаем уже func(l, m, Q_l).

Если правильно работать с памятью то решение будет за O(N) памяти и O(N*log^2(N) + Q*loq^2(N)) времени. На самом деле у меня есть сомнения что это пройдёт по ТЛу.

А теперь вспомним один интересный факт об этой задаче, нас просят делать get только на ОДНОМ элементе, а значит никакие обновления на отрезке здесь и подавно не нужны, мы можем заменить эту задачу на get на префиксе и апдейт на позициях. А значит в решении которое все предлагали выше мы можем перестать говорить о персистентной ДОшке которая требует массовых апдейтов(Что очень неприятно), и перейти к обычной персистентной ДО с апдейтом в позиции и гетом на префиксе, а в решении с параллельным бин. поиском всё становится ещё легче, ведь можно заменить структуру на фенвик, ведь в том решении даже не требуется персистентность.

Подводя итог хочу сказать что перед тем как начать код задумайтесь о том действительно ли нужно решать задачу так, лишние пару минут размышлений и небольших оптимизаций могут спасти вас от десятков минут кодинга и дебага, а в рамках почти любой олимпиады время является очень важным ресурсом.

1 лайк