{"problem":{"name":"「DTOI-4」中位数","description":{"content":"给定一个长度为 $n$ 的整数序列 $a$，你可以进行以下操作不超过 $k$ 次： - 选择一个区间 $[l, r]$ 满足 $1 \\leq l \\leq r \\leq n$，并将 $[l, r]$ 中的所有数替换为这个区间的中位数。 你要使得操作后 $a$ 的**最小值最大**。 关于此处中位数的定义：对于一个长度为 $len$ 的序列，其中位数定义为该序列中第 $\\lceil \\frac","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8978"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的整数序列 $a$，你可以进行以下操作不超过 $k$ 次：\n\n- 选择一个区间 $[l, r]$ 满足 $1 \\leq l \\leq r \\leq n$，并将 $[l, r]$ 中的所有数替换为这个区间的中位数。\n\n你要使得操作后 $a$ 的**最小值最大**。\n\n关于此处中位数的定义：对于一个长度为 $len$ 的序列，其中位数定义为该序列中第 $\\lceil \\frac{len}{2} \\rceil$ 小的数。\n\n## Input\n\n第一行，两个整数 $n, k$；\n\n第二行，$n$ 个整数 $a_1, a_2, \\cdots, a_n$。\n\n## Output\n\n一行，表示经过不超过 $k$ 次操作后序列最小值的最大值。\n\n[samples]\n\n## Note\n\n| $\\textbf{Subtask}$ | $n$ | 分值 |\n| :------: | :------: | :------: |\n| $1$ | $1 \\leq n \\leq 10$ | $10 \\operatorname{pts}$ |\n| $2$ | $1 \\leq n \\leq 100$ | $10 \\operatorname{pts}$ |\n| $3$ | $1 \\leq n \\leq 10^3$ | $10 \\operatorname{pts}$ |\n| $4$ | $1 \\leq n \\leq 10^4$ | $20 \\operatorname{pts}$ |\n| $5$ | $1 \\leq n \\leq 10^5$ | $20 \\operatorname{pts}$ |\n| $6$ | 无特殊限制 | $30 \\operatorname{pts}$ |\n\n对于 $100\\%$ 的数据，$1 \\leq n \\leq 4 \\times 10^5$，$0 \\leq k \\leq n$，$0 \\leq a_i \\leq 10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8978","tags":["动态规划 DP","二分","单调队列","2023","洛谷原创","O2优化"],"sample_group":[["10 2\n2 8 3 2 5 7 10 4 9 7","7"],["30 3\n1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0","0"],["31 3\n1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1","1"]],"created_at":"2026-03-03 11:09:25"}}