Задача ШАДа
Дают n отрезков (1 <= n <= 1e5). Каждый отрезок это два числа l, r (1 <= l <= r <= 1e5).
Для каждого натурального числа x которое состоит хотя-бы в одном отрезке, посчитать в скольких отрезках содержится число x.

Например:
5
1 10
2 9
3 8
4 7
5 5
Ответ
1 1
2 2
3 3
4 4
5 5
6 4
7 4
8 3
9 2
10 1

например число 9 встречается только в первом и во втором отрезке.


Решение:

Наверное придет в голову создать массив cnt, размера 1e5, для каждого отрезка l, r пройтись циклом for i in range(l, r + 1) и сделать cnt[i] += 1
Таким образом ответом является все такие пары (i, cnt[i]), такие что cnt[i] > 0.
Проблема в том, что работает этот алгоритм O(m * n), где m = 1e5.

Давайте попытаемся это же решение оптимизировать. Конечно вы можете написать дерево отрезков или дерево Фенвика, но вам скажут, нужно ли писать такие структуры, так как они способны на большее и в этой задаче это лишнее.
Можно придумать решение за O(n + m). Заметим во первых, что задачу можно решить оффлайн. Давайте для каждого отрезка l, r сделаем cnt[l] += 1, cnt[r + 1] -= 1.
Это можно понимать так: Давайте не будем прибавлять плюс один ко всем ячейкам в [l, r] а поставим +1 на позиции l которая будет работать на всем суффиксе, но в таком случае мы должны еще поставить -1 на позиции r + 1, чтобы тот +1 работал только на отрезке [l, r].

И так у нас есть cnt осталось на нем посчитать префикс функцию, после пройтись по префикс функции и вывести все ячейки на которых стоит положительное число.

Время работы O(n + m), где m = 1e5

Код в комментариях.

Такая задача попадалась в Epam epic-institue.
Своего рода ШАД от Epam