trang chủ / đề bài / icpc26_mn_e

Bộ nhớ động

Đề bài

Mô tả

Một hệ thống bộ nhớ gồm 2k ô, đánh số từ 0 đến 2k−1. Mỗi ô lưu một bit, 0 hoặc 1.

Hệ thống hỗ trợ thao tác STORE(i, j, x), trong đó 0≤i≤k, 0≤j<2k−i và x∈{0,1}. Thao tác này gán giá trị x cho mọi ô trong đoạn [j·2i,(j+1)·2i−1] (tính cả hai đầu). Chi phí của nó là wi, không phụ thuộc vào j và x. 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 T gồm 2k bit. Ban đầu mọi bit của T đều bằng 0. Có q truy vấn, mỗi truy vấn cho bởi hai số nguyên L và R. Truy vấn đảo mọi bit của T trong đoạn [L,R] (tính cả hai đầu):

T[p]←T[p]⊕1(L≤p≤R),

trong đó ⊕ là phép XOR theo bit. Đoạn [L,R] 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 2 và không cần thỏa ràng buộc căn lề nào.

Các truy vấn thay đổi T 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 0 thành cấu hình T 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 0 khi mọi bit của T bằng 0.

Dữ liệu vào

  • Dòng đầu tiên chứa hai số nguyên k và q (1≤k≤30, 1≤q≤105).
  • Dòng thứ hai chứa k+1 số nguyên w0,w1,…,wk (1≤wi≤106), trong đó wi là chi phí của một thao tác STORE trên đoạn độ dài 2i.
  • Mỗi dòng trong q dòng tiếp theo chứa hai số nguyên L và R (0≤L≤R<2k), mô tả một truy vấn đảo các bit của T tại mọi vị trí từ L đến R.

Dữ liệu ra

In ra q dòng. Dòng thứ t chứa một số nguyên: tổng chi phí nhỏ nhất để thu được cấu hình đích T sau truy vấn thứ t.

Đáp án có thể vượt quá 1012, vượt phạm vi kiểu số nguyên 32 bit. Hãy dùng kiểu số nguyên 64 bit.

Ràng buộc

  • 1≤k≤30, 1≤q≤105.
  • 1≤wi≤106.
  • 0≤L≤R<2k.

Ví dụ

Input Output Giải thích
3 3
1 1 1 1
0 7
2 3
0 1
1
2
1
Có 23=8 ô nhớ và mọi thao tác STORE có chi phí 1. Sau truy vấn 1, T=[1,1,1,1,1,1,1,1]: chỉ cần STORE(3, 0, 1), chi phí 1. Sau truy vấn 2, T=[1,1,0,0,1,1,1,1]: thực hiện STORE(3, 0, 1) rồi STORE(1, 1, 0), chi phí 2. Sau truy vấn 3, T=[0,0,0,0,1,1,1,1]: chỉ cần STORE(2, 1, 1), chi phí 1.
2 4
2 5 1
0 3
2 2
0 3
1 1
1
3
2
4
w0=2, w1=5, w2=1. Sau truy vấn 2, T=[1,1,0,1]: thực hiện STORE(2, 0, 1) rồi STORE(0, 2, 0), chi phí 1+2=3. Nếu không được ghi đè ô đã ghi trước đó thì cách rẻ nhất là gán lần lượt các ô 0, 1, 3, chi phí 6. Sau truy vấn 3, T=[0,0,1,0], chi phí 2; sau truy vấn 4, T=[0,1,1,0], gán riêng hai ô 1 và 2, chi phí 4.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0