Xóa điểm bất động
Đề bài
Mô tả
Cho dãy gồm số nguyên dương. Trong một thao tác, bạn được chọn một chỉ số thỏa mãn và xóa phần tử khỏi dãy; sau khi xóa, các phần tử phía sau dồn lên (chỉ số của chúng giảm đi ).
Trọng số của dãy là số phần tử lớn nhất có thể xóa được bằng các thao tác trên.
Có truy vấn độc lập, mỗi truy vấn cho hai số : thay phần tử đầu tiên và phần tử cuối cùng của dãy bằng (khiến chúng không bao giờ xóa được). Hãy cho biết trọng số của dãy thu được. Mỗi truy vấn được thực hiện trên dãy ban đầu.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ hai chứa số nguyên .
- dòng tiếp theo, mỗi dòng chứa hai số nguyên và mô tả một truy vấn.
Dữ liệu ra
In ra dòng, dòng thứ là đáp án của truy vấn thứ .
Ràng buộc
- và
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 13 5 2 2 3 9 5 4 6 5 7 8 3 11 13 3 1 0 0 2 4 5 0 0 12 |
5 11 6 1 0 |
Truy vấn đầu tiên: dãy thành [×, ×, ×, 9, 5, 4, 6, 5, 7, 8, 3, 11, ×]. Lần lượt xóa các phần tử 5, 11, 6, 8, 7 (mỗi lần xóa, giá trị đúng bằng vị trí hiện tại), được 5 phần tử và không thể làm tốt hơn. |
| 5 2 1 4 1 2 4 0 0 1 0 |
2 0 |
Truy vấn thứ nhất: xóa , dãy thành [4, 1, 2, 4] và phần tử cuối nằm ở vị trí 4 nên xóa được, tổng cộng 2. Truy vấn thứ hai: không có phần tử nào xóa được. |
Bình luận