#1792. 落日珊瑚
落日珊瑚
落日珊瑚
题目描述
标题: 落日珊瑚 - Problem - QOJ.ac
#7770. 落日珊瑚
The problem was used in the following contests:
题目描述
给一个长度为n、包含方括号和圆括号的括号串,定义一个串S 合法,当且仅当以下几种情况之一:
- S 为空串
- S=[T] 且 T 合法。
- S=(T) 且 T 合法。
- S=TU 且 T,U 合法。
比如(),[()]都是一个合法的括号串,但 [()]())不是。
定义一个操作叫选择一个区间 [l,r],并把所有在区间里的字符从方括号变圆括号,从圆括号变方括号。
定义一个括号串的权值val(S) 为:如果这个括号串能通过操作变成合法,就是最小的操作次数;否则是0。
给出 q 次修改查询,有以下两种可能。 1. 修改,给出一个区间[l,r] 把所有在区间里的字符从方括号变圆括号,从圆括号变方括号。 2. 查询,给出一个区间[l,r],求∑[l′,r′]∈[l,r]val(s[l′,r′])。
输入格式
第一行四个整数n,q,T,subtaskid,分别表示字符串长度,操作次数,强制在线的参数,子任务编号。
接下来一行一个长度为 n 的字符串。
接下来 q 行,每行三个数 opt,L,R,表示一次操作。
强制在线,真实的
l=min((L+T⋅lastans)modn+1,(R+T⋅lastans)modn+1)
r=max((L+T⋅lastans)modn+1,(R+T⋅lastans)modn+1)
其中 lastans 是上一次询问的答案,如果没有上次询问则为 0。
请注意,即使是离线的部分分,也有可能 L≠l, R≠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≤n,q≤5⋅105,0≤T≤109,1≤l,r≤n,1≤opt≤2。
子任务编号 n,q≤ 特殊性质 分值 1 100 E 5 2 6000 E 5 3 105 AE 5 4 2⋅105 BE 5 5 2⋅105 CDE 5 6 2⋅105 CE 10 7 2⋅105 DE 10 8 2⋅105 E 10 9 2⋅105 无 20 10 5⋅105 无 25
A性质:每个位置有14 的概率为方圆左右括号。
B性质:保证没有修改。
C性质:保证修改为单点修改。
D性质:保证查询区间[l,r]满足S[l,r]经过若干次操作可以变成合法串,且不存在另一个k∈[l,r),使得S[l,k]可以经过若干次操作变成合法串。
E性质:保证 T=0,即可以离线。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 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
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
0
0
1
2
1
0
4