#P17543. [JAG 2026 Summer Camp #2] Deque Bracket Optimization
[JAG 2026 Summer Camp #2] Deque Bracket Optimization
Problem Description
A string satisfying one of the following conditions is defined as a correct parenthesis sequence.
- The empty string.
- A string obtained by concatenating
(, , and)in this order for some correct parenthesis sequence . - A string obtained by concatenating and in this order, where and are nonempty correct parenthesis sequences.
Let be a positive integer. For an integer sequence of length , define as follows.
For a correct parenthesis sequence of length , define its score with respect to as the sum of over all () such that is (. Let be the maximum value of over all correct parenthesis sequences of length .
You are given a positive integer . Initially, the integer sequence is empty.
Process queries in order. In the -th query, you are given integers . Here, is one of and indicates the following:
- If : prepend to , and then prepend to .
- If : prepend to , and then append to .
- If : append to , and then append to .
For each query, find after the query has been processed.
Input Format
The input consists of one or more test cases. The first line of the input contains an integer (), the number of test cases. Each of the test cases is given in the following format:
Q
t_1 x_1 y_1
t_2 x_2 y_2
...
t_Q x_Q y_Q
The integer () represents the number of queries.
For each integer (), the integers represent the contents of the query. Here, is one of , and .
The sum of over all test cases does not exceed .
Output Format
For each of the test cases, print lines. The -th line should contain after has been modified by the -th query.
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