#PQJ1455x7973. QOJ 1455_7973

    ID: 2610 传统题 2000ms 512MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:2023-2024 集训队互测线段树差分

QOJ 1455_7973

标题: 括号 - 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): 无特殊限制