RiseOJ – 논리 음머

설명

농부 존은 $$N$$ 개의 키워드로 이루어진 불리언 식을 가지고 있다 ( $1 \leq N < 2 \cdot 10^5$ , $$N$$ 은 홀수). 홀수 번째 위치에는 $\texttt{true}$ 또는 $\texttt{false}$ 만 나타나고, 짝수 번째 위치에는 $\texttt{and}$ 와 $\texttt{or}$ 만 나타난다.

$x\text{ OPERATOR }y$ 형태의 구는, $$x$$ 와 $$y$$ 가 각각 $\texttt{true}$ 또는 $\texttt{false}$ 이고 $\text{OPERATOR}$ 가 $\texttt{and}$ 또는 $\texttt{or}$ 일 때, 다음과 같이 평가된다.

$x\texttt{ and }y$ : $$x$$ 와 $$y$$ 가 모두 true이면 true, 그렇지 않으면 false로 평가된다.
$x\texttt{ or }y$ : $$x$$ 와 $$y$$ 중 하나라도 true이면 true, 그렇지 않으면 false로 평가된다.

식을 평가할 때 농부 존은 음머 언어(Moo Language)의 연산자 우선순위를 고려해야 한다. C++과 마찬가지로 $\texttt{and}$ 가 $\texttt{or}$ 보다 우선순위가 높다. 구체적으로, 식이 키워드 하나만 남을 때까지 다음 단계를 반복하여 평가한다.

식에 $\texttt{and}$ 가 있으면, 그중 아무거나 하나를 골라 그 주변의 구를 평가 결과로 치환한다.
그렇지 않으면 식에는 $\texttt{or}$ 가 있다. 그중 아무거나 하나를 골라 그 주변의 구를 평가 결과로 치환한다.

어떤 단계에서 여러 구를 평가할 수 있더라도 어느 것을 선택하든 상관없으며, 식은 항상 같은 값으로 평가됨을 증명할 수 있다.

농부 존에게는 $$Q$$ $(1 \leq Q \leq 2 \cdot 10^5)$ 개의 쿼리가 있다. 각 쿼리에서 그는 두 정수 $$l$$ 과 $$r$$ ( $1 \leq l \leq r \leq N$ , $$l$$ 과 $$r$$ 은 모두 홀수)을 주고, 키워드 $$l$$ 부터 키워드 $$r$$ 까지의 구간을 삭제한다. 그 대신 방금 삭제한 구간을 단 하나의 $\texttt{true}$ 또는 $\texttt{false}$ 로 대체하여 전체 식이 원하는 불리언 값으로 평가되게 하고 싶다. 이것이 가능한지 농부 존이 판단하도록 도와주자!

문제 제공: Chongtian Ma

제약

배점

입력 3-5: $N,Q\le 10^2$
입력 6-8: $N,Q\le 10^3$
입력 9-26: 추가 제약 없음.

문제 제공: Chongtian Ma

입력 형식

첫째 줄에 $$N$$ 과 $$Q$$ 가 주어진다.

다음 줄에 올바른 불리언 식을 이루는 $$N$$ 개의 문자열이 주어진다.

다음 $$Q$$ 개의 줄에는 두 정수 $$l$$ 과 $$r$$ , 그리고 전체 식이 true로 평가되기를 원하는지 false로 평가되기를 원하는지를 나타내는 문자열 $\texttt{true}$ 또는 $\texttt{false}$ 가 주어진다.

출력 형식

길이 $$Q$$ 의 문자열을 출력한다. $$i$$ 번째 문자는 $$i$$ 번째 쿼리가 가능하면 Y, 그렇지 않으면 N이다.

예제 1

입력

5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

출력

NYYYNYY

설명

Let's analyze the first query:

If we were to replace delete the segment $$[1, 1]$$ and replace it with
$\texttt{true}$ , then the whole statement becomes:

true and true or true

We evaluate the $\texttt{and}$ keyword from at position $$2$$ and obtain

true or true

Since we have no $\texttt{and}$ keywords left, we have to evaluate the
$\texttt{or}$ keyword. After evaluation, all that is left is

true

It can be shown that if we were to replace the segment with $\texttt{false}$ ,
the statement will still evaluate to $\texttt{true}$ , so we output N since the
statement cannot possibly evaluate to $\texttt{false}$ .

For the second query, we can replace the segment $$[1, 3]$$ with $\texttt{true}$
and the whole statement will evaluate to $\texttt{true}$ , so we output Y.

For the third query, since $$[1, 5]$$ is the whole statement, we can replace it
with anything, so we output Y.

예제 2

입력

13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

출력

YNYY

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2023-2024 > US Open > Bronze

올림피아드 > USACO > 2023-2024 > US Open > Bronze

태그

JudgeUSACO

논리 음머

평가 및 의견

풀이 제출