스위치

시간 제한1초메모리 제한128 MB

요약

스위치 N개에 대해 구간 뒤집기와 구간 켜진 개수 질의를 M번 처리하는 문제로, 지연 전파가 있는 세그먼트 트리로 해결합니다.

문제

준규의 집에는 1번부터 N번까지 번호가 붙은 스위치 N개가 있다. 처음에는 모든 스위치가 꺼져 있다.

처리해야 할 작업은 두 종류이다.

0 S_i T_i: S_i번 스위치부터 T_i번 스위치까지의 상태를 모두 반전한다. 켜져 있던 스위치는 꺼지고, 꺼져 있던 스위치는 켜진다.
1 S_i T_i: S_i번 스위치부터 T_i번 스위치까지 중 켜져 있는 스위치의 개수를 구한다.

주어진 작업을 순서대로 처리하라.

첫 줄에 스위치의 개수 N (2 ≤ N ≤ 100,000)과 처리할 작업의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개의 줄에는 각 작업을 나타내는 세 정수 O, S_i, T_i가 주어진다. O가 0이면 구간의 스위치 상태를 반전하는 작업이고, O가 1이면 구간에서 켜져 있는 스위치의 개수를 묻는 작업이다.

O가 1인 작업마다, 해당 구간에서 켜져 있는 스위치의 개수를 한 줄에 하나씩 출력한다.