Ну это-то понятно, что запрещало сделать 10^4 тестов, вот поэтому и TL. Ты же с увы много пишешь, там такое вообще вроде бы чуть не в каждой задаче :)

Да и с выводом - боян же. cout тормозной, printf непереносимый. Мы сразу ручной вывод int64 писали в тех задачах, где боялись за TL.

Хоть и не Илья, но расскажу наше решение :)

sqrt-декомпозицией разобьём всё на sqrt(n) блоков.

В каждом блоке будем хранить maximum_x - наибольшее x, которым мы красили весь этот блок, и ещё все числа этого блока в порядке сортировки.

Тогда если поступает запрос присвоения, то во всех блоках, которые попадают в наш отрезок целиком, просто обновляем maximum_x. В двух граничных блоках проходимся и присваиваем значения втупую (за sqrt(n). это можно сделать, не пересорчивая содержимое блока (слиянием за линию двух отсортированных массивов), иначе TL).

Теперь пусть пришёл запрос поиска суммы. В двух граничных блоках ответим на запрос втупую. Теперь что делать с целыми блоками: в каждом таком блоке нужно найти, сколько элементов <= текущего maximum_x этого блока; для этого очевидное решение - сделать бинпоиск по содержимому блока (как раз для этого мы и поддерживали его содержимое в отсортированном порядке), но это будет лишний log в асимптотике. Поэтому, заметив, что maximum_x всегда только возрастает, будет хранить в каждом блоке указатель на первый элемент, >= maximum_x, и продвигать его вправо когда надо.

В сумме должно быть N sqrt(N), а не сдали из-за реализационных косяков.