OpenJudge

1017:Challenge 17

总时间限制:
20000ms
单个测试点时间限制:
3000ms
内存限制:
512000kB
描述

给你一个长度为n的括号序列a(仅含小括号)和m个操作。

每次操作格式为opt, l, r。

opt=0表示询问将a[l .. r]更改为合法的括号序列最少需要反转多少个括号。

opt=1表示将a[l .. r]反转,既将所有左括号改为右括号,右括号改为左括号。

opt=2表示将a[l .. r]翻转,既交换a[l]与a[r],a[l + 1]与a[r - 1]……

合法序列的定义:

空串为合法序列

“(合法序列)”为合法序列

“合法序列合法序列”为合法序列

输入
第一行两个正整数n和m。
第二行一个长度为n的仅由'('与')'构成的串,表示初始时的a。
接下来m行每行描述一个操作,格式如题目描述。
输出
对于每个0操作输出一行一个整数表示答案。
样例输入
3 6
())
0 1 2
1 1 3
0 1 2
2 3 3
0 2 3
样例输出
0
2
1
1
提示
1 ≤ n, m ≤ 100,000
1 ≤ l, r ≤ n
对于询问保证长度为偶数
来源
hejiaao

请大家尽量使用非暴力的在线做法
部分题目可尝试多种解法
C++选手尽量不用STL容器

全局题号
7639
添加于
2014-11-19
提交次数
17
尝试人数
8
通过人数
8