{"problem":{"name":"[CoE R4 D] 01 串","description":{"content":"定义一个好的 $01$ 串 $\\mathcal{S}$ 满足以下条件： + $\\mathcal{S}$ 非空。 + $\\mathcal{S}$ 的任意一个前缀 $\\mathcal {S} [1\\dots p](p\\in [1,|\\mathcal S|])$ 中，$0$ 的数量都不多于 $1$ 的数量。 + $\\mathcal{S}$ 的任意一个后缀 $\\mathcal S[p\\dots |\\m","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8304"},"statements":[{"statement_type":"Markdown","content":"定义一个好的 $01$ 串 $\\mathcal{S}$ 满足以下条件：\n\n+ $\\mathcal{S}$ 非空。\n\n+ $\\mathcal{S}$ 的任意一个前缀 $\\mathcal {S} [1\\dots p](p\\in [1,|\\mathcal S|])$ 中，$0$ 的数量都不多于 $1$ 的数量。\n+ $\\mathcal{S}$ 的任意一个后缀 $\\mathcal S[p\\dots |\\mathcal{S}|](p\\in [1,|\\mathcal S|])$ 中，$0$ 的数量都不多于 $1$ 的数量。\n\n现在你得到了一个长度为 $n$ 的 $01$ 串 $\\mathcal{T}$，有 $q$ 次询问，每次询问给定一对 $l,r$，求 $\\mathcal{T}[l\\dots r]$ 中的最长的好的 $01$ **子序列** 的长度。若没有好的 $01$ 子序列，则输出 $-1$。\n\n注意：**子序列** 是指去除某些元素但不破坏余下元素的相对位置而形成的新序列。\n\n## Input\n\n第一行两个整数 $n,q$，分别表示 $01$ 串的长度和询问次数。\n\n第二行一个长度为 $n$ 的 $01$ 串，表示 $\\mathcal{T}$。\n\n接下来 $q$ 行，每行两个整数 $l,r$，表示一次询问。\n\n## Output\n\n输出 $q$ 行，每行一个整数，依次表示每次询问的答案。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n第一次询问中，询问的串为 $0$，没有任何的子序列是好的，所以答案是 $-1$。\n\n第二次询问中，询问的串为 $01001$，子序列 $101$ 是好的且是最长的，所以答案是 $3$。\n\n第三次询问中，询问的串为 $10010101$，子序列 $1010101$ 是好的且是最长的，所以答案是 $7$。\n\n第四次询问中，询问的串为 $0100101011$，子序列 $10101011$ 是好的且是最长的，所以答案是 $8$。\n\n---\n\n### 数据规模\n\n**本题采用捆绑测试。**\n\n| 子任务 | 分值 | $n \\le$ | $q \\le$ |\n| :-: | :-: | :-: | :-: |\n| $1$ | $10$ | $10$ | $10$ |\n| $2$ | $20$ | $2000$ | $2000$ |\n| $3$ | $30$ | $8\\times 10^4$ | $8\\times 10^4$ |\n| $4$ | $10$ | $10^5$ | $1$ |\n| $5$ | $30$ | $5\\times 10^5$ | $5\\times 10^5$ |\n\n对于 $100\\%$ 的数据，$1 \\leq l \\leq r \\leq n \\leq 5 \\times 10^5$，$1 \\leq q \\leq 5 \\times 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8304","tags":["贪心","线段树","洛谷原创","O2优化","前缀和","洛谷月赛"],"sample_group":[["10 4\n0100101011\n1 1\n1 5\n2 9\n1 10","-1\n3\n7\n8"]],"created_at":"2026-03-03 11:09:25"}}