ROPER - Biến đổi hoán vị
Giới hạn- Thời gian: 0.09s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho 1 dãy số có N phần tử. Có 2 thao tác được phép sử dụng để biến đổi dãy số:
Đổi chỗ 2 phần tử đầu tiên của dãy
Cho 1 hoán vị P, di chuyển phần tử thứ nhất đến vị trí P[1], phần tử thứ 2 đến vị trí P[2],..
Các thao tác được phép thực hiện với số lần không hạn chế và theo bất kì thứ tự nào.
Cho M truy vấn “u v”, bạn cần trả lời xem có thể có thể biến đổi hoán vị ban đầu sao cho phần tử thứ u có thể di chuyển đến vị tri v hay không?
Input:
Dòng 1: 2 số N và M (0 < N,M <= 10^5)
Dòng 2: hoán vị P (1 hoán vị của {1,2,…,N})
Dòng 3..M + 2: mỗi dòng chứa 2 số nguyên u và v (0 < u,v <= N)
Output:
Với mỗi truy vấn, đưa ra “Yes” hoặc “No” tương ứng
Example
Input 4 2 1 4 3 2 4 1 3 4 Output Yes No
- Người up: voj
- Nguồn bài: Russian Code Cup 2012