Khả năng tới được qua AND

Điểm: 8,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++

Cho mảng số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Ta nói $y$ tới được từ $x$ nếu $x < y$ và tồn tại dãy chỉ số $x = p_{1} < p_{2} < \dots < p_{k} = y$ sao cho $a_{p_{i}} & a_{p_{i + 1}} > 0$ với mọi $1 \leq i < k$ . Ở đây $&$ là phép AND bit.

Cho $q$ truy vấn, mỗi truy vấn gồm cặp chỉ số $(x, y)$ . Với mỗi truy vấn, hãy kiểm tra xem $y$ có tới được từ $x$ hay không.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $q$ $(2 \leq n \leq 3 \cdot 10^{5}, 1 \leq q \leq 3 \cdot 10^{5})$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ $(0 \leq a_{i} \leq 3 \cdot 10^{5})$ .
$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ $(1 \leq x < y \leq n)$ .

Dữ liệu ra

In ra $q$ dòng. Trên dòng thứ $i$ , in Shi nếu $y_{i}$ tới được từ $x_{i}$ , ngược lại in Fou.

Ràng buộc

$2 \leq n \leq 3 \cdot 10^{5}$
$1 \leq q \leq 3 \cdot 10^{5}$
$0 \leq a_{i} \leq 3 \cdot 10^{5}$
$1 \leq x_{i} < y_{i} \leq n$

Ví dụ

Input	Output	Giải thích
5 3 1 3 0 2 1 1 3 2 4 1 4	Fou Shi Shi	$a_{3} = 0$ nên không thể tới $3$ vì AND với $0$ luôn bằng $0$ . Có $a_{2} & a_{4} = 3 & 2 = 2 > 0$ , nên $4$ tới được từ $2$ . Từ $1$ tới $4$ dùng dãy $p = [1, 2, 4]$ vì $a_{1} & a_{2} = 1$ và $a_{2} & a_{4} = 2$ .
2 1 300000 300000 1 2	Shi	$a_{1} & a_{2} = 300000 > 0$ , nên $2$ tới được trực tiếp từ $1$ .

Bình luận

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