Две карты

Будем поддерживать ответ. При добавлении отрезка нужно добавить к ответу количество отрезков, которые дают длину s в объединении с новым, при удалении — отнять.

Как посчитать, сколько отрезков [li;ri] в объединении с [L;R] дают длину s: рассмотрим несколько случаев.

  1. Если R - L > s, то ответ 0
  2. Эти два отрезка не имеют общих точек, li > R или ri < L. Тогда длина второго отрезка равна leni = s - (R - L), а li либо больше R, либо меньше L - leni. Чтобы быстро находить количество таких отрезков, будем для каждой длины поддерживать структуру, в которой будем хранить левые концы отрезков, чтобы быстро искать их количество. Это может быть декартово дерево, дерево отрезков, дерево Фенвика (последние два — разреженные).
  3. Эти два отрезка пересекаются, но не являются вложенными. Тогда либо li < L, L ≤ ri < R, либо ri > R, L < li ≤ R. В первом случае объединение отрезков - это [li;R], поэтому R - li = s. Это означает, что li фиксирован, а ri находится в некотором интервале. Для этого для каждого левого конца отрезка будем поддерживать структуру, в которой будем хранить правые концы отрезков, чтобы быстро искать их количество. Во втором случае аналогично — нужно будет завести такую структуру для каждого правого конца.
  4. Отрезки вложенные, длина [li;ri] больше либо равна длине [L;R]. Это означает, что ri - li = s, R - s ≤ li ≤ L. Найдём это количество при помощи структуры из второго пункта.
  5. Отрезки вложенные, длина [li;ri] меньше длины [L;R]. Это может быть только в том случае, когда R - L = s. Требуется посчитать, сколько есть отрезков таких, что L < li < ri < R. Для каждого L будем поддерживать количество отрезков строго внутри [L;L + s]. Отрезок [li;ri] лежит строго внутри отрезка [L;L + s], если ri - s + 1 ≤ L ≤ li - 1. Поэтоэму при добавлении отрезка [li;ri] прибавим единицу на отрезке [ri - s + 1;li - 1], при удалении — вычтем. Это можно делать при помощи дерева отрезков.
Время работы решения: O(n·logn).