Bộ nhớ động
Đề bài
Mô tả
Một hệ thống bộ nhớ gồm ô, đánh số từ đến . Mỗi ô lưu một bit, hoặc .
Hệ thống hỗ trợ thao tác STORE(i, j, x), trong đó , và . Thao tác này gán giá trị cho mọi ô trong đoạn (tính cả hai đầu). Chi phí của nó là , không phụ thuộc vào và . Các thao tác được thực hiện lần lượt, nên một thao tác sau có thể ghi đè các giá trị do thao tác trước ghi.
Cho thêm một cấu hình đích gồm bit. Ban đầu mọi bit của đều bằng . Có truy vấn, mỗi truy vấn cho bởi hai số nguyên và . Truy vấn đảo mọi bit của trong đoạn (tính cả hai đầu):
trong đó là phép XOR theo bit. Đoạn có thể là đoạn liên tiếp bất kỳ: khác với đoạn của thao tác STORE, độ dài của nó không nhất thiết là lũy thừa của và không cần thỏa ràng buộc căn lề nào.
Các truy vấn thay đổi một cách tích lũy. Sau mỗi truy vấn, hãy tìm tổng chi phí nhỏ nhất của một dãy thao tác STORE biến bộ nhớ có mọi ô bằng thành cấu hình hiện tại. Các thao tác đã xét cho các truy vấn trước không có vai trò gì. Dãy thao tác có thể rỗng, nên đáp án bằng khi mọi bit của bằng .
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 (), trong đó là chi phí của một thao tác
STOREtrên đoạn độ dài . - Mỗi dòng trong dòng tiếp theo chứa hai số nguyên và (), mô tả một truy vấn đảo các bit của tại mọi vị trí từ đến .
Dữ liệu ra
In ra dòng. Dòng thứ chứa một số nguyên: tổng chi phí nhỏ nhất để thu được cấu hình đích sau truy vấn thứ .
Đáp án có thể vượt quá , vượt phạm vi kiểu số nguyên bit. Hãy dùng kiểu số nguyên bit.
Ràng buộc
- , .
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 1 1 1 0 7 2 3 0 1 |
1 2 1 |
Có ô nhớ và mọi thao tác STORE có chi phí . Sau truy vấn 1, : chỉ cần STORE(3, 0, 1), chi phí . Sau truy vấn 2, : thực hiện STORE(3, 0, 1) rồi STORE(1, 1, 0), chi phí . Sau truy vấn 3, : chỉ cần STORE(2, 1, 1), chi phí . |
| 2 4 2 5 1 0 3 2 2 0 3 1 1 |
1 3 2 4 |
, , . Sau truy vấn 2, : thực hiện STORE(2, 0, 1) rồi STORE(0, 2, 0), chi phí . Nếu không được ghi đè ô đã ghi trước đó thì cách rẻ nhất là gán lần lượt các ô , , , chi phí . Sau truy vấn 3, , chi phí ; sau truy vấn 4, , gán riêng hai ô và , chi phí . |
Bình luận