Мне очень интересно, умеют ли сейчас люди решать вот такую задачу (я приведу сперва основную идею, а потом несколько вариаций условия):

Дана плоскость т.е. бесконечный грид точек с целыми координатами. На плоскость упали по очереди N прямоугольников (по очереди, значит, порядок важен) со сторонами параллельными осям координат и значением value_i внутри. Для всех точек, покрытых прямоугольником, нужно сделать некоторую операцию с value_i. После этого вам поступают K запросов вида "посчитайте что-нибудь на прямоугольнике".

Предполагается, что структуру данных для N прямоугольников можно строить в Offline, а вот на запросы нужно отвечать в Online.

1. операция +=, запрос сумма
2. операция +=, запрос минимум
3. операция присваивание, запрос сумма
4. операция присваивание, запрос минимум

Утверждается, что я умею решать все 4 задачи за следующее время:

1. Time = Nlog, Memory = Nlog, AnswerQuery = log
2. Time = Nlog², Memory = Nlog², AnswerQuery = log
3. Time = Nlog², Memory = Nlog, AnswerQuery = log
4. Time = Nlog³, Memory = Nlog², AnswerQuery = log

Краткое описание решений:

1. 1-я задача: Scanline + Persistent Дерево Отрезков
2. 2-я задача: Давайте для каждого K для каждого X-а предподсчитаем дерево отрезков по Y для полоски [X..X+2^K) делается это опять же ScanLine-ом с Persistent Деревом Отрезков.
3. 3-я задача: Scanline + Persistent Дерево Отрезков, при этом на дереве отрезков операция сложнее. Нужно добавлять и удалять информацию вида "на отрезок [L..R] в момент времени t кто-то упал", и, считая сумму на отрезке, выбирать последнее по t событие для каждой точки. Утверждается (1) если нет удаления, добавлять не трудно, (2) удалять не нужно. От удаления я избавляюсь также, как и в Dynamic-Connectivity в Offline, далее ссылка на условие задачи: http://195.19.228.2/Sk1/download/codeforces/connect.pdf
4. 4-я задача: 2+3

UPD про задачи (2 и 3):

Я извиняюсь перед теми, кто видел первую версию поста. "Краткие решения" к задачам 2 и 3 были перепутаны местами =(