310030: CF1773L. Lisa's Sequences
Memory Limit：1024 MB
Time Limit：5 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Lisa's Sequences
题意翻译
有一个长度为 $n$ 的数列 $b_i$，求至少改变多少个数使得最长的不降或不升子序列 $b_l,b_{l+1},...b_{r}$ 长度小于 $k$。题目描述
Lisa loves playing with the sequences of integers. When she gets a new integer sequence $ a_i $ of length $ n $ , she starts looking for all monotone subsequences. A monotone subsequence $ [l, r] $ is defined by two indices $ l $ and $ r $ ( $ 1 \le l < r \le n $ ) such that $ \forall i = l, l+1, \ldots, r-1: a_i \le a_{i+1} $ or $ \forall i = l, l+1, \ldots, r-1: a_i \ge a_{i+1} $ . Lisa considers a sequence $ a_i $ to be boring if there is a monotone subsequence $ [l, r] $ that is as long as her boredom threshold $ k $ , that is when $ r - l + 1 = k $ . Lucas has a sequence $ b_i $ that he wants to present to Lisa, but the sequence might be boring for Lisa. So, he wants to change some elements of his sequence $ b_i $ , so that Lisa does not get bored playing with it. However, Lucas is lazy and wants to change as few elements of the sequence $ b_i $ as possible. Your task is to help Lucas find the required changes.输入输出格式
输入格式
The first line of the input contains two integers $ n $ and $ k $ ( $ 3 \le k \le n \le 10^6 $ ) — the length of the sequence and Lisa's boredom threshold. The second line contains $ n $ integers $ b_i $ ( $ 1 \le b_i \le 99\,999 $ ) — the original sequence that Lucas has.
输出格式
On the first line output an integer $ m $ — the minimal number of elements in $ b_i $ that needs to be changed to make the sequence not boring for Lisa. On the second line output $ n $ integers $ a_i $ ( $ 0 \le a_i \le 100\,000 $ ), so that the sequence of integers $ a_i $ is not boring for Lisa and is different from the original sequence $ b_i $ in exactly $ m $ positions.
输入输出样例
输入样例 #1
5 3
1 2 3 4 5输出样例 #1
2
1 0 3 0 5输入样例 #2
6 3
1 1 1 1 1 1输出样例 #2
3
1 100000 0 1 0 1输入样例 #3
6 4
1 1 4 4 1 1输出样例 #3
1
1 1 4 0 1 1输入样例 #4
6 4
4 4 4 2 2 2输出样例 #4
2
4 4 0 2 0 2输入样例 #5
6 4
4 4 4 3 4 4输出样例 #5
1
4 4 100000 3 4 4输入样例 #6
8 4
2 1 1 3 3 1 1 2输出样例 #6
2
2 1 1 3 0 1 0 2输入样例 #7
10 4
1 1 1 2 2 1 1 2 2 1输出样例 #7
2
1 1 100000 2 2 100000 1 2 2 1输入样例 #8
7 5
5 4 4 3 4 4 4输出样例 #8
0
5 4 4 3 4 4 4输入样例 #9
10 10
1 1 1 1 1 1 1 1 1 1输出样例 #9
1
1 1 1 1 1 1 1 1 0 1Input
题意翻译
有一个长度为 $n$ 的数列 $b_i$，求至少改变多少个数使得最长的不降或不升子序列 $b_l,b_{l+1},...b_{r}$ 长度小于 $k$。Output
**题意翻译**
有一个长度为 $ n $ 的数列 $ b_i $，求至少改变多少个数使得最长的不降或不升子序列 $ b_l, b_{l+1}, \ldots, b_{r} $ 长度小于 $ k $。
**题目描述**
Lisa 喜欢玩整数序列。当她得到一个新的整数序列 $ a_i $ 时，她开始寻找所有的单调子序列。一个单调子序列由两个指标 $ l $ 和 $ r $ 定义（$ 1 \le l < r \le n $），使得对于所有 $ i = l, l+1, \ldots, r-1 $，满足 $ a_i \le a_{i+1} $ 或 $ a_i \ge a_{i+1} $。
Lisa 认为一个序列 $ a_i $ 是无聊的，如果存在一个长度达到她的无聊阈值 $ k $ 的单调子序列，即当 $ r - l + 1 = k $。
Lucas 有一个序列 $ b_i $，他想呈现给 Lisa，但这个序列可能会让 Lisa 感到无聊。因此，他想改变序列 $ b_i $ 的一些元素，使得 Lisa 玩起来不会感到无聊。然而，Lucas 很懒，他想尽可能少地改变序列 $ b_i $ 中的元素。你的任务是帮助 Lucas 找到所需的改变。
**输入输出格式**
**输入格式**
输入的第一行包含两个整数 $ n $ 和 $ k $（$ 3 \le k \le n \le 10^6 $）——序列的长度和 Lisa 的无聊阈值。第二行包含 $ n $ 个整数 $ b_i $（$ 1 \le b_i \le 99,999 $）—— Lucas 拥有的原始序列。
**输出格式**
在第一行输出一个整数 $ m $——需要改变的 $ b_i $ 中元素的最小数量，以使序列对 Lisa 来说不无聊。在第二行输出 $ n $ 个整数 $ a_i $（$ 0 \le a_i \le 100,000 $），使得整数序列 $ a_i $ 对 Lisa 来说不无聊，并且与原始序列 $ b_i $ 恰好在 $ m $ 个位置上不同。**题意翻译** 有一个长度为 $ n $ 的数列 $ b_i $，求至少改变多少个数使得最长的不降或不升子序列 $ b_l, b_{l+1}, \ldots, b_{r} $ 长度小于 $ k $。 **题目描述** Lisa 喜欢玩整数序列。当她得到一个新的整数序列 $ a_i $ 时，她开始寻找所有的单调子序列。一个单调子序列由两个指标 $ l $ 和 $ r $ 定义（$ 1 \le l < r \le n $），使得对于所有 $ i = l, l+1, \ldots, r-1 $，满足 $ a_i \le a_{i+1} $ 或 $ a_i \ge a_{i+1} $。 Lisa 认为一个序列 $ a_i $ 是无聊的，如果存在一个长度达到她的无聊阈值 $ k $ 的单调子序列，即当 $ r - l + 1 = k $。 Lucas 有一个序列 $ b_i $，他想呈现给 Lisa，但这个序列可能会让 Lisa 感到无聊。因此，他想改变序列 $ b_i $ 的一些元素，使得 Lisa 玩起来不会感到无聊。然而，Lucas 很懒，他想尽可能少地改变序列 $ b_i $ 中的元素。你的任务是帮助 Lucas 找到所需的改变。 **输入输出格式** **输入格式** 输入的第一行包含两个整数 $ n $ 和 $ k $（$ 3 \le k \le n \le 10^6 $）——序列的长度和 Lisa 的无聊阈值。第二行包含 $ n $ 个整数 $ b_i $（$ 1 \le b_i \le 99,999 $）—— Lucas 拥有的原始序列。 **输出格式** 在第一行输出一个整数 $ m $——需要改变的 $ b_i $ 中元素的最小数量，以使序列对 Lisa 来说不无聊。在第二行输出 $ n $ 个整数 $ a_i $（$ 0 \le a_i \le 100,000 $），使得整数序列 $ a_i $ 对 Lisa 来说不无聊，并且与原始序列 $ b_i $ 恰好在 $ m $ 个位置上不同。
有一个长度为 $ n $ 的数列 $ b_i $，求至少改变多少个数使得最长的不降或不升子序列 $ b_l, b_{l+1}, \ldots, b_{r} $ 长度小于 $ k $。
**题目描述**
Lisa 喜欢玩整数序列。当她得到一个新的整数序列 $ a_i $ 时，她开始寻找所有的单调子序列。一个单调子序列由两个指标 $ l $ 和 $ r $ 定义（$ 1 \le l < r \le n $），使得对于所有 $ i = l, l+1, \ldots, r-1 $，满足 $ a_i \le a_{i+1} $ 或 $ a_i \ge a_{i+1} $。
Lisa 认为一个序列 $ a_i $ 是无聊的，如果存在一个长度达到她的无聊阈值 $ k $ 的单调子序列，即当 $ r - l + 1 = k $。
Lucas 有一个序列 $ b_i $，他想呈现给 Lisa，但这个序列可能会让 Lisa 感到无聊。因此，他想改变序列 $ b_i $ 的一些元素，使得 Lisa 玩起来不会感到无聊。然而，Lucas 很懒，他想尽可能少地改变序列 $ b_i $ 中的元素。你的任务是帮助 Lucas 找到所需的改变。
**输入输出格式**
**输入格式**
输入的第一行包含两个整数 $ n $ 和 $ k $（$ 3 \le k \le n \le 10^6 $）——序列的长度和 Lisa 的无聊阈值。第二行包含 $ n $ 个整数 $ b_i $（$ 1 \le b_i \le 99,999 $）—— Lucas 拥有的原始序列。
**输出格式**
在第一行输出一个整数 $ m $——需要改变的 $ b_i $ 中元素的最小数量，以使序列对 Lisa 来说不无聊。在第二行输出 $ n $ 个整数 $ a_i $（$ 0 \le a_i \le 100,000 $），使得整数序列 $ a_i $ 对 Lisa 来说不无聊，并且与原始序列 $ b_i $ 恰好在 $ m $ 个位置上不同。**题意翻译** 有一个长度为 $ n $ 的数列 $ b_i $，求至少改变多少个数使得最长的不降或不升子序列 $ b_l, b_{l+1}, \ldots, b_{r} $ 长度小于 $ k $。 **题目描述** Lisa 喜欢玩整数序列。当她得到一个新的整数序列 $ a_i $ 时，她开始寻找所有的单调子序列。一个单调子序列由两个指标 $ l $ 和 $ r $ 定义（$ 1 \le l < r \le n $），使得对于所有 $ i = l, l+1, \ldots, r-1 $，满足 $ a_i \le a_{i+1} $ 或 $ a_i \ge a_{i+1} $。 Lisa 认为一个序列 $ a_i $ 是无聊的，如果存在一个长度达到她的无聊阈值 $ k $ 的单调子序列，即当 $ r - l + 1 = k $。 Lucas 有一个序列 $ b_i $，他想呈现给 Lisa，但这个序列可能会让 Lisa 感到无聊。因此，他想改变序列 $ b_i $ 的一些元素，使得 Lisa 玩起来不会感到无聊。然而，Lucas 很懒，他想尽可能少地改变序列 $ b_i $ 中的元素。你的任务是帮助 Lucas 找到所需的改变。 **输入输出格式** **输入格式** 输入的第一行包含两个整数 $ n $ 和 $ k $（$ 3 \le k \le n \le 10^6 $）——序列的长度和 Lisa 的无聊阈值。第二行包含 $ n $ 个整数 $ b_i $（$ 1 \le b_i \le 99,999 $）—— Lucas 拥有的原始序列。 **输出格式** 在第一行输出一个整数 $ m $——需要改变的 $ b_i $ 中元素的最小数量，以使序列对 Lisa 来说不无聊。在第二行输出 $ n $ 个整数 $ a_i $（$ 0 \le a_i \le 100,000 $），使得整数序列 $ a_i $ 对 Lisa 来说不无聊，并且与原始序列 $ b_i $ 恰好在 $ m $ 个位置上不同。