题解 | #[JSOI2010]缓存交换#

package main

import (
	"bufio"
	. "fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

type Cache struct {
	nextIndex, num, pos int
}

func siftUp(heap []*Cache, index int) {
	for index != 0 && heap[index].nextIndex > heap[(index-1)/2].nextIndex {
		heap[index].pos, heap[(index-1)/2].pos = heap[(index-1)/2].pos, heap[index].pos
		heap[index], heap[(index-1)/2] = heap[(index-1)/2], heap[index]
		index = (index - 1) / 2
	}
}

func siftDown(heap []*Cache, last int) {
	curr := 0
	for curr*2+1 < last {
		max := curr
		if heap[curr*2+1].nextIndex > heap[curr].nextIndex {
			max = curr*2 + 1
		}
		if curr*2+2 < last && heap[curr*2+2].nextIndex > heap[max].nextIndex {
			max = curr*2 + 2
		}
		if max == curr {
			break
		}
		heap[curr].pos, heap[max].pos = heap[max].pos, heap[curr].pos
		heap[curr], heap[max] = heap[max], heap[curr]
		curr = max
	}
}

// 获取i后一个位置
func getNextIndex(tmp map[int][]int, num int, i int) int {
	if i == int(^uint(0)>>1) {
		return int(^uint(0) >> 1)
	}
	l, r := 0, len(tmp[num])-1
	for l <= r {
		mid := l + (r-l)/2
		if tmp[num][mid] <= i {
			l = mid + 1
		} else {
			r = mid - 1
		}
	}
	if l == len(tmp[num]) {
		return int(^uint(0) >> 1)
	}
	return tmp[num][l]
}

// https://ac.nowcoder.com/acm/problem/20185
func NC20185(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	line1, _ := in.ReadString('\n')
	line1 = strings.Trim(line1, "\n")
	line2, _ := in.ReadString('\n')
	line2 = strings.Trim(line2, "\n")
	first := strings.Split(line1, " ")
	second := strings.Split(line2, " ")
	n, _ := strconv.Atoi(first[0])
	m, _ := strconv.Atoi(first[1])
	arr := make([]int, n)
	tmp := make(map[int][]int) // 每个元素的索引位置
	for i := 0; i < n; i++ {
		num, _ := strconv.Atoi(second[i])
		arr[i] = num
		if _, ok := tmp[arr[i]]; ok {
			tmp[arr[i]] = append(tmp[arr[i]], i)
		} else {
			tmp[arr[i]] = []int{i}
		}
	}
	ans := 0
	heap, lastIndex := make([]*Cache, m), 0 // 大根堆
	currHeapCache := make(map[int]*Cache)   // 缓存 （O1） 复杂度 这里不做缓存AC不掉

	for i := 0; i < n; i++ {
		// 如果已经在缓存中存在
		if c, ok := currHeapCache[i]; ok {
			delete(currHeapCache, c.nextIndex)
			c.nextIndex = getNextIndex(tmp, arr[i], i) // 更新下一个位置
			currHeapCache[c.nextIndex] = c
			siftUp(heap, c.pos)
		} else {
			if lastIndex == m { // 淘汰堆顶
				delete(currHeapCache, heap[0].nextIndex)
				heap[0] = &Cache{getNextIndex(tmp, arr[i], i), arr[i], 0}
				currHeapCache[heap[0].nextIndex] = heap[0]
				siftDown(heap, lastIndex)
			} else {
				// 堆还没满
				heap[lastIndex] = &Cache{getNextIndex(tmp, arr[i], i), arr[i], lastIndex}
				currHeapCache[heap[lastIndex].nextIndex] = heap[lastIndex]
				siftUp(heap, lastIndex)
				lastIndex++
			}
			ans++
		}
	}
	Fprintln(out, ans)
}

func main() {
	NC20185(os.Stdin, os.Stdout)
}