Диппер и аппарат

Будем решать задачу в оффлайн. По m запросам создадим события:

для первого типа запросов l r s:

для второго типа запросов i x y:

Отсортируем события сначала по первой координате, а при равенстве — по второй. При событии 1-го типа — добавляем пару (j, |s|) в декартово дерево, при событии 3-го типа — удаляем пару (j, |s|) из декартова дерева. В качестве x значения используем j, а |s| используем для того, чтобы поддерживать сумму длин добавленных строк.

При событии 2-го типа нужно выбрать такие строки, которые попали в подстроку-запрос. Для этого выберем в декартовом дереве такой наименьший префикс, что сумма длин строк на нем больше либо равна y из запроса, а также наибольший префикс, что сумма длин строк на нем меньше либо равна x. Это стандартная задача и решается просто спуском по декартову дереву, подобно тому, как делается split. Обойдем данное поддерево и сконкатенируем строки в нем. Так как суммарная длина запрашиваемых подстрок не превосходит 106, суммарное количество вершин, которые мы обойдем, не превзойдет 106.

Итоговая сложность получается