#1813. 括号
括号
括号
题目描述
标题: 括号 - Problem - QOJ.ac
The problem was used in the following contests:
定义一个只包括 ( 和 ) 的字符串 s 为括号串,定义合法括号串如下:
- 空串是合法括号字符串
- 如果 A 和 B 都是合法括号串,那么 A+B 也是合法括号串
- 人如果 A 是合法括号串,那么 (A) 也是合法括号串
给出一个长度为 2n 的括号序列 s,修改第 i 个括号有代价 ai,q 次修改 ai 并询问将 s 修改为合法括号串的最小代价和,修改是永久的,询问相互独立。
输入格式
第一行两个正整数 n,q。
接下来一行 2n 个非负整数 a1,…,a2n。
接下来一行一个长为 2n 的括号串 s。
接下来 q 行,每行两个非负整数 i,x,表示将 ai 修改为 x。
输出格式
输出 q+1 行,顺序表示初始和进行完每次修改后的答案。
样例
样例输入 1
3 5
9 2 2 2 2 10
())(((
3 7
5 10
6 5
2 2
6 2
样例输出 1
14
14
14
9
9
6
样例输入 2
5 10
5 10 6 8 3 6 2 1 16 11
((())()(((
4 9
9 9
2 11
4 20
7 9
1 5
9 16
8 4
2 18
4 20
样例输出 2
12
12
12
12
12
12
12
12
15
15
15
样例 3~5
见下发文件。
数据范围
对于所有数据,满足 1≤n≤105,1≤q≤5×105,0≤ai,x≤109,s 为括号串。
- subtask 1(15pts): n,q≤100
- subtask 2(10pts): n,q≤1000,s 在所有括号串中随机生成
- subtask 3(10pts): n,q≤1000
- subtask 4(5pts): ai=x=1
- subtask 5(25pts): q≤105
- subtask 6(35pts): 无特殊限制
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 5
9 2 2 2 2 10
())(((
3 7
5 10
6 5
2 2
6 2
14
14
14
9
9
6
样例 2
5 10
5 10 6 8 3 6 2 1 16 11
((())()(((
4 9
9 9
2 11
4 20
7 9
1 5
9 16
8 4
2 18
4 20
12
12
12
12
12
12
12
12
15
15
15