{"problem":{"name":"[集训队互测 2023] 落日珊瑚","description":{"content":"给一个长度为 $n$、包含方括号和圆括号的括号串，定义一个串 $S$ 合法，当且仅当以下几种情况之一： 1.  $S$ 为空串； 1.  $S= [T]$ 且 $T$ 合法； 1.  $S= (T)$ 且 $T$ 合法； 1.  $S=TU$ 且 $T, U$ 合法。 比如 ```()```，```[()]``` 都是一个合法的括号串，但 ```[()]())``` 不是。 定义一个操作叫选","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10012"},"statements":[{"statement_type":"Markdown","content":"给一个长度为 $n$、包含方括号和圆括号的括号串，定义一个串 $S$ 合法，当且仅当以下几种情况之一：\n\n1.  $S$ 为空串；\n1.  $S= [T]$ 且 $T$ 合法；\n1.  $S= (T)$ 且 $T$ 合法；\n1.  $S=TU$ 且 $T, U$ 合法。\n\n比如 ```()```，```[()]``` 都是一个合法的括号串，但 ```[()]())``` 不是。\n\n定义一个操作叫选择一个区间 $[l, r]$，并把所有在区间里的字符从方括号变圆括号，从圆括号变方括号。\n\n定义一个括号串的权值 $val(S)$ 为：如果这个括号串能通过操作变成合法，就是最小的操作次数；否则是 $0$。\n\n给出 $q$ 次修改查询，有以下两种可能。\n\n1.  修改，给出一个区间 $[l, r]$ 把所有在区间里的字符从方括号变圆括号，从圆括号变方括号。\n2.  查询，给出一个区间 $[l, r]$，求 $\\sum_{[l', r'] \\in [l, r]} val(s[l', r'])$。\n\n## Input\n\n第一行四个整数 $n, q, T, subtaskid$，分别表示字符串长度，操作次数，强制在线的参数，子任务编号。\n\n接下来一行一个长度为 $n$ 的字符串。\n\n接下来 $q$ 行，每行三个数 $opt, L, R$，表示一次操作。\n\n强制在线，真实的 $l = \\min((L + T \\cdot lastans) \\bmod n + 1, (R + T \\cdot lastans) \\bmod n + 1)$，$r = \\max((L + T \\cdot lastans) \\bmod n + 1, (R + T \\cdot lastans) \\bmod n + 1)$ 其中 $lastans$ 是上一次询问的答案，如果没有上次询问则为 $0$。\n\n**请注意，即使是离线的部分分，也有可能 $L \\neq l$，$R \\neq r$**。\n\n## Output\n\n若干行，每次询问输出一个答案。\n\n[samples]\n\n## Note\n\n对于所有数据，$1 \\le n, q \\le 5\\cdot 10^5$，$0 \\le T \\le 10^9$，$1 \\le l, r \\le n$，$1 \\le opt \\le 2$。\n\n| 子任务编号 |  $n, q \\le $  | 特殊性质 | 分值 |\n| :--------: | :-----------: | :------: | :--: |\n|     1      |      $100$      |    E     |  5   |\n|     2      |     $6000$      |    E     |  5   |\n|     3      |    $10^5$     |    AE    |  5   |\n|     4      | $2\\cdot 10^5$ |    BE    |  5   |\n|     5      | $2\\cdot 10^5$ |   CDE    |  5   |\n|     6      | $2\\cdot 10^5$ |    CE    |  10  |\n|     7      | $2\\cdot 10^5$ |    DE    |  10  |\n|     8      | $2\\cdot 10^5$ |    E     |  10  |\n|     9      | $2\\cdot 10^5$ |    无    |  20  |\n|     10     | $5\\cdot 10^5$ |    无    |  25  |\n\nA 性质：每个位置有 $\\frac{1}{4}$ 的概率为方圆左右括号。\n\nB 性质：保证没有修改。\n\nC 性质：保证修改为单点修改。\n\nD 性质：保证查询区间 $[l, r]$ 满足 $S[l, r]$ 经过若干次操作可以变成合法串，且不存在另一个 $k \\in [l, r)$，使得 $S[l, k]$ 可以经过若干次操作变成合法串。\n\nE 性质：保证 $T = 0$，即可以离线。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10012","tags":["集训队互测","2023"],"sample_group":[["10 10 0 0\n[)]]((()][\n2 10 6\n1 6 6\n1 3 6\n2 5 7\n2 3 3\n2 10 4\n1 7 1\n2 4 4\n2 4 2\n1 5 5\n","1\n0\n0\n1\n0\n0\n"],["20 20 0 0\n[)])[)[](()((]]([[)[\n2 9 3\n2 8 10\n1 4 15\n1 5 9\n1 16 10\n1 18 20\n1 1 8\n2 8 9\n1 2 16\n1 10 13\n1 16 9\n1 8 1\n2 20 7\n2 14 11\n1 3 16\n1 15 18\n1 6 4\n2 10 7\n2 2 4\n2 13 2\n","2\n0\n0\n1\n2\n1\n0\n4\n"]],"created_at":"2026-03-03 11:09:25"}}