#1813. 括号

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

括号

括号

题目描述

标题: 括号 - Problem - QOJ.ac

Statistics

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