Heidi and Library (medium) (Codeforces 802B)
Tags: Greedy, data structures

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.


Sample Inputs:
4 100
1 2 2 1

4 1
1 2 2 1

4 2
1 2 3 1

Sample Outputs:
2

3

3

Solution (Python):
import sys
import heapq
from collections import namedtuple
Record = namedtuple('Record', ['index', 'book_id'])
l1 = sys.stdin.readline()
l2 = sys.stdin.readline()
(n, k) = map(int, l1.split(' '))
books = list(map(int, l2.split(' ')))
cost = 0
cache = set()
prev = dict()
next = [n + 1] * n
inactive_ids = set()
book_to_record = dict()

def serve_book(book_id, i):
    cache.add(book_id)
    record = Record(-next[i], book_id)
    heapq.heappush(h, record)
    book_to_record[book_id] = record
h = []
for (i, book_id) in enumerate(books):
    if book_id in prev:
        next[prev[book_id]] = i
    prev[book_id] = i
for (i, book_id) in enumerate(books):
    if book_id in cache:
        previous_record = book_to_record[book_id]
        inactive_ids.add(id(previous_record))
        serve_book(book_id, i)
        continue
    if len(cache) < k:
        cost += 1
        serve_book(book_id, i)
        continue
    while True:
        item = heapq.heappop(h)
        if id(item) in inactive_ids:
            inactive_ids.remove(id(item))
            continue
        cache.remove(item.book_id)
        serve_book(book_id, i)
        cost += 1
        break
print(cost)

Solution (Python):
import heapq
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
pos = {}
Q = []
cnt = 0
for (i, x) in enumerate(a):
    if x not in pos:
        pos[x] = []
    pos[x].append(i)
for (i, x) in enumerate(a):
    if x not in d:
        cnt += 1
        if len(d) == k:
            (pos_, x_) = heapq.heappop(Q)
            del d[x_]
        d[x] = 1
    pos[x].pop(0)
    if len(pos[x]) > 0:
        heapq.heappush(Q, (-pos[x][0], x))
    else:
        heapq.heappush(Q, (-float('inf'), x))
print(cnt)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque, defaultdict
from heapq import heappush, heappop
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
dic = defaultdict(deque)
for (i, a) in enumerate(A):
    dic[a].append(i)
hp = []
S = set()
ans = 0
for (i, a) in enumerate(A):
    dic[a].popleft()
    if a not in S:
        if len(S) < k:
            S.add(a)
            ans += 1
        else:
            idx = heappop(hp)[1]
            S.discard(idx)
            S.add(a)
            ans += 1
    if dic[a]:
        heappush(hp, (-dic[a][0], a))
    else:
        heappush(hp, (float('-inf'), a))
print(ans)