Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

Блог пользователя Truba

Задача из SPOJ
Автор Truba, 10 лет назад, По-русски

Привет Кодфорсчане! Недавно начал решать задачи на дерево отрезков, наткнулся на задачи "Can you answer these queries". Решил только первую и третью но никак не могу решить вторую. Я понял что спрашивают но, ничего на ум не приходит. Поискал в Google и нашел блог MinakoKojima но ничего не понял. Помогите с решением пожалуйста!

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Правильно ли я понял, что нам нужно среди всех подотрезков отрезка [X;Y] найти тот, сумма на котором максимальна?

Если да, то это относительно несложно.

Во-первых, подсчитаем префиксные суммы для всех отрезков [0;i], назовем их sum[i].

Пусть у нас есть отрезок [X;Y], и мы его как-то разобьем на две части: [X;M] и [M + 1;Y]. Тогда оптимальный ответ может выглядеть следующим образом:

  1. Он является подотрезком первого отрезка.
  2. Он является подотрезком второго отрезка.
  3. Левый конец лежит в первом отрезке, а правый — во втором.

Первые два случая тривиальны, а оптимальный ответ третьего типа выглядит так: берется максимум среди sum[i] на отрезке [M + 1;Y] — это будет правым краем отрезка, и берется минимум среди sum[i - 1] на отрезке [X;M] — это левый край.

Итого нам нужно в каждой вершине дерева отрезков хранить три вещи: максимум среди sum[i] на этом отрезке, минимум среди sum[i - 1] на этом отрезке и оптимальный ответ на этом отрезке.

Если что-то не понятно — скажите, что именно.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Кодфорсчане) На лурке сидишь?)

→ Ответить