seuOJ454 - Bracket Distance

题目描述

有一个长度为nn的括号序列seqseq，序列下标从11开始，你需要从中选择一个子序列，该子序列需要满足：

  1. 该序列是一个匹配的括号序列。
  2. 该序列中没有出现多层括号嵌套的情况。 例如(())中就出现了一个两层括号嵌套的情况，是不满足条件的，但是()()()就是一个满足条件的括号序列。

假设选出的括号序列ss长度为lenlen，indexiindex_i表示序列中第ii个括号在原序列中的下标，那么这个括号序列的优美度为：

∑i=1lenindexi⋅[si=′)′]−∑i=1lenindexi⋅[si=′(′]\sum_{i=1}^{len} index_i·[s_i = ')'] - \sum_{i=1}^{len} index_i·[s_i = '(']

其中"[]"内的内容代表需要满足的条件，即你选择的子括号序列中所有右括号在原序列中的下标和减去所有左括号在原序列中的下标和。

现在有qq次修改操作: pos c，即 seqpos:=cseq_{pos} := c 。

你需要在每次修改操作后输出一个整数，代表在这次修改后你能取出的优美度最大的合法子序列的优美度。

请注意，每次修改操作会实际地修改括号序列。

输入格式

第一行，两个整数 n,q(1≤n≤2⋅105;1≤q≤2⋅105)n,q(1\le n \le 2·10^5;1\le q \le 2·10^5)代表初始时括号序列的长度和修改操作的次数。

第二行，一个长度为nn括号序列，不保证该括号序列是匹配的括号序列。

接下来连续的qq行，每行两个整数 pos,c(1≤pos≤n;c是左括号或右括号)pos,c(1\le pos\le n;c是左括号或右括号)，代表一次操作。

输出格式

共qq行，在每次操作后能输出可以取出的合法的优美度最大的子序列的优美度，如果取不出任何的合法的子序列，输出0。

样例

输入样例：

5 2
())))
1 )
2 (

输出样例：

0
3

样例解释：
第一次修改后，括号序列变为)))))，选不出任何合法子序列。
第二次修改后，括号序列变为)()))，选择下标22和55的括号作为当前子序列。