QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100

# 7770. 落日珊瑚

统计

题目描述

给一个长度为$n$、包含方括号和圆括号的括号串,定义一个串$S$ 合法,当且仅当以下几种情况之一:

  1. $S$ 为空串
  2. $S= [T]$ 且 $T$ 合法。
  3. $S= (T)$ 且 $T$ 合法。
  4. $S=TU$ 且 $T, U$ 合法。

比如()[()]都是一个合法的括号串,但 [()]())不是。

定义一个操作叫选择一个区间 $[l, r]$,并把所有在区间里的字符从方括号变圆括号,从圆括号变方括号。

定义一个括号串的权值$val(S)$ 为:如果这个括号串能通过操作变成合法,就是最小的操作次数;否则是0。

给出 $q$ 次修改查询,有以下两种可能。 1. 修改,给出一个区间$[l, r]$ 把所有在区间里的字符从方括号变圆括号,从圆括号变方括号。 2. 查询,给出一个区间$[l, r]$,求$\sum_{[l', r'] \in [l, r]} val(s[l', r'])$。

输入格式

第一行四个整数$n, q, T, subtaskid$,分别表示字符串长度,操作次数,强制在线的参数,子任务编号。

接下来一行一个长度为 $n$ 的字符串。

接下来 $q$ 行,每行三个数 $opt, L, R$,表示一次操作。

强制在线,真实的

$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$。

请注意,即使是离线的部分分,也有可能 $L \neq l$, $R \neq r$

输出格式

若干行,每次询问输出一个答案。

样例

样例输入 1

10 10 0 0
[)]]((()][
2 10 6
1 6 6
1 3 6
2 5 7
2 3 3
2 10 4
1 7 1
2 4 4
2 4 2
1 5 5

样例输出 1

1
0
0
1
0
0

样例输入 2

20 20 0 0
[)])[)[](()((]]([[)[
2 9 3
2 8 10
1 4 15
1 5 9
1 16 10
1 18 20
1 1 8
2 8 9
1 2 16
1 10 13
1 16 9
1 8 1
2 20 7
2 14 11
1 3 16
1 15 18
1 6 4
2 10 7
2 2 4
2 13 2

样例输出 2

2
0
0
1
2
1
0
4

样例 3

见下发文件。

数据范围

$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, q \le $ 特殊性质 分值
1 100 E 5
2 6000 E 5
3 $10^5$ AE 5
4 $2\cdot 10^5$ BE 5
5 $2\cdot 10^5$ CDE 5
6 $2\cdot 10^5$ CE 10
7 $2\cdot 10^5$ DE 10
8 $2\cdot 10^5$ E 10
9 $2\cdot 10^5$ 20
10 $5\cdot 10^5$ 25

A性质:每个位置有$\frac{1}{4}$ 的概率为方圆左右括号。

B性质:保证没有修改。

C性质:保证修改为单点修改。

D性质:保证查询区间$[l, r]$满足$S[l, r]$经过若干次操作可以变成合法串,且不存在另一个$k \in [l, r)$,使得$S[l, k]$可以经过若干次操作变成合法串。

E性质:保证 $T = 0$,即可以离线。