{"problem":{"name":"B. Heidi and Library (medium)","description":{"content":"Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF802B"},"statements":[{"statement_type":"Markdown","content":"Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.\n\n## Input\n\nSame as the easy version, but the limits have changed: 1 ≤ _n_, _k_ ≤ 400 000.\n\n## Output\n\nSame as the easy version.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"尽管如今人类阅读纸质书籍越来越少，但土拨鼠的阅读量却激增。Heidi 扩展了图书馆，现在需要处理更长的请求序列。\n\n与简单版本相同，但限制已更改：#cf_span[1 ≤ n, k ≤ 400 000]。\n\n与简单版本相同。\n\n## Input\n\n与简单版本相同，但限制已更改：#cf_span[1 ≤ n, k ≤ 400 000]。\n\n## Output\n\n与简单版本相同。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Given a sequence of $ n $ book requests $ a_1, a_2, \\dots, a_n $, where each $ a_i \\in \\{1, 2, \\dots, k\\} $, and a shelf of capacity $ k $, initially empty. At each step $ i $, if book $ a_i $ is not on the shelf, it must be added. If the shelf is full, one book must be removed. The goal is to minimize the total number of shelf operations (insertions and removals) using an optimal offline eviction strategy.\n\nDefine $ f(i, S) $ as the minimum number of operations to process the first $ i $ requests with current shelf state $ S \\subseteq \\{1, 2, \\dots, k\\} $, $ |S| \\leq k $. The optimal strategy is the Belady’s algorithm: evict the book whose next request is farthest in the future (or never again).\n\nObjective: Compute the minimum number of insertions required to serve all $ n $ requests, assuming optimal offline eviction.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF802B","tags":["data structures","greedy"],"sample_group":[["4 100\n1 2 2 1","2"],["4 1\n1 2 2 1","3"],["4 2\n1 2 3 1","3"]],"created_at":"2026-03-03 11:00:39"}}