33OJ
登录 注册

#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 (, AA, and ) in this order for some correct parenthesis sequence AA.
  • A string obtained by concatenating AA and BB in this order, where AA and BB are nonempty correct parenthesis sequences.

Let nn be a positive integer. For an integer sequence w=(w1,w2,…,w2n)w=(w_1,w_2,\ldots,w_{2n}) of length 2n2n, define f(w)f(w) as follows.

For a correct parenthesis sequence s=s1s2…s2ns=s_1s_2\ldots s_{2n} of length 2n2n, define its score w(s)w(s) with respect to ww as the sum of wiw_i over all ii (1≤i≤2n1\le i\le 2n) such that sis_i is (. Let f(w)f(w) be the maximum value of w(s)w(s) over all correct parenthesis sequences ss of length 2n2n.

You are given a positive integer QQ. Initially, the integer sequence WW is empty.

Process QQ queries in order. In the ii-th query, you are given integers ti,xi,yit_i,x_i,y_i. Here, tit_i is one of 1,2,31,2,3 and indicates the following:

  • If ti=1t_i=1: prepend xix_i to WW, and then prepend yiy_i to WW.
  • If ti=2t_i=2: prepend xix_i to WW, and then append yiy_i to WW.
  • If ti=3t_i=3: append xix_i to WW, and then append yiy_i to WW.

For each query, find f(W)f(W) 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 TT (1≤T≤1051\le T\le 10^5), the number of test cases. Each of the TT 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 QQ (1≤Q≤4×1051\le Q\le 4\times 10^5) represents the number of queries.

For each integer ii (1≤i≤Q1\le i\le Q), the integers ti,xi,yit_i,x_i,y_i represent the contents of the query. Here, tit_i is one of 1,2,31,2,3, and ∣xi∣,∣yi∣≤107|x_i|,|y_i|\le 10^7.

The sum of QQ over all test cases does not exceed 4×1054\times 10^5.

Output Format

For each of the TT test cases, print QQ lines. The ii-th line should contain f(W)f(W) after WW has been modified by the ii-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