전등 스위치

면접 대비

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

요약

N개의 전등 상태를 두고 구간 뒤집기와 구간 켜진 개수 세기 연산 M개를 처리하며, 각 조회 결과를 출력한다.

난이도: 보통10점 중 5점
유형: 세그먼트 트리, 배열, 누적 합
정답자: 아직 제출이 없습니다

문제

농부 존은 소들이 머리를 예리하게 유지하도록 지적인 장난감을 가지고 놀게 한다. 더 큰 장난감 중 하나가 외양간의 전등이다. $1 \ldots N$ ( $2 \le N \le 500$ )으로 편리하게 번호가 매겨진 각 축사 위에는 색색의 전등이 하나씩 달려 있다.

저녁이 시작될 때 모든 전등은 꺼져 있다. 소들은 N개의 누름 스위치로 전등을 제어한다. 스위치 $i$ 를 누르면 전등 $i$ 의 상태가 꺼짐에서 켜짐으로, 또는 켜짐에서 꺼짐으로 뒤바뀐다(토글).

소들은 M( $1 \le M \le 2000$ )개의 연산으로 이루어진 목록을 읽고 실행한다. 각 연산은 맨 앞의 정수 $0$ 또는 $1$ 로 구분된다.

종류 $0$ 연산에는 두 정수 $S$ 와 $E$ ( $1 \le S \le E \le N$ )가 뒤따르며, 시작 스위치와 끝 스위치를 나타낸다. $S$ 번부터 $E$ 번까지의 스위치를 각각 정확히 한 번씩 눌러 실행한다.

종류 $1$ 연산에는 두 정수 $S$ 와 $E$ ( $1 \le S \le E \le N$ )가 뒤따르며, 닫힌 구간을 나타낸다. 소들은 그 구간에서 켜져 있는 전등의 개수를 센다.

목록 전체를 처리하여 종류 $1$ 연산마다 올바른 개수를 출력하라.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $M$ .
둘째 줄부터 $M+1$ 째 줄까지: 각 줄은 하나의 연산을 공백으로 구분된 세 정수, 즉 연산 종류, $S$ , $E$ 로 나타낸다.

출력

종류 $1$ (세기) 연산마다, 켜져 있는 전등의 개수를 한 줄에 정수 하나로 출력한다.

힌트

전등 4개와 명령 5개에 대한 처리 과정 예시:

          전등
              1 2 3 4
  초기:       O O O O   O = 꺼짐, * = 켜짐
  0 1 2  ->   * * O O   전등 1, 2를 토글
  0 2 4  ->   * O * *   전등 2, 3, 4를 토글
  1 2 3  ->   1         구간 2..3에서 켜진 전등 수를 셈
  0 2 4  ->   * * O O   전등 2, 3, 4를 토글
  1 1 4  ->   2         구간 1..4에서 켜진 전등 수를 셈

예제3

예제 1
입력
```
4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4
```
예상 출력
```
1
2
```
예제 2
입력
```
2 2
0 1 2
1 1 2
```
예상 출력
```
2
```
예제 3
입력
```
3 3
0 1 3
0 1 3
1 1 3
```
예상 출력
```
0
```