{"problem":{"name":"[蓝桥杯 2021 国 AB] 翻转括号序列","description":{"content":"给定一个长度为 $n$ 的括号序列，要求支持两种操作: 1. 将 $\\left[L_{i}, R_{i}\\right]$ 区间内（序列中的第 $L_{i}$ 个字符到第 $R_{i}$ 个字符）的括号全部翻转(左括号变成右括号，右括号变成左括号)。 2. 求出以 $L_{i}$ 为左端点时，最长的合法括号序列对应的 $R_{i}$ （即找出最大的 $R_{i}$ 使 $\\left[L_{i},","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8765"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的括号序列，要求支持两种操作:\n\n1. 将 $\\left[L_{i}, R_{i}\\right]$ 区间内（序列中的第 $L_{i}$ 个字符到第 $R_{i}$ 个字符）的括号全部翻转(左括号变成右括号，右括号变成左括号)。\n\n2. 求出以 $L_{i}$ 为左端点时，最长的合法括号序列对应的 $R_{i}$ （即找出最大的 $R_{i}$ 使 $\\left[L_{i}, R_{i}\\right]$ 是一个合法括号序列）。\n\n## Input\n\n输入的第一行包含两个整数 $n, m$，分别表示括号序列长度和操作次数。\n\n第二行包含给定的括号序列，括号序列中只包含左括号和右括号。\n\n接下来 $m$ 行，每行描述一个操作。如果该行为 `1 L R`, 表示第一种操作，区间为 $\\left[L, R\\right]$；如果该行为 `2 L` 表示第二种操作，左端点为 $L$ 。\n\n## Output\n\n对于每个第二种操作，输出一行，表示对应的 $R_{i}$。如果不存在这样的 $R_{i}$，请输出 $0$ 。\n\n[samples]\n\n## Note\n\n对于 $20 \\%$ 的评测用例，$n, m \\leq 5000$;\n\n对于 $40 \\%$ 的评测用例，$n, m \\leq 30000$;\n\n对于 $60 \\%$ 的评测用例，$n, m \\leq 100000$;\n\n对于所有评测用例，$1 \\leq n \\leq 10^{6}, 1 \\leq m \\leq 2 \\times 10^{5}$ 。 \n\n蓝桥杯 2021 国赛 A 组 H 题（B 组 I 题）。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8765","tags":["线段树","二分","2021","蓝桥杯国赛"],"sample_group":[["7 5\n((())()\n2 3\n2 2\n1 3 5\n2 3\n2 1","4\n7\n0\n0"]],"created_at":"2026-03-03 11:09:25"}}