题解 | #Running Median#

package main

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

func siftDown(h []int, bigHeap bool, end int) {
	curr := 0
	if bigHeap {
		for curr < end {
			max := curr
			l, r := 2*curr+1, 2*curr+2
			if l < end {
				if h[l] > h[max] {
					max = l
				}
				if r < end && h[r] > h[max] {
					max = r
				}
			}
			if max == curr {
				break
			}
			h[curr], h[max] = h[max], h[curr]
			curr = max
		}
	} else {
		for curr < end {
			min := curr
			l, r := 2*curr+1, 2*curr+2
			if l < end {
				if h[l] < h[min] {
					min = l
				}
				if r < end && h[r] < h[min] {
					min = r
				}
			}
			if min == curr {
				break
			}
			h[curr], h[min] = h[min], h[curr]
			curr = min
		}
	}
}

func siftUp(h []int, bigHeap bool, last int) {
	i := last
	if bigHeap {
		for i > 0 && h[i] > h[(i-1)/2] {
			h[i], h[(i-1)/2] = h[(i-1)/2], h[i]
			i = (i - 1) / 2
		}
	} else {
		for i > 0 && h[i] < h[(i-1)/2] {
			h[i], h[(i-1)/2] = h[(i-1)/2], h[i]
			i = (i - 1) / 2
		}
	}
}

// https://ac.nowcoder.com/acm/problem/16663
func NC50940(_r io.Reader, _w io.Writer) {
	in, out := bufio.NewReader(_r), bufio.NewWriter(_w)
	defer out.Flush()
	var P int
	for Fscan(in, &P); P > 0; P-- {
		var id, cnt int
		Fscan(in, &id, &cnt)

		var printCnt = 1
		// 小根堆存大的一半   大根堆存小的那一部分
		h1, h2 := make([]int, cnt/2+1), make([]int, cnt/2+1)
		h1Last, h2Last := 0, 0

		Fprintln(out, id, cnt/2+1)
		for i := 1; i <= cnt; i++ {
			var e int
			Fscan(in, &e)
			// 插入策略
			if h1Last == 0 {
				h1[h1Last] = e
				h1Last++
			} else {
				if e <= h1[0] {
					h2[h2Last] = e
					siftUp(h2, true, h2Last)
					h2Last++
				} else {
					h1[h1Last] = e
					siftUp(h1, false, h1Last)
					h1Last++
				}
			}
			var tmp int
			// 平衡调整
			if h1Last-h2Last > 1 {
				tmp = h1[0]
				h1[0] = h1[h1Last-1]
				siftDown(h1, false, h1Last-1)
				h1Last--
				h2[h2Last] = tmp
				siftUp(h2, true, h2Last)
				h2Last++
			} else if h2Last-h1Last > 1 {
				tmp = h2[0]
				h2[0] = h2[h2Last-1]
				siftDown(h2, true, h2Last-1)
				h2Last--
				h1[h1Last] = tmp
				siftUp(h1, false, h1Last)
				h1Last++
			}
			// 输出
			if i%2 != 0 {
				if h1Last > h2Last {
					if printCnt%10 == 1 {
						if printCnt > 10 {
							Fprintln(out)
						}
						Fprint(out, h1[0])
					} else {
						Fprint(out, " ", h1[0])
					}
				} else {
					if printCnt%10 == 1 {
						if printCnt > 10 {
							Fprintln(out)
						}
						Fprint(out, h2[0])
					} else {
						Fprint(out, " ", h2[0])
					}
				}
				printCnt++
			}
		}
		Fprintln(out)
	}
}

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