DRASHOOT - Dragon Shooting
Giới hạn- Thời gian: 0.3s
- 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 một cột N số thẳng đứng, phần tử dưới cùng ở độ cao 1, phần tử trên cùng ở độ cao N. Có 2 loại truy vấn
_ S x: xóa đi phần tử ở độ cao x, sau đó các phần tử phía trên sẽ dồn xuống và tất nhiên các phần tử bị dồn xuống sẽ giảm một đơn vị độ cao (x không vượt quá số phần tử hiện tại của dãy số)
_ Q x y: trong các phần tử thuộc các nhóm từ x đến y, hãy tìm phần tử có giá trị lớn nhất (x<=y)
Nhóm được định nghĩa như sau: Tại một thời điểm nào đó, ta nói phần tử ở độ cao i thuộc nhóm x nếu độ cao phần tử đó đã giảm x đơn vị so với độ cao ban đầu
Input
_ Dòng đầu chứa số N là số phần tử ban đầu của dãy số (1<=N<=100000)
_ N dòng sau chứa N số nguyên là giá trị của các phần tử (0<=A_i<=10^9)
_ Dòng tiếp theo chứa số M là số truy vấn (1<=M<=100000)
_ M dòng tiếp theo chứa một trong hai loại truy vấn như định dạng trên. Chú ý là với truy vấn x..y thì x và y có thể âm hoặc dương
Output
_ In ra kết quả cho các truy vấn Q (mỗi số in trên một dòng). Nếu trong dãy số không tồn tại phần tử nào thuộc nhóm từ x đến y thì in ra “NONE”
Example
Input: 5 1 2 3 4 5 5 Q 0 0 S 3 Q 0 0 S 3 Q 2 2 Output: 5 2 5
Input: 8 1 5 7 2 6 4 5 3 10 S 5 Q 0 1 Q 0 1 Q 2 2 S 5 Q 1 2 Q 1 1 Q 2 3 S 4 Q 1 1 Output: 7 7 NONE 5 NONE 5 NONE
Giải thích: ban đầu các phần tử theo thứ tự từ dưới lên trên mang giá trị 1 2 3 4 5. Ban đầu các số chưa bị thay đổi vị trí nên tất cả đều thuộc nhóm 0. Q 0 0 => 5 Sau khi bắn ptử thứ 3 dãy còn lại là 1 2 4 5 với (1 2) thuộc nhóm 0 và (4 5) thuộc nhóm 1. Khi đó thực hiện Q 0 0 => 2 Tiếp tục bắn ptử thứ 3, dãy còn lại 1 2 5 với (1 2) thuộc nhóm 0 và (5) thuộc nhóm 2 nên Q 2 2 => 5
- Người up: duyhung123abc
- Nguồn bài: duyhung123abc