Bóng bàn (bản dễ)
Đề bài
Mô tả
Bạn quản lý một tập các đoạn thẳng, ban đầu tập này rỗng. Các đoạn được đánh số theo thứ tự chúng được thêm vào: đoạn thêm vào đầu tiên có số hiệu , đoạn tiếp theo có số hiệu , v.v.
Từ đoạn trong tập, ta có thể đi một bước sang đoạn cũng thuộc tập khi và chỉ khi hoặc , tức là ít nhất một trong hai đầu mút của đoạn nguồn nằm hoàn toàn bên trong đoạn đích.
Tồn tại đường đi từ đoạn tới đoạn nếu có một dãy các bước đi liên tiếp bắt đầu từ và kết thúc tại . Chú ý quan hệ này có hướng: đi được từ sang không có nghĩa là đi được theo chiều ngược lại.
Hãy xử lý truy vấn thuộc hai loại:
1 x y(với ) — thêm đoạn vào tập. Độ dài của đoạn mới được đảm bảo lớn hơn hẳn độ dài của mọi đoạn đã có trước đó.2 a b(với ) — trả lời: có đường đi từ đoạn số hiệu tới đoạn số hiệu hay không, xét trên tập các đoạn tại thời điểm truy vấn.
Dữ liệu vào
- Dòng đầu chứa số nguyên — số truy vấn.
- dòng tiếp theo, mỗi dòng chứa một truy vấn theo định dạng mô tả ở trên.
Dữ liệu ra
Với mỗi truy vấn loại 2, in ra YES hoặc NO trên một dòng riêng.
Ràng buộc
- Mọi số trong dữ liệu vào là số nguyên có giá trị tuyệt đối không vượt quá
- Dữ liệu vào được đảm bảo hợp lệ: với truy vấn loại 2 thì và cả hai đoạn số hiệu , đều đã được thêm vào trước đó
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 1 1 5 1 5 11 2 1 2 1 2 9 2 1 2 |
NO YES |
Với hai đoạn và : không có bước đi nào giữa chúng vì đầu mút chung không nằm hoàn toàn bên trong đoạn kia, nên đáp án là NO. Sau khi thêm : từ đi được sang vì , rồi từ đi được sang vì , nên đáp án là YES. |
| 9 1 1 4 1 5 20 1 11 30 1 29 60 1 59 100 1 100 200 2 1 5 2 1 6 2 2 5 |
NO NO YES |
Đoạn rời hẳn mọi đoạn khác nên không đi đâu được, hai truy vấn đầu cho NO. Từ đoạn có nên sang được đoạn ; từ đó nên sang được đoạn ; cuối cùng nên tới được đoạn , đáp án YES. |
Bình luận