시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB80103385240841.944%

문제

준규네 집에는 총 N개의 스위치가 있고 이를 편하게 1번부터 N번까지 차례대로 번호를 매겼다. 그리고 준규의 취미는 이 스위치들을 켜고 끄는 것이다.

준규가 하는 스위치를 갖고 노는 일은 크게 두 가지이다. 하나는 A번부터 B번 사이의 스위치 상태를 반전시키는 것이고 다른 하나는 C번부터 D번 사이의 스위치 중 켜져 있는 상태의 스위치의 개수를 세는 것이다.

하지만 준규가 싫증을 느껴 우리가 이 귀찮은 일을 떠맡게 되었고 프로그래밍을 통해 일을 처리하도록 결정하였다.

입력

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O가 0이면 Si번 스위치부터 Ti번 스위치까지 스위치 상태를 반전시키는 일이고 1이면 Si번 스위치부터 Ti번 스위치까지 중 켜져 있는 상태의 스위치 개수를 묻는 일이다. 단, 초기에는 모든 스위치의 상태는 꺼져있는 상태로 되어있다.

출력

입력에서 켜진 스위치 개수에 대한 답을 한 줄에 하나씩 출력한다.

예제 입력 1

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

예제 출력 1

1
2
W3sicHJvYmxlbV9pZCI6IjEzOTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyYTRcdWM3MDRcdWNlNTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzkwMFx1YWRkY1x1YjEyNCBcdWM5ZDFcdWM1ZDBcdWIyOTQgXHVjZDFkIE5cdWFjMWNcdWM3NTggXHVjMmE0XHVjNzA0XHVjZTU4XHVhYzAwIFx1Yzc4OFx1YWNlMCBcdWM3NzRcdWI5N2MgXHVkM2I4XHVkNTU4XHVhYzhjIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YWU0Y1x1YzljMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHViOTdjIFx1YjllNFx1YWNiY1x1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YzkwMFx1YWRkY1x1Yzc1OCBcdWNkZThcdWJiZjhcdWIyOTQgXHVjNzc0IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YjRlNFx1Yzc0NCBcdWNmMWNcdWFjZTAgXHViMDQ0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTAwXHVhZGRjXHVhYzAwIFx1ZDU1OFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWI5N2MgXHVhYzE2XHVhY2UwIFx1YjE3OFx1YjI5NCBcdWM3N2NcdWM3NDAgXHVkMDZjXHVhYzhjIFx1YjQ1MCBcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuIFx1ZDU1OFx1YjA5OFx1YjI5NCBBXHViYzg4XHViZDgwXHVkMTMwIEJcdWJjODggXHVjMGFjXHVjNzc0XHVjNzU4IFx1YzJhNFx1YzcwNFx1Y2U1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViYzE4XHVjODA0XHVjMmRjXHVkMGE0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCBcdWIyZTRcdWI5NzggXHVkNTU4XHViMDk4XHViMjk0IENcdWJjODhcdWJkODBcdWQxMzAgRFx1YmM4OCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjMmE0XHVjNzA0XHVjZTU4IFx1YzkxMSBcdWNmMWNcdWM4MzggXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YzEzOFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OFx1YzljMFx1YjljYyBcdWM5MDBcdWFkZGNcdWFjMDAgXHVjMmViXHVjOTlkXHVjNzQ0IFx1YjI5MFx1YWVmNCBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjNzc0IFx1YWRjMFx1Y2MyZVx1Yzc0MCBcdWM3N2NcdWM3NDQgXHViNWEwXHViOWUxXHVhYzhjIFx1YjQxOFx1YzVjOFx1YWNlMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3OThcdWJjMGRcdWM3NDQgXHVkMWI1XHVkNTc0IFx1Yzc3Y1x1Yzc0NCBcdWNjOThcdWI5YWNcdWQ1NThcdWIzYzRcdWI4NWQgXHVhY2IwXHVjODE1XHVkNTU4XHVjNjAwXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NTggXHVhYzFjXHVjMjE4IE4oMiAmbGU7IE4gJmxlOyAxMDAsMDAwKVx1YWNmYyBcdWNjOThcdWI5YWNcdWQ1NjAgXHVjNzdjXHVjNzU4IFx1YWMxY1x1YzIxOCBNKDEgJmxlOyBNICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YWMwMSBcdWM5MDRcdWM1ZDAgXHVjYzk4XHViOWFjXHVkNTYwIFx1Yzc3Y1x1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0XHVhYzAwIFx1YjJmNFx1YWNhOFx1YzljNCBcdWMxMzggXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBPLCBTPHN1Yj5pPFwvc3ViPiwgVDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LiBPXHVhYzAwIDBcdWM3NzRcdWJhNzQgUzxzdWI+aTxcL3N1Yj5cdWJjODggXHVjMmE0XHVjNzA0XHVjZTU4XHViZDgwXHVkMTMwIFQ8c3ViPmk8XC9zdWI+XHViYzg4IFx1YzJhNFx1YzcwNFx1Y2U1OFx1YWU0Y1x1YzljMCBcdWMyYTRcdWM3MDRcdWNlNTggXHVjMGMxXHVkMGRjXHViOTdjIFx1YmMxOFx1YzgwNFx1YzJkY1x1ZDBhNFx1YjI5NCBcdWM3N2NcdWM3NzRcdWFjZTAgMVx1Yzc3NFx1YmE3NCBTPHN1Yj5pPFwvc3ViPlx1YmM4OCBcdWMyYTRcdWM3MDRcdWNlNThcdWJkODBcdWQxMzAgVDxzdWI+aTxcL3N1Yj5cdWJjODggXHVjMmE0XHVjNzA0XHVjZTU4XHVhZTRjXHVjOWMwIFx1YzkxMSBcdWNmMWNcdWM4MzggXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1Yzc1OCBcdWMyYTRcdWM3MDRcdWNlNTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YmIzYlx1YjI5NCBcdWM3N2NcdWM3NzRcdWIyZTQuIFx1YjJlOCwgXHVjZDA4XHVhZTMwXHVjNWQwXHViMjk0IFx1YmFhOFx1YjRlMCBcdWMyYTRcdWM3MDRcdWNlNThcdWM3NTggXHVjMGMxXHVkMGRjXHViMjk0IFx1YWViY1x1YzgzOFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWQwZGNcdWI4NWMgXHViNDE4XHVjNWI0XHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzVkMFx1YzExYyBcdWNmMWNcdWM5YzQgXHVjMmE0XHVjNzA0XHVjZTU4IFx1YWMxY1x1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHViMmY1XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMzk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTGlnaHQgU3dpdGNoaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiB0cmllcyB0byBrZWVwIHRoZSBjb3dzIHNoYXJwIGJ5IGxldHRpbmcgdGhlbSBwbGF5IHdpdGggaW50ZWxsZWN0dWFsIHRveXMuIE9uZSBvZiB0aGUgbGFyZ2VyIHRveXMgaXMgdGhlIGxpZ2h0cyBpbiB0aGUgYmFybi4gRWFjaCBvZiB0aGUgTiAoMiAmbHQ7PSBOICZsdDs9IDEwMCwwMDApIGNvdyBzdGFsbHMgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4gaGFzIGEgY29sb3JmdWwgbGlnaHQgYWJvdmUgaXQuPFwvcD5cclxuXHJcbjxwPkF0IHRoZSBiZWdpbm5pbmcgb2YgdGhlIGV2ZW5pbmcsIGFsbCB0aGUgbGlnaHRzIGFyZSBvZmYuIFRoZSBjb3dzIGNvbnRyb2wgdGhlIGxpZ2h0cyB3aXRoIGEgc2V0IG9mIE4gcHVzaGJ1dHRvbiBzd2l0Y2hlcyB0aGF0IHRvZ2dsZSB0aGUgbGlnaHRzOyBwdXNoaW5nIHN3aXRjaCBpIGNoYW5nZXMgdGhlIHN0YXRlIG9mIGxpZ2h0IGkgZnJvbSBvZmYgdG8gb24gb3IgZnJvbSBvbiB0byBvZmYuPFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzIHJlYWQgYW5kIGV4ZWN1dGUgYSBsaXN0IG9mIE0gKDEgJmx0Oz0gTSAmbHQ7PSAxMDAsMDAwKSBvcGVyYXRpb25zIGV4cHJlc3NlZCBhcyBvbmUgb2YgdHdvIGludGVnZXJzICgwICZsdDs9IG9wZXJhdGlvbiAmbHQ7PSAxKS48XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IGtpbmQgb2Ygb3BlcmF0aW9uIChkZW5vdGVkIGJ5IGEgMCBjb21tYW5kKSBpbmNsdWRlcyB0d28gc3Vic2VxdWVudCBpbnRlZ2VycyBTX2kgYW5kIEVfaSAoMSAmbHQ7PSBTX2kgJmx0Oz0gRV9pICZsdDs9IE4pIHRoYXQgaW5kaWNhdGUgYSBzdGFydGluZyBzd2l0Y2ggYW5kIGVuZGluZyBzd2l0Y2guIFRoZXkgZXhlY3V0ZSB0aGUgb3BlcmF0aW9uIGJ5IHB1c2hpbmcgZWFjaCBwdXNoYnV0dG9uIGZyb20gU19pIHRocm91Z2ggRV9pIGluY2x1c2l2ZSBleGFjdGx5IG9uY2UuPFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQga2luZCBvZiBvcGVyYXRpb24gKGRlbm90ZWQgYnkgYSAxIGNvbW1hbmQpIGFza3MgdGhlIGNvd3MgdG8gY291bnQgaG93IG1hbnkgbGlnaHRzIGFyZSBvbiBpbiB0aGUgcmFuZ2UgZ2l2ZW4gYnkgdHdvIGludGVnZXJzIFNfaSBhbmQgRV9pICgxICZsdDs9IFNfaSAmbHQ7PSBFX2kgJmx0Oz0gTikgd2hpY2ggc3BlY2lmeSB0aGUgaW5jbHVzaXZlIHJhbmdlIGluIHdoaWNoIHRoZSBjb3dzIHNob3VsZCBjb3VudCB0aGUgbnVtYmVyIG9mIGxpZ2h0cyB0aGF0IGFyZSBvbi48XC9wPlxyXG5cclxuPHA+SGVscCBGSiBlbnN1cmUgdGhlIGNvd3MgYXJlIGdldHRpbmcgdGhlIGNvcnJlY3QgYW5zd2VyIGJ5IHByb2Nlc3NpbmcgdGhlIGxpc3QgYW5kIHByb2R1Y2luZyB0aGUgcHJvcGVyIGNvdW50cy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOIGFuZCBNPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTSsxOiBFYWNoIGxpbmUgcmVwcmVzZW50cyBhbiBvcGVyYXRpb24gd2l0aCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IG9wZXJhdGlvbiwgU19pLCBhbmQgRV9pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lcyAxLi5udW1iZXIgb2YgcXVlcmllczogRm9yIGVhY2ggb3V0cHV0IHF1ZXJ5LCBwcmludCB0aGUgY291bnQgYXMgYW4gaW50ZWdlciBieSBpdHNlbGYgb24gYSBzaW5nbGUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO November 2008 Contest > Gold 3번

  • 문제를 번역한 사람: author6
  • 데이터를 추가한 사람: doju