Рычаги в подземелье

В игре-подземелье есть коридор из n магических плиток. Каждая плитка либо светится, либо нет. Сначала все плитки не светятся.

Герой дёргает рычаги. Каждый рычаг действует на подряд идущий кусок плиток: все плитки на отрезке меняют состояние на противоположное (светилась → перестаёт, не светилась → загорается).

Посчитайте, сколько плиток будет светиться после всех рычагов.

Формат ввода

В первой строке два целых числа n и m — число плиток и число рычагов. Далее идут m строк по два целых числа l и r (1 ≤ l ≤ r ≤ n) — границы отрезка, на котором плитки переключаются.

Формат вывода

Выведите одно целое число — сколько плиток светится после всех переключений.

Ограничения

• 1 ≤ n ≤ 2000
• 1 ≤ m ≤ 2000
• 1 ≤ l ≤ r ≤ n

Пример

Ввод:

5 3
1 3
2 5
3 3

Вывод:

4

Ключевое наблюдение: состояние плитки после всех рычагов зависит только от того, сколько раз её перевернули. Важно не число, а чётность: если переключений нечётное число — плитка горит, если чётное — нет (потому что два переворота взаимно отменяются).

Чтобы не переворачивать каждый раз весь отрезок (это было бы медленно), используем разностный массив для «включения/выключения действия» на границах. Для операции «перевернуть» удобно хранить не суммы, а XOR по 0/1.

Идея: для каждого рычага [l, r] отметим, что начиная с l чётность переключений меняется, и после r (то есть с r+1) меняется обратно: diff[l] ^= 1; diff[r+1] ^= 1

Дальше идём слева направо и накапливаем текущую чётность cur как префиксный XOR. Если cur == 1, значит текущая плитка перевёрнута нечётное число раз и горит.

План:

• Создать массив diff длины n+2 из нулей.
• Для каждого отрезка [l, r]: сделать XOR-отметки в diff на l и r+1.
• Пройти i = 1..n, поддерживая cur ^= diff[i].
• Если cur == 1, увеличить ответ.

Сложность: O(n + m) по времени и O(n) по памяти.

Частая ошибка: забыть про позицию r+1 (или выйти за границы массива). Поэтому diff делают размером минимум n+2, чтобы r = n тоже обрабатывался корректно.