#1792. 落日珊瑚

    ID: 1792 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1419来源:qoj.ac数据:公开样例线段树

落日珊瑚

落日珊瑚

题目描述

标题: 落日珊瑚 - Problem - QOJ.ac

#7770. 落日珊瑚

Statistics

The problem was used in the following contests:

题目描述

给一个长度为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],求∑[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