{"problem":{"name":"「AWOI Round 2 C」数组操作？数组操作！","description":{"content":"给定两个长度为 $n$ 的数组 $a,b$ ，将它们合并得到一个长度为 $2\\times n$ 的数组 $c$。 设 $a$ 数组第 $i$ 个元素合并后位于 $c$ 数组第 $lb_i$ 个位置，$b$ 数组第 $i$ 个元素合并后位于 $c$ 数组第 $lc_i$ 个位置，合并后需要满足：$lb_1 < lb_2 < ...< lb_{n-1} < lb_n$ 且 $lc_1 < lc_2<","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9540"},"statements":[{"statement_type":"Markdown","content":"给定两个长度为 $n$ 的数组 $a,b$ ，将它们合并得到一个长度为 $2\\times n$ 的数组 $c$。\n\n设 $a$ 数组第 $i$ 个元素合并后位于 $c$ 数组第 $lb_i$ 个位置，$b$ 数组第 $i$ 个元素合并后位于 $c$ 数组第 $lc_i$ 个位置，合并后需要满足：$lb_1 < lb_2 < ...< lb_{n-1} < lb_n$ 且 $lc_1 < lc_2< ...< lc_{n-1}< lc_n$，即两个数组中元素的相对位置不变。\n\n合并过后，你需要对 $c$ 数组进行下面操作：\n\n1. 变换操作：选择一个区间 $[l,r]$，对于每一个 $i \\in [l,r]$，如果 $c_i$ 为 $y$，则将其变成一个不同于 $y$ 的数，否则将其变为 $y$。\n2. 翻转操作：选择一个区间 $[l,r]$，翻转该数组区间中的数。此操作**必须刚好**操作 $z$ 次。\n\n请输出最少需要执行多少次变换操作才能使得 $c$ 数组中的数字都为 $y$。 \n\n## Input\n\n第一行包含三个整数 $n,y,z$。\n\n第二行包含 $n$ 个整数，代表 $a$ 数组中的元素。\n\n第三行包含 $n$ 个整数，代表 $b$ 数组中的元素。\n\n## Output\n\n一个正整数，表示答案。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n对于样例 $1$，令 $c$ 为 $\\{1,1,1,9,45,1,1,9,4,810\\}$。\n\n其中 $c_1=a_1,c_2=b_1,c_3=a_2,c_4=b_2,c_5=a_3,c_6=a_4,c_7=b_3,c_8=b_4,c_9=a_5,c_{10}=b_5$。满足要求。\n\n然后翻转区间 $[4,7]$， $c$ 数组变为 $\\{1,1,1,1,1,45,9,9,4,810\\}$。\n\n接着执行变换操作，将 $[6,10]$ 中的数全部变成 $1$。\n\n所以最少只需要一次变换操作，可以证明没有比该方法更优的策略。\n\n**【数据规模】**\n\n请注意本题特殊的时间限制，并使用更快的 IO 方式。\n\n**本题使用捆绑测试。**\n\n| 子任务编号 | $n\\leqslant$ | 特殊性质 | 分值 |\n| -----------: | -----------: | -----------: | -----------: |\n| $1$ | $5$ | 无 | $20$ |\n| $2$ | $10^6$ | $z>n$ | $5$ |\n| $3$ | $10^6$ | 特殊性质 A | $10$ |\n| $4$ | $10^6$ | $z=0$ | $25$ |\n| $5$ | $10^6$ | 无 | $40$ |\n\n特殊性质 A：保证两个数组中的元素都为 $y$ 或都不为 $y$。\n\n对于全部数据，保证 $0 \\leqslant y,z \\leqslant 10^9$，输入数据全部在 `int` 范围内。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9540","tags":["贪心"],"sample_group":[["5 1 1\n1 1 45 1 4\n1 9 1 9 810","1"],["20 0 3\n1 0 0 8 6 10 0 8 6 1 0 0 86 1 0 0 8 6 0 0\n5 2 0 1 3 1 4 52 0 13 14 0 1 0 1 0 4 0 5 0","4"],["3 2 4\n110 105 117\n99 108 98","1"]],"created_at":"2026-03-03 11:09:25"}}