AT_arc210_b [ARC210B] Remove Median Operations

You are given an integer sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ and an integer sequence $ B=(B_1,B_2,\ldots,B_M) $ of length $ M $ . Here, $ N $ is **even**. You are given $ Q $ queries. The $ q $ -th query is given as a triple of integers $ (t_q,i_q,x_q) $ , and it does the following. - If $ t_q=1 $ : In this case, $ 1\leq i_q\leq N $ . This query changes $ A_{i_q} $ to $ x_q $ . - If $ t_q=2 $ : In this case, $ 1\leq i_q\leq M $ . This query changes $ B_{i_q} $ to $ x_q $ . After processing each query, find the answer to the following subproblem. > Initialize a multiset $ X $ with $ X=\lbrace A_1,A_2,\ldots,A_N\rbrace $ . For $ j=1,2,\ldots,M $ , perform the following operation: > > - Insert $ B_j $ into $ X $ . Then, remove one median of $ X $ from $ X $ . > > Find the sum of elements in $ X $ when all operations are finished. What is a median?When $ N $ is even, the median of a multiset $ X $ with $ N+1 $ elements is the $ \left(1+\frac{N}{2}\right) $ -th value in ascending order among the elements of $ X $ . For example, the median of $ X=\lbrace 1, 3, 4, 5, 8\rbrace $ is $ 4 $ , and the median of $ X=\lbrace 2,2,2\rbrace $ is $ 2 $ . Note that in this problem, the multiset for which we consider the median always has an odd number of elements.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ Q $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_M $ $ t_1 $ $ i_1 $ $ x_1 $ $ \vdots $ $ t_Q $ $ i_Q $ $ x_Q $

Output $ Q $ lines. The $ q $ -th line should contain the answer to the subproblem immediately after processing the $ q $ -th query.

### Sample Explanation 1 First, the $ 1 $ -st query makes $ A=(5,1,3,3) $ and $ B=(1,2) $ . In this case, the operations in the subproblem proceed as follows. - Initialize $ X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace $ . - Insert $ B_1=1 $ into $ X $ , making $ X=\lbrace 1,1,3,3,5\rbrace $ . Then, remove one median from $ X $ , making $ X=\lbrace 1,1,3,5\rbrace $ . - Insert $ B_2=2 $ into $ X $ , making $ X=\lbrace 1,1,2,3,5\rbrace $ . Then, remove one median from $ X $ , making $ X=\lbrace 1,1,3,5\rbrace $ . The sum of elements in $ X $ when all operations are finished is $ 1+1+3+5=10 $ . Next, the $ 2 $ -nd query makes $ A=(5,1,3,3) $ and $ B=(5,2) $ . In this case, the operations in the subproblem proceed as follows. - Initialize $ X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace $ . - Insert $ B_1=5 $ into $ X $ , making $ X=\lbrace 1,3,3,5,5\rbrace $ . Then, remove one median from $ X $ , making $ X=\lbrace 1,3,5,5\rbrace $ . - Insert $ B_2=2 $ into $ X $ , making $ X=\lbrace 1,2,3,5,5\rbrace $ . Then, remove one median from $ X $ , making $ X=\lbrace 1,2,5,5\rbrace $ . The sum of elements in $ X $ when all operations are finished is $ 1+2+5+5=13 $ . ### Constraints - $ 1\leq N,M,Q\leq 2\times 10^5 $ - $ N $ is even. - $ 1\leq A_i\leq 10^9 $ - $ 1\leq B_i\leq 10^9 $ - $ t_q\in\lbrace 1,2\rbrace $ - If $ t_q=1 $ , then $ 1\leq i_q\leq N $ - If $ t_q=2 $ , then $ 1\leq i_q\leq M $ - $ 1\leq x_q\leq 10^9 $ - All input values are integers.