Truy vấn dễ
Đề bài
Mô tả
Cho mảng gồm số nguyên .
Bạn cần trả lời truy vấn. Mỗi truy vấn gồm số nguyên (, ):
- Xét mảng con của từ chỉ số đến chỉ số : .
- Gọi là mảng thu được khi sắp xếp mảng con trên theo thứ tự không giảm. Lưu ý rằng ta không thay đổi thứ tự các phần tử của mảng , tức là mảng giữ nguyên sau mỗi truy vấn.
- Gọi là tập các giá trị xuất hiện ít nhất lần trong .
- Gọi là phép OR theo bit của tất cả các phần tử trong (OR của tập rỗng bằng ).
- Kết quả của truy vấn là .
Ví dụ, với , xét truy vấn , , , :
- .
- .
- .
- .
- .
- .
- .
- Kết quả của truy vấn là .
Dữ liệu vào
Dòng đầu tiên chứa số nguyên () là số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ gồm:
- Dòng đầu tiên chứa hai số nguyên và ().
- Dòng thứ hai chứa đúng số nguyên là mảng ().
- dòng tiếp theo, mỗi dòng chứa đúng số nguyên (, ).
Tổng của tất cả các bộ dữ liệu không vượt quá . Tổng của tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra đúng dòng, dòng thứ chứa đúng một số nguyên là kết quả của truy vấn thứ .
Ràng buộc
- , tổng và tổng không vượt quá
- ,
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 11 3 123 3 2 2 7 2 1 5 5 7 456 2 10 2 8 1 1 1 1 1 4 1 3 |
16 123 5 |
Truy vấn thứ nhất được giải thích ở trên. Truy vấn thứ hai: , kết quả . Truy vấn thứ ba: , , kết quả . |
| 1 6 3 4 1 4 2 4 1 1 6 1 6 1 6 2 5 2 5 2 3 |
16 11 6 |
Ví dụ bổ sung (không có trong đề gốc). Truy vấn thứ nhất: , kết quả . Truy vấn thứ hai: , kết quả . Truy vấn thứ ba: , , kết quả . |
Bình luận