{"problem":{"name":"大娱乐至上","description":{"content":"给出一个由小写字母组成、长度为 $n$ 的字符串 $S$ 和一个长度为 $n$ 的 $01$ 串 $b$，$b_i=1$ 表示 $S_i$ 是可修改的。 给出 $m$ 个子串 $S_{[l,r]}$，定义一个子串 $str$ 是**非偏序**的，当且仅当可以通过修改 $S$ 的至多一个位置，使得 $m$ 个子串中原先 $<str$ 的子串都 $\\ge str$。 形式化地说，一个二元组 $(l","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10273"},"statements":[{"statement_type":"Markdown","content":"给出一个由小写字母组成、长度为 $n$ 的字符串 $S$ 和一个长度为 $n$ 的 $01$ 串 $b$，$b_i=1$ 表示 $S_i$ 是可修改的。\n\n给出 $m$ 个子串 $S_{[l,r]}$，定义一个子串 $str$ 是**非偏序**的，当且仅当可以通过修改 $S$ 的至多一个位置，使得 $m$ 个子串中原先 $<str$ 的子串都 $\\ge str$。\n\n形式化地说，一个二元组 $(l_i,r_i)$ 是**非偏序**的，当且仅当存在一个字符串 $T$（由 $S$ 修改至多一个字符得到），使得 $\\forall\\,1 \\le j \\le m,[S_{[l_j,r_j]}<S_{[l_i,r_i]}]+[T_{[l_j,r_j]}<T_{[l_i,r_i]}]\\not=2$。\n\n询问哪些子串是**非偏序**的。\n\n注意，修改后出现比 `a` 小或比 `z` 大的字符是**允许的**。\n\n## Input\n\n第一行两个数 $n,m$。\n\n第二行一个字符串 $S$。\n\n第三行一个 $01$ 串 $b$。\n\n接下来 $m$ 行，每行一个二元组 $(l_i,r_i)$。\n\n## Output\n\n输出为一个长度为 $m$ 的 $01$ 串 $ans$。$ans_i=1$ 表示 $(l_i,r_i)$ 是 `非偏序` 的，$ans_i=0$ 表示不是。\n\n[samples]\n\n## Background\n\n> 闪光，黑洞，万众瞩目之星。\n>\n> 美丽的国度之中最美丽的梦。\n>\n> 她的发丝比金箔更贵，她的唇印可抵成捆钞票。\n>\n> 而她的心呀，心呀，心呀，\n>\n> 不值一枚金币，不值一枚金币，不值一瞧。\n\n## Note\n\n### 样例一解释\n\n为了方便表述，钦定比 `a` 小的字符为 `#`，比 `z` 大的字符为 `*`。\n\n- $(1,5):$ 无论如何修改，恒有 $S_{[1,3]}<S_{[1,5]},T_{[1,3]}<T_{[1,5]}$。\n\n- $(7,10):$ $T$ 可以为 `abbcababaa`。\n\n- $(1,3):$ $T$ 可以为 `a#baababaa`。\n\n- $(3,7):$ $T$ 可以为 `ab#aababaa`。\n\n- $(4,8):$ $T$ 可以为 `abbaababaa`。\n\n### 数据范围与约定\n \n**本题采用捆绑测试**。\n\n$\\text{subtask1(10pt):}$ $1 \\le n,m \\le 100$。\n\n$\\text{subtask2(30pt):}$ $1 \\le n,m \\le 1000$。\n\n$\\text{subtask3(10pt):}$ $b_i=1$。\n\n$\\text{subtask4(50pt):}$ 无特殊限制。\n\n对于所有数据，$1\\le n,m \\le 2\\times 10^5,1 \\le l_i \\le r_i \\le n$，输入均为整数和小写字母。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10273","tags":["O2优化"],"sample_group":[["10 5\nabbaababaa\n0111111111\n1 5\n7 10\n1 3\n3 7\n4 8","01111"]],"created_at":"2026-03-03 11:09:25"}}