B. Heidi and Library (medium)

Codeforces

IDCF802B

Time10000ms

Memory256MB

Difficulty—

data structuresgreedy

English · Original

Chinese · Translation

Formal · Original

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. ## Input Same as the easy version, but the limits have changed: 1 ≤ _n_, _k_ ≤ 400 000. ## Output Same as the easy version. [samples]

尽管如今人类阅读纸质书籍越来越少，但土拨鼠的阅读量却激增。Heidi 扩展了图书馆，现在需要处理更长的请求序列。与简单版本相同，但限制已更改：#cf_span[1 ≤ n, k ≤ 400 000]。与简单版本相同。 ## Input 与简单版本相同，但限制已更改：#cf_span[1 ≤ n, k ≤ 400 000]。 ## Output 与简单版本相同。 [samples]

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. Define $ 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). Objective: Compute the minimum number of insertions required to serve all $ n $ requests, assuming optimal offline eviction.

Samples

Input #1

4 100
1 2 2 1

Output #1

Input #2

4 1
1 2 2 1

Output #2

Input #3

4 2
1 2 3 1

Output #3

API Response (JSON)

{
  "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 th...",
      "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 ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments