TopCoder

User's AC Ratio

27.3% (3/11)

Submission's AC Ratio

28.6% (12/42)

Tags

Description

小七在施展完變身魔法後,與她的好朋友小皮一起去爬山。
小皮與小七都是登山愛好者,兩人曾經爬過大大小小的山,今天因為兩人相距太遠了,所以他們決定同時爬不同的山,小皮爬 A 山,小七則爬 B 山。

A 山共有 n 個階梯,第 i1in)階的海拔為 ai 公尺,並且海拔是嚴格遞增的,也就是 ai<ai+11i<n)。
B 山共有 m 個階梯,第 j1jm)階的海拔為 bj 公尺,並且海拔也是嚴格遞增的,也就是 bj<bj+11j<m)。

兩人在時刻 t=1 時都在所處山脈的第 1 階,小皮的目標是爬到 A 山的第 n 階,小七則想要爬到 B 山的第 m 階。
為了有同時爬山的感覺,兩人邊爬山時會邊通話,從 t=1 開始,每經過一個時刻,兩人會做以下的事情:

  • 若小皮還沒到達 A 山的第 n 階,小七也還沒到達 B 山的第 m 階,那兩人可以決定讓其中一人移動到下一階,也就是讓小皮從第 i 階移動到第 i+1 階,或是讓小七從第 j 階移動到第 j+1 階,另外一人則留在原本的階梯。
  • 若其中一人已經到達山脈的最後一階了,則讓另外一人移動到下一階:例如當小七已經在 B 山的第 m 階了,那就讓小皮從第 i 階移動到第 i+1 階。

t=n+m1 時,小皮會在 A 山的第 n 階,小七會在 B 山的第 m 階,兩人此時不再移動。

經過上述兩人一連串的決定後,小皮在時刻 t1tn+m1)會位於 A 山的第 pt 階,小七則會位於 B 山的第 qt 階。
兩人在同一時刻的海拔差距越大,違和感就會越大,違和感的計算方式為兩人海拔差距的平方值,在時刻 t 的違和感可以表示成 (aptbqt)2

兩人的目標是讓 n+m1 個時刻的總違和感最小,也就是 t=1n+m1(aptbqt)2 最小。

令人驚訝的是,地殼的變動可能會影響階梯的高度,依序有 k 個地殼變動發生,每個地殼變動的形式可能為 1 x h2 y h

  • 若形式為 1 x h,代表這次的地殼變動會讓 A 山第 x 個階梯的海拔變成 h,也就是使 ax 變成 h
  • 若形式為 2 y h,代表這次的地殼變動會讓 B 山第 y 個階梯的海拔變成 h,也就是使 by 變成 h
  • 地殼變動的影響是永久的,也就是說當 axby 變成 h 後,除非之後的地殼變動影響到同一個階梯,否則此階梯的海拔會維持在 h
  • 每次地殼變動完,A 山、B 山階梯的海拔仍然保持嚴格遞增,也就是維持 ai<ai+11i<n)與 bj<bj+11j<m)。(不然就不叫爬山了)

請你在每次地殼變動完,輸出小皮與小七在經過一連串的決定爬到最後一階後,總違和感 t=1n+m1(aptbqt)2 最小可以是多少。

Input Format

第一行有三個正整數 n,m,k,分別代表 A 山階梯數、B 山階梯數、地殼變動發生幾次。
第二行有 n 個嚴格遞增的正整數 a1an,代表 A 山階梯的海拔。
第三行有 m 個嚴格遞增的正整數 b1bm,代表 B 山階梯的海拔。

接下來 k 行,每行輸入的三個正整數形式可能為 1 x h2 y h,代表此次地殼變動將 A 山第 x 階或 B 山第 y 階的海拔變成 h 了。

對於所有測試資料:

  • 2n,m3×105
  • 1k105
  • 1ai,bj2×1061in,1jm
  • ai<ai+11i<n
  • bj<bj+11j<m
  • 1xn,1ym
  • 1h2×106
  • 保證每次地殼變動完 a,b 陣列皆保持嚴格遞增

Output Format

每次地殼變動完,輸出一整數,代表小皮與小七在經過一連串的決定爬到最後一階後,總違和感 t=1n+m1(aptbqt)2 最小可以是多少。

Sample Input 1

2 2 2
5 6
1 4
2 2 7
1 1 1

Sample Output 1

21
26

Sample Input 2

4 9 5
7 8 12 20
1 5 8 14 15 18 20 23 24
2 2 3
2 8 22
1 2 11
1 4 18
1 1 10

Sample Output 2

136
131
133
149
230

Hints

在範例測資一,初始 a=[5,6],b=[1,4]

經過第 1 次的地殼變動,a=[5,6],b=[1,7],此時 p=[1,1,2],q=[1,2,2]
會有最小的總違和感: t=1n+m1(aptbqt)2=(a1b1)2+(a1b2)2+(a2b2)2=42+(2)2+(1)2=21

經過第 2 次的地殼變動,a=[1,6],b=[1,7],此時 p=[1,2,2],q=[1,1,2]
會有最小的總違和感: t=1n+m1(aptbqt)2=(a1b1)2+(a2b1)2+(a2b2)2=02+52+(1)2=26

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~4 n,m,k10 12
3 0~10 n,m,k400 11
4 0~16 n,m,k5000 26
5 0, 2, 17~20 n=2 15
6 21~34, 55~56 地殼變動形式只會是 1 x h 17
7 0~58 無其他限制 19

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3 4 5 7
1 3000 262144 65536 1 2 3 4 7
2 3000 262144 65536 2 3 4 5 7
3 3000 262144 65536 2 3 4 7
4 3000 262144 65536 2 3 4 7
5 3000 262144 65536 3 4 7
6 3000 262144 65536 3 4 7
7 3000 262144 65536 3 4 7
8 3000 262144 65536 3 4 7
9 3000 262144 65536 3 4 7
10 3000 262144 65536 3 4 7
11 3000 262144 65536 4 7
12 3000 262144 65536 4 7
13 3000 262144 65536 4 7
14 3000 262144 65536 4 7
15 3000 262144 65536 4 7
16 3000 262144 65536 4 7
17 3000 262144 65536 5 7
18 3000 262144 65536 5 7
19 3000 262144 65536 5 7
20 3000 262144 65536 5 7
21 3000 262144 65536 6 7
22 3000 262144 65536 6 7
23 3000 262144 65536 6 7
24 3000 262144 65536 6 7
25 3000 262144 65536 6 7
26 3000 262144 65536 6 7
27 3000 262144 65536 6 7
28 3000 262144 65536 6 7
29 3000 262144 65536 6 7
30 3000 262144 65536 6 7
31 3000 262144 65536 6 7
32 3000 262144 65536 6 7
33 3000 262144 65536 6 7
34 3000 262144 65536 6 7
35 3000 262144 65536 7
36 3000 262144 65536 7
37 3000 262144 65536 7
38 3000 262144 65536 7
39 3000 262144 65536 7
40 3000 262144 65536 7
41 3000 262144 65536 7
42 3000 262144 65536 7
43 3000 262144 65536 7
44 3000 262144 65536 7
45 3000 262144 65536 7
46 3000 262144 65536 7
47 3000 262144 65536 7
48 3000 262144 65536 7
49 3000 262144 65536 7
50 3000 262144 65536 7
51 3000 262144 65536 7
52 3000 262144 65536 7
53 3000 262144 65536 7
54 3000 262144 65536 7
55 3000 262144 65536 6 7
56 3000 262144 65536 6 7
57 3000 262144 65536 7
58 3000 262144 65536 7