B - Remove Median Operations Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) および，長さ M の整数列 B=(B_1,B_2,\ldots,B_M) が与えられます．ここで N は偶数です．

Q 個のクエリが与えられます．q 個目のクエリの情報は整数の 3 つ組 (t_q,i_q,x_q) として与えられ，その内容は以下の通りです．

  • t_q=1 の場合：このとき 1\leq i_q\leq N である．このクエリでは A_{i_q} を x_q に変更する．
  • t_q=2 の場合：このとき 1\leq i_q\leq M である．このクエリでは B_{i_q} を x_q に変更する．

クエリを処理するたびに，次の小問題の答を求めてください．

多重集合 X を X=\lbrace A_1,A_2,\ldots,A_N\rbrace で初期化します． j=1,2,\ldots,M に対して次の操作を行います：

  • X に B_j を挿入する．その後，X の中央値を X からひとつ削除する．

すべての操作が終了したときの X の要素の総和を求めてください．

中央値とは

N が偶数であるとき，N+1 個の要素を持つ多重集合 X の中央値とは，X の要素のうち昇順で \left(1+\frac{N}{2}\right) 番目の値です．

例えば X=\lbrace 1, 3, 4, 5, 8\rbrace の中央値は 4，X=\lbrace 2,2,2\rbrace の中央値は 2 です．

本問題において，中央値を考える多重集合は常に要素数が奇数であることに注意してください．

制約

  • 1\leq N,M,Q\leq 2\times 10^5
  • N は偶数．
  • 1\leq A_i\leq 10^9
  • 1\leq B_i\leq 10^9
  • t_q\in\lbrace 1,2\rbrace
  • t_q=1 ならば 1\leq i_q\leq N
  • t_q=2 ならば 1\leq i_q\leq M
  • 1\leq x_q\leq 10^9
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられます．

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

出力

Q 行出力してください．q 行目には，q 個目のクエリを処理した直後における小問題の答を出力してください．

入力例 1

4 2 2
5 1 4 3
1 2
1 3 3
2 1 5

出力例 1

10
13

まず 1 個目のクエリによって，A=(5,1,3,3), B=(1,2) となります．この場合，小問題の操作は次のように進行します．

  • X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace で初期化される．
  • X に B_1=1 を挿入し，X=\lbrace 1,1,3,3,5\rbrace となる．その後，X の中央値をひとつ削除して X=\lbrace 1,1,3,5\rbrace となる．
  • X に B_2=2 を挿入し，X=\lbrace 1,1,2,3,5\rbrace となる．その後，X の中央値をひとつ削除して X=\lbrace 1,1,3,5\rbrace となる．

すべての操作が終了した時点での X の要素の総和は 1+1+3+5=10 です．

次に 2 個目のクエリによって，A=(5,1,3,3), B=(5,2) となります．この場合，小問題の操作は次のように進行します．

  • X=\lbrace 5,1,3,3\rbrace=\lbrace 1,3,3,5\rbrace で初期化される．
  • X に B_1=5 を挿入し，X=\lbrace 1,3,3,5,5\rbrace となる．その後，X の中央値をひとつ削除して X=\lbrace 1,3,5,5\rbrace となる．
  • X に B_2=2 を挿入し，X=\lbrace 1,2,3,5,5\rbrace となる．その後，X の中央値をひとつ削除して X=\lbrace 1,2,5,5\rbrace となる．

すべての操作が終了した時点での X の要素の総和は 1+2+5+5=13 です．

入力例 2

6 7 5
7 1 2 5 5 3
4 2 5 1 3 3 8
2 1 3
2 7 1
1 3 6
2 4 2
1 5 1

出力例 2

24
20
21
22
21

Score : 600 points

Problem Statement

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.

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.

Input

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

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

Sample Input 1

4 2 2
5 1 4 3
1 2
1 3 3
2 1 5

Sample Output 1

10
13

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.

Sample Input 2

6 7 5
7 1 2 5 5 3
4 2 5 1 3 3 8
2 1 3
2 7 1
1 3 6
2 4 2
1 5 1

Sample Output 2

24
20
21
22
21