33OJ
登录 注册

#P17543. [JAG 2026 Summer Camp #2] Deque Bracket Optimization

[JAG 2026 Summer Camp #2] Deque Bracket Optimization

题目描述

满足下列条件之一的字符串被定义为合法括号序列。

  • 空字符串。
  • 对于某个合法括号序列 AA,将 (、AA 和 ) 按此顺序拼接得到的字符串。
  • 将两个非空合法括号序列 AA 和 BB 按此顺序拼接得到的字符串。

设 nn 为正整数。对于长度为 2n2n 的整数序列 w=(w1,w2,…,w2n)w=(w_1,w_2,\ldots,w_{2n}),定义 f(w)f(w) 如下。

对于长度为 2n2n 的合法括号序列 s=s1s2…s2ns=s_1s_2\ldots s_{2n},定义它相对于 ww 的得分 w(s)w(s) 为所有满足 sis_i 为 ( 的下标 ii(1≤i≤2n1\le i\le 2n)对应的 wiw_i 之和。令 f(w)f(w) 为所有长度为 2n2n 的合法括号序列 ss 的 w(s)w(s) 的最大值。

给定一个正整数 QQ。初始时,整数序列 WW 为空。

依次处理 QQ 次询问。第 ii 次询问给出整数 ti,xi,yit_i,x_i,y_i。其中 tit_i 为 1,2,31,2,3 之一,其含义如下:

  • 若 ti=1t_i=1:先在 WW 的开头插入 xix_i,再在 WW 的开头插入 yiy_i。
  • 若 ti=2t_i=2:先在 WW 的开头插入 xix_i,再在 WW 的末尾插入 yiy_i。
  • 若 ti=3t_i=3:先在 WW 的末尾插入 xix_i,再在 WW 的末尾插入 yiy_i。

对于每次询问,求处理完该询问后的 f(W)f(W)。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 TT(1≤T≤1051\le T\le 10^5),表示测试数据组数。每组测试数据的格式如下:

Q
t_1 x_1 y_1
t_2 x_2 y_2
...
t_Q x_Q y_Q

整数 QQ(1≤Q≤4×1051\le Q\le 4\times 10^5)表示询问次数。

对于每个整数 ii(1≤i≤Q1\le i\le Q),整数 ti,xi,yit_i,x_i,y_i 表示询问的内容。其中 tit_i 为 1,2,31,2,3 之一,且 ∣xi∣,∣yi∣≤107|x_i|,|y_i|\le 10^7。

所有测试数据的 QQ 之和不超过 4×1054\times 10^5。

输出格式

对于每组测试数据,输出 QQ 行。第 ii 行包含 WW 经过第 ii 次询问修改后的 f(W)f(W)。

3
4
3 2 3
3 4 5
3 6 7
3 -1 -1
3
1 10 100
2 1 100000
3 10000 1000
1
2 -1234567 7654321
2
6
12
19
100
101
100101
-1234567