Bò Logic

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John có một biểu thức logic gồm $N$ từ khóa ( $1 \leq N < 2 \times 10^{5}$ , $N$ lẻ). Các vị trí lẻ (1, 3, 5, ...) chứa "true" hoặc "false", các vị trí chẵn (2, 4, 6, ...) chứa "and" hoặc "or".

Phép toán "and" có độ ưu tiên cao hơn "or". Biểu thức được tính bằng cách lặp lại: chọn một phép "and" bất kỳ, thay thế ba từ khóa xung quanh (giá trị - and - giá trị) bằng kết quả, cho đến khi chỉ còn một giá trị. Sau đó tính tương tự với "or".

Có $Q$ truy vấn ( $1 \leq Q \leq 2 \times 10^{5}$ ). Mỗi truy vấn cho hai số lẻ $l$ và $r$ ( $1 \leq l \leq r \leq N$ ) và một giá trị mục tiêu "true" hoặc "false". Truy vấn hỏi: liệu có thể xóa đoạn từ khóa $l$ đến $r$ và thay thế bằng đúng một giá trị "true" hoặc "false" sao cho toàn bộ biểu thức có kết quả bằng giá trị mục tiêu?

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $Q$
Dòng 2: $N$ từ khóa cách nhau bởi dấu cách, tạo thành biểu thức logic hợp lệ
$Q$ dòng tiếp theo: Hai số nguyên $l$ , $r$ (đều lẻ) và một chuỗi "true" hoặc "false"

Dữ liệu ra

Một chuỗi độ dài $Q$ , ký tự thứ $i$ là 'Y' nếu truy vấn thứ $i$ khả thi, ngược lại là 'N'.

Ràng buộc

$3 \leq N < 2 \times 10^{5}$ , $N$ lẻ
$1 \leq Q \leq 2 \times 10^{5}$
Test 3-5: $N, Q \leq 100$
Test 6-8: $N, Q \leq 1000$

Ví dụ

Input	Output	Giải thích
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	Biểu thức gốc: false AND true OR true = false OR true = true. Truy vấn 1: thay vị trí 1 bằng "true" hoặc "false", kết quả cần là "false" -- không thể vì "true or true" = true.
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	Biểu thức gồm 7 giá trị và 6 toán tử.

Bình luận

Không có bình luận tại thời điểm này.