{"problem":{"name":"『MdOI R5』Message","description":{"content":"小 A 有一个群。这个群正在玩一个小游戏：给出一个函数 $f$，从某一个时间点起，发送第 $x$ 条消息，而 $f(x)=1$ 的群友会受到一个小惩罚。当群内消息总数达到 $m$ 时游戏结束。 但小 A 是个话痨，这段时间他在这个群发了 $n$ 条消息，他发的第 $i$ 条消息在整个消息记录里是第 $a_i$ 条消息。 但是小 A 不想受到惩罚，而小 A 恰好是管理员，他可以撤回**任何时刻、","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8919"},"statements":[{"statement_type":"Markdown","content":"小 A 有一个群。这个群正在玩一个小游戏：给出一个函数 $f$，从某一个时间点起，发送第 $x$ 条消息，而 $f(x)=1$ 的群友会受到一个小惩罚。当群内消息总数达到 $m$ 时游戏结束。\n\n但小 A 是个话痨，这段时间他在这个群发了 $n$ 条消息，他发的第 $i$ 条消息在整个消息记录里是第 $a_i$ 条消息。\n\n但是小 A 不想受到惩罚，而小 A 恰好是管理员，他可以撤回**任何时刻、任何群成员发的任何消息**，注意这会导致这条消息之后的消息排名改变。\n\n但是撤回消息太多容易被当成暴政，因此他要尽可能减少撤回信息次数，不管是自己的还是别人的。\n\n接下来你也猜到你要干什么了：假如其他群成员不操作，给出 $n$、函数 $f$ 和 $a_i$，求出他至少要撤回几条消息。\n\n## Input\n\n输入的第一行有两个正整数 $n,m$，表示他的消息数量以及群内消息数量总数。\n\n第二行是一个长为 $m$ 的 **01 串** $f$，其第 $i$ 项 $f(i)$ 表示发第 $i$ 条消息的群成员是否要受到惩罚。\n\n第三行有 $n$ 个正整数 $a_1,a_2,\\ldots,a_n$，表示每条消息的初始排名。保证数列 $a$ 严格递增，且 $1\\le a_i\\le m$。\n\n## Output\n\n输出一行一个整数 $ans$ 表示至少撤回几条消息才能让小 A 不被惩罚。\n\n[samples]\n\n## Note\n\n【样例解释】\n\n下面给出一种可能的方式：\n- 小 A 先撤回第 $1$ 条消息（群友发的），他的四条消息在消息记录里现在是第 $1,5,7,10$ 条。\n- 然后撤回第 $5$ 条消息（他自己发的），剩下三条消息在消息记录里现在是第 $1,6,9$ 条。\n\n此时三条消息满足 $f(1)=f(6)=f(9)=0$，符合题意。\n\n可以证明无法仅撤回一条消息达成要求。\n\n【数据范围】\n\n|Subtask|$n\\le$|$m\\le$|特殊性质|分值|\n|:-:|:-:|:-:|:-:|:-:|\n|1|$17$|$17$||$15$|\n|2|$17$|$100$||$15$|\n|3|$10^3$|$10^4$||$20$|\n|4||$10^5$|$n=m$|$8$|\n|5|$10^5$|$10^6$|A|$12$|\n|6|$10^5$|$10^6$||$30$|\n\n- 特殊性质 A：小 A 没有连发两条消息。\n\n对于全部数据，$1\\le n\\le 10^5$，$1\\le a_i\\le m\\le 10^6$，$a_i$ 严格递增，$f(i)\\in \\{0,1\\}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8919","tags":["贪心","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["4 11\n01101010001\n2 6 8 11\n","2\n"]],"created_at":"2026-03-03 11:09:25"}}