좋은 수열

시간 제한4초메모리 제한1024 MB

요약

0과 1이 같은 개수로 들어 있는 수열에서 구간을 뒤집을 때마다, 네 원소 연산으로 N을 만들 수 있는지 판단합니다.

문제

$N$ 개의 $0$ 과 $N$ 개의 $1$ 로 이루어진 길이 $2N$ 의 수열 $A$ 가 있다. 이 수열에 다음 작업을 0회 이상 시행하여 $A$ 에 $N$ 이 존재하게 할 수 있으면, 수열 $A$ 를 좋은 수열이라고 한다.

$A$ 에서 연속한 정수 네 개를 골라 차례대로 $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$ 로 이루어진 길이 $2N$ 의 수열 $B$ 가 주어진다. 다음 쿼리를 적용할 때마다 수열 $B$ 가 좋은 수열인지 판별하라.

$l\ r$ : $l \le i \le r$ 인 모든 $i$ 에 대해 $B_i$ 를 반전시킨다. 즉, $1$ 은 $0$ 으로, $0$ 은 $1$ 로 바꾼다. 이때 구간 $[l, r]$ 에서 $1$ 의 개수와 $0$ 의 개수는 같다고 보장된다.

첫 번째 줄에 정수 $N$ 이 주어진다.

두 번째 줄에 $2N$ 개의 정수 $B_1, B_2, \cdots, B_{2N}$ 이 공백으로 구분되어 주어진다.

세 번째 줄에 정수 $Q$ 가 주어진다.

이어지는 $Q$ 개의 줄에는 각각 공백으로 구분된 두 정수 $l$ 과 $r$ 이 주어진다.

$Q+1$ 개의 줄에 답을 출력한다. $i$ 번째 줄에는 주어진 쿼리를 앞에서부터 $i-1$ 개 적용한 뒤 $B$ 가 좋은 수열이면 YES를, 그렇지 않으면 NO를 출력한다.