{"problem":{"name":"[THUPC 2024 决赛] 贸易","description":{"content":"小 Z 生活的学校就像是一条链，直径很长，宽度很窄。 具体来说，这里有一个长度为 $n$ 的序列，每个位置有一个属性 $a_i\\in \\{0/1\\}$ 和一个类型 $c_i$，在这里有一些贸易事件会发生。 小 Z 从左往右通过这个序列，若当前遇到一个 $0$ 属性的节点，则小 Z 可以购入至多一个 $c_i$ 类型的物品，若当前遇到一个 $1$ 属性的节点，则小 Z 可以卖出至多一个 $c_i","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10550"},"statements":[{"statement_type":"Markdown","content":"小 Z 生活的学校就像是一条链，直径很长，宽度很窄。\n\n具体来说，这里有一个长度为 $n$ 的序列，每个位置有一个属性 $a_i\\in \\{0/1\\}$ 和一个类型 $c_i$，在这里有一些贸易事件会发生。\n\n小 Z 从左往右通过这个序列，若当前遇到一个 $0$ 属性的节点，则小 Z 可以购入至多一个 $c_i$ 类型的物品，若当前遇到一个 $1$ 属性的节点，则小 Z 可以卖出至多一个 $c_i$ 类型的物品，显然，在小 Z 没有这种类型的物品时是不能卖出的。\n\n一次合法的交易定义为从某个节点买入，并在某个节点卖出，注意，你需要保证在最后小 Z 手里不存在任何东西。\n\n给出 $q$ 次询问，每次小 Z 从 $l_i$ 顺序走到 $r_i$，问：最大合法交易次数是多少。\n\n## Input\n\n第一行两个正整数 $n,q$。\n\n接下来一行 $n$ 个数，第 $i$ 个表示 $a_i$。\n\n接下来一行 $n$ 个数，第 $i$ 个表示 $c_i$。\n\n接下来 $q$ 行，每行两个数表示 $l_i,r_i$。\n\n## Output\n\n输出共 $q$ 行，每行一个数表示当前这个询问中的最大合法交易次数。\n\n[samples]\n\n## Note\n\n对于所有数据，满足 $1\\le n,q\\le5\\times 10^5,1\\le c_i\\le n,1\\le l_i\\le r_i\\le n,a_i\\in\\{0,1\\}$。\n\n请注意输入输出效率。\n\n**来源与致谢**\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。\n\n数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10550","tags":["2024","THUPC"],"sample_group":[["10 5\n1 1 0 0 0 0 0 1 1 1 \n1 1 1 1 1 1 1 1 1 1 \n4 6\n2 4\n2 6\n7 10\n4 7\n","0\n0\n0\n1\n0\n"]],"created_at":"2026-03-03 11:09:25"}}