Ленивые лесорубы

Заметим, что набор отрезков подходит, то есть уменьшает высоту на каждом единичном отрезке на целое число метров, если каждый единичный отрезок покрывается четным числом отрезков. Для этого, необходимо и достаточно, чтобы каждая точка встречалась как конец отрезка чётное число раз. Докажем это:

Теперь мы свели задачу к такой: дан массив пар чисел, посчитать количество отрезков массива, на которых каждое число встречается четное число раз. Заменим все числа таким образом, чтобы их значения стали целыми числами от $$$0$$$ до $$$k - 1$$$, где $$$k$$$ — количество различных чисел. Будем идти слева направо и для текущего префикса поддерживать двоичный вектор $$$pref$$$ длины $$$k$$$, $$$pref_i$$$ равно количеству раз, которое встречается число $$$i$$$ на текущем префиксе, по модулю $$$2$$$. Все значения анологичного вектора, построенного для отрезка, являющегося ответом, равны $$$0$$$. Вектор для отрезка $$$[l, r]$$$ равен поэлементному xor-у векторов для префикса $$$r$$$ и префикса $$$l - 1$$$. Поэтому, для каждого префикса нужно прибавить к ответу количество предыдущих префиксов, в которых вектор совпадал с текущим. Для этого можно вместе с вектором поддерживать хеш вектора. При добавлении очередной пары, хеш пересчитывается за $$$O(1)$$$. Количество префиксов с каждым значением хеша можно хранить в хеш таблице.