문제
$N$개의 0ドル$과 $N$개의 1ドル$로 이루어진 길이 2ドルN$의 수열 $A$가 있을 때, 다음과 같은 작업을 0ドル$회 이상 시행하여 $A$에 $N$이 존재하게 할 수 있으면 그런 수열 $A$를 좋은 수열이라고 하자.
- $A$에서 연속한 4ドル$개의 정수를 골라 순서대로 $x,ドル $y,ドル $z,ドル $w$라고 하고, 현재 작업 진행 전 $A$의 크기를 $L$이라 하자.
- $x,ドル $y,ドル $z,ドル $w$을 삭제하고 그 위치에 $w,ドル $x+y$를 삽입한다.
- 즉, $A_1, A_2, \cdots, x, y, z, w, \cdots, A_L$을 $A_1, A_2, \cdots, w, x+y, \cdots, A_L$로 바꾼다.
$N$개의 0ドル$과 $N$개의 1ドル$로 이루어진 길이 2ドルN$의 수열 $B$가 주어진다. 다음과 같은 쿼리를 적용할 때마다 수열 $B$가 좋은 수열인지 판별하여라.
- $l,円 r$: $l\le i\le r$인 모든 $i$에 대해 $B_i$를 반전시킨다. 즉, $B_i=1$이면 0ドル$으로, $B_i=0$이면 1ドル$로 바꾼다. 이때, $[l,r]$ 구간에서 1ドル$의 개수와 0ドル$의 개수는 같다.
출력
$Q+1$개의 줄에 걸쳐 문제의 정답을 출력한다. $i$번째 줄에는 주어진 쿼리를 순서대로 $i-1$번 적용했을 때 $B$가 좋은 수열이면 YES를, 그렇지 않다면 NO를 출력해야 한다.
제한
- 2ドル\le N\le 2\times 10^5$
- $B_i\in\{0,1\}$ $(1\le i\le 2N)$
- $\sum_{i=1}^{2N} B_i=N$
- 0ドル\le Q\le 2\times 10^5$
- 1ドル\le l\le r\le 2N$
서브태스크
| 번호 | 배점 | 제한 | | 1 | 41 | $N \le 5000;$ $Q \le 5000$
|
| 2 | 32 | $l + 1 = r$
|
| 3 | 27 | 추가 제약 조건 없음
|
W3sicHJvYmxlbV9pZCI6IjMxNDQyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjODhiXHVjNzQwIFx1YzIxOFx1YzVmNCIsImRlc2NyaXB0aW9uIjoiPHA+JE4kXHVhYzFjXHVjNzU4ICQwJFx1YWNmYyAkTiRcdWFjMWNcdWM3NTggJDEkXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFlMzhcdWM3NzQgJDJOJFx1Yzc1OCBcdWMyMThcdWM1ZjQgJEEkXHVhYzAwIFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjNzkxXHVjNWM1XHVjNzQ0ICQwJFx1ZDY4YyBcdWM3NzRcdWMwYzEgXHVjMmRjXHVkNTg5XHVkNTU4XHVjNWVjICRBJFx1YzVkMCAkTiRcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVhYzhjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTc0IFx1YWRmOFx1YjdmMCBcdWMyMThcdWM1ZjQgJEEkXHViOTdjIDxzdHJvbmc+XHVjODhiXHVjNzQwIFx1YzIxOFx1YzVmNDxcL3N0cm9uZz5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRBJFx1YzVkMFx1YzExYyBcdWM1ZjBcdWMxOGRcdWQ1NWMgJDQkXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWFjZThcdWI3N2MgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjICR4JCwgJHkkLCAkeiQsICR3JFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWFjZTAsIFx1ZDYwNFx1YzdhYyBcdWM3OTFcdWM1YzUgXHVjOWM0XHVkNTg5IFx1YzgwNCAkQSRcdWM3NTggXHVkMDZjXHVhZTMwXHViOTdjICRMJFx1Yzc3NFx1Yjc3YyBcdWQ1NThcdWM3OTAuPFwvbGk+XHJcblx0PGxpPiR4JCwgJHkkLCAkeiQsICR3JFx1Yzc0NCBcdWMwYWRcdWM4MWNcdWQ1NThcdWFjZTAgXHVhZGY4IFx1YzcwNFx1Y2U1OFx1YzVkMCAkdyQsICR4K3kkXHViOTdjIFx1YzBiZFx1Yzc4NVx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjOTg5LCAkQV8xLCBBXzIsIFxcY2RvdHMsIHgsIHksIHosIHcsIFxcY2RvdHMsIEFfTCRcdWM3NDQgJEFfMSwgQV8yLCBcXGNkb3RzLCB3LCB4K3ksIFxcY2RvdHMsIEFfTCRcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPiROJFx1YWMxY1x1Yzc1OCAkMCRcdWFjZmMgJE4kXHVhYzFjXHVjNzU4ICQxJFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVhZTM4XHVjNzc0ICQyTiRcdWM3NTggXHVjMjE4XHVjNWY0ICRCJFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjZmZjXHViOWFjXHViOTdjIFx1YzgwMVx1YzZhOVx1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjMjE4XHVjNWY0ICRCJFx1YWMwMCA8c3Ryb25nPlx1Yzg4Ylx1Yzc0MCBcdWMyMThcdWM1ZjQ8XC9zdHJvbmc+XHVjNzc4XHVjOWMwIFx1ZDMxMFx1YmNjNFx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4kbFxcLCByJDogJGxcXGxlIGlcXGxlIHIkXHVjNzc4IFx1YmFhOFx1YjRlMCAkaSRcdWM1ZDAgXHViMzAwXHVkNTc0ICRCX2kkXHViOTdjIFx1YmMxOFx1YzgwNFx1YzJkY1x1ZDBhOFx1YjJlNC4gXHVjOTg5LCAkQl9pPTEkXHVjNzc0XHViYTc0ICQwJFx1YzczY1x1Yjg1YywgJEJfaT0wJFx1Yzc3NFx1YmE3NCAkMSRcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LiBcdWM3NzRcdWI1NGMsICRbbCxyXSQgXHVhZDZjXHVhYzA0XHVjNWQwXHVjMTFjICQxJFx1Yzc1OCBcdWFjMWNcdWMyMThcdWM2NDAgJDAkXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWFjMTlcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCAkTiRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCAkMk4kXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCAkQl8xLCBCXzIsIFxcY2RvdHMsIEJfezJOfSRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzgxNVx1YzIxOCAkUSRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgJFEkXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNmZmNcdWI5YWNcdWI0ZTRcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI0NTAgXHVjODE1XHVjMjE4ICRsJFx1YWNmYyAkciRcdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JFErMSRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjZmZjXHViOWFjXHViOTdjIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyAkaS0xJFx1YmM4OCBcdWM4MDFcdWM2YTlcdWQ1ODhcdWM3NDQgXHViNTRjICRCJFx1YWMwMCA8c3Ryb25nPlx1Yzg4Ylx1Yzc0MCBcdWMyMThcdWM1ZjQ8XC9zdHJvbmc+XHVjNzc0XHViYTc0IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5ZRVM8XC9jb2RlPjxcL3NwYW4+XHViOTdjLCBcdWFkZjhcdWI4MDdcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5OTzxcL2NvZGU+PFwvc3Bhbj5cdWI5N2MgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDJcXGxlIE5cXGxlIDJcXHRpbWVzIDEwXjUkPFwvbGk+XHJcblx0PGxpPiRCX2lcXGluXFx7MCwxXFx9JCAkKDFcXGxlIGlcXGxlIDJOKSQ8XC9saT5cclxuXHQ8bGk+JFxcc3VtX3tpPTF9XnsyTn0gQl9pPU4kPFwvbGk+XHJcblx0PGxpPiQwXFxsZSBRXFxsZSAyXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgbFxcbGUgclxcbGUgMk4kPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROIFxcbGUgNTAwMDskICRRIFxcbGUgNTAwMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRsICsgMSA9IHIkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD5cdWNkOTRcdWFjMDAgXHVjODFjXHVjNTdkIFx1Yzg3MFx1YWM3NCBcdWM1YzZcdWM3NGM8XC9wPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMTQ0MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ikdvb2QgU2VxdWVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPkxldCAkQSQgYmUgYSBzZXF1ZW5jZSBvZiBsZW5ndGggJDJOJCBjb25zaXN0aW5nIG9mICROJCB6ZXJvcyBhbmQgJE4kIG9uZXMuIFdlIGNhbGwgc3VjaCBhIHNlcXVlbmNlICRBJCBhIDxzdHJvbmc+Z29vZCBzZXF1ZW5jZTxcL3N0cm9uZz4gaWYgaXQgaXMgcG9zc2libGUgdG8gbWFrZSAkQSQgY29udGFpbiAkTiQgYnkgcGVyZm9ybWluZyB0aGUgZm9sbG93aW5nIG9wZXJhdGlvbiB6ZXJvIG9yIG1vcmUgdGltZXMuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+U2VsZWN0IGZvdXIgY29uc2VjdXRpdmUgaW50ZWdlcnMgaW4gJEEkIGFuZCBkZW5vdGUgdGhlbSBhcyAkeCQsICR5JCwgJHokLCBhbmQgJHckLCBhbmQgbGV0ICRMJCBiZSB0aGUgc2l6ZSBvZiAkQSQgYmVmb3JlIHRoZSBjdXJyZW50IG9wZXJhdGlvbi48XC9saT5cclxuXHQ8bGk+UmVtb3ZlICR4JCwgJHkkLCAkeiQsIGFuZCAkdyQsIGFuZCBpbnNlcnQgJHckLCAkeCt5JCBhdCB0aGVpciBwb3NpdGlvbnMuPFwvbGk+XHJcblx0PGxpPkluIG90aGVyIHdvcmRzLCBjaGFuZ2UgJEFfMSwgQV8yLCBcXGNkb3RzLCB4LCB5LCB6LCB3LCBcXGNkb3RzLCBBX0wkIHRvICRBXzEsIEFfMiwgXFxjZG90cywgdywgeCt5LCBcXGNkb3RzLCBBX0wkLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPkEgc2VxdWVuY2UgJEIkIG9mIGxlbmd0aCAkMk4kIGNvbnNpc3Rpbmcgb2YgJE4kIHplcm9zIGFuZCAkTiQgb25lcyBpcyBnaXZlbi4gRGV0ZXJtaW5lIHdoZXRoZXIgdGhlIHNlcXVlbmNlICRCJCBpcyBhIDxzdHJvbmc+Z29vZCBzZXF1ZW5jZTxcL3N0cm9uZz4gYWZ0ZXIgYXBwbHlpbmcgdGhlIGZvbGxvd2luZyBxdWVyaWVzLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiRsIFxcOyZuYnNwO3IkOiBSZXZlcnNlICRCX2kkIGZvciBhbGwgJGkkIHN1Y2ggdGhhdCAkbFxcbGUgaVxcbGUgciQuIFRoYXQgaXMsIGlmICRCX2k9MSQsIGNoYW5nZSBpdCB0byAkMCQsIGFuZCBpZiAkQl9pPTAkLCBjaGFuZ2UgaXQgdG8gJDEkLiBUaGUgbnVtYmVyIG9mIG9uZXMgYW5kIHplcm9zIGluIHRoZSBpbnRlcnZhbCAkW2wscl0kIHJlbWFpbnMgdGhlIHNhbWUuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgJE4kLjxcL3A+XHJcblxyXG48cD5UaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgJDJOJCBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJEJfMSwgQl8yLCBcXGNkb3RzLCBCX3syTn0kLjxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyBhbiBpbnRlZ2VyICRRJC48XC9wPlxyXG5cclxuPHA+JFEkIGxpbmVzIGZvbGxvdywgZWFjaCBjb250YWluaW5nIHR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJGwkIGFuZCAkciQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UHJpbnQgdGhlIGFuc3dlcnMgdG8gdGhlIHByb2JsZW0gb24gJFErMSQgbGluZXMuIEZvciB0aGUgJGkkLXRoIGxpbmUsIHByaW50IDxzcGFuIHN0eWxlPVwiY29sb3I6I2U3NGMzYztcIj48Y29kZT5ZRVM8XC9jb2RlPjxcL3NwYW4+IGlmIHRoZSBzZXF1ZW5jZSAkQiQgaXMgYSA8c3Ryb25nPmdvb2Qgc2VxdWVuY2U8XC9zdHJvbmc+IGFmdGVyIGFwcGx5aW5nIHRoZSBmaXJzdCAkaS0xJCBxdWVyaWVzIGluIG9yZGVyIGFuZCA8c3BhbiBzdHlsZT1cImNvbG9yOiNlNzRjM2M7XCI+PGNvZGU+Tk88XC9jb2RlPjxcL3NwYW4+IG90aGVyd2lzZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPiQyXFxsZSBOXFxsZSAyXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kQl9pXFxpblxcezAsMVxcfSQgJCgxXFxsZSBpXFxsZSAyTikkPFwvbGk+XHJcblx0PGxpPiRcXHN1bV97aT0xfV57Mk59Jm5ic3A7Ql9pPU4kPFwvbGk+XHJcblx0PGxpPiQwXFxsZSBRXFxsZSAyXFx0aW1lcyAxMF41JDxcL2xpPlxyXG5cdDxsaT4kMVxcbGUgbFxcbGUgclxcbGUgMk4kPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6IjxwPiROIFxcbGUgNTAwMDskJm5ic3A7JFEgXFxsZSA1MDAwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JGwgKyAxID0gciQ8XC9wPlxyXG4iLCJzdWJ0YXNrMyI6IjxwPk5vIGFkZGl0aW9uYWwgY29uc3RyYWludHM8XC9wPlxyXG4ifV0=