#P17543. [JAG 2026 Summer Camp #2] Deque Bracket Optimization
[JAG 2026 Summer Camp #2] Deque Bracket Optimization
题目描述
满足下列条件之一的字符串被定义为合法括号序列。
- 空字符串。
- 对于某个合法括号序列 ,将
(、 和)按此顺序拼接得到的字符串。 - 将两个非空合法括号序列 和 按此顺序拼接得到的字符串。
设 为正整数。对于长度为 的整数序列 ,定义 如下。
对于长度为 的合法括号序列 ,定义它相对于 的得分 为所有满足 为 ( 的下标 ()对应的 之和。令 为所有长度为 的合法括号序列 的 的最大值。
给定一个正整数 。初始时,整数序列 为空。
依次处理 次询问。第 次询问给出整数 。其中 为 之一,其含义如下:
- 若 :先在 的开头插入 ,再在 的开头插入 。
- 若 :先在 的开头插入 ,再在 的末尾插入 。
- 若 :先在 的末尾插入 ,再在 的末尾插入 。
对于每次询问,求处理完该询问后的 。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 (),表示测试数据组数。每组测试数据的格式如下:
Q
t_1 x_1 y_1
t_2 x_2 y_2
...
t_Q x_Q y_Q
整数 ()表示询问次数。
对于每个整数 (),整数 表示询问的内容。其中 为 之一,且 。
所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,输出 行。第 行包含 经过第 次询问修改后的 。
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