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

Автор dmkz, история, 6 лет назад, перевод, По-русски

Недавно узнал, что многие двумерные задачи на offline запросы можно решить с помощью сканирующей прямой и дерева отрезков или дерева фенвика, но не могу найти, на чем потренироваться. Надеюсь, вы можете подкинуть куда можно эту штуку заслать. Заранее спасибо!

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

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Что-нибудь такое подойдёт?

Ещё есть вот эта классическая задача.

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

На сборах в МФТИ в DivB этой осенью был отдельный контест на эти задачи. Вот одна из задач, которая была там.

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

Вот простая и классическая

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

I strictly recommend you to check out -Morass-'s topic with problems grouped by algorithm.

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

Excuse me, but what is scanline? do you actually mean scanning the array (sliding window or two pointers)?