Bài 3: Rừng cây "RC.*" (draft)

Trong một rừng cây có $N$ cây, các cây được đánh số từ $1$ đến $N$, có tất cả $M$ loại cây.
Cây thứ $i$ thuộc loại $B_i ;(1 \leq B_i \leq M).$

Chênh lệch chiều cao của rừng cây được tính theo công thức: tổng các giá trị tuyệt đối của hiệu chiều cao giữa tất cả các cặp cây khác loại nhau.
Nghĩa là chênh lệch chiều cao của rừng cây được tính bằng công thức

$\sum |C_i - C_j|\forall 1 \le i < j \le N, ; B_i \ne B_j$

Yêu cầu: Hãy tính chênh lệch chiều cao của rừng cây đã cho.

Dữ liệu vào từ tệp văn bản RC.INP

Dòng đầu tiên gồm hai số nguyên dương $N$ và $M$ $(1\le N \le 10^5;M\le N)$

Dòng thứ hai gồm $N$ số nguyên dương $B_i$ $(1\le B_i\le M)$

Dòng thứ ba gồm $N$ số nguyên dương $C_i$ $(1\le C_i\le 10^9)$ Kết quả ghi ra tệp văn bản RC.OUT

Một số nguyên là chênh lệch chiều cao của rừng cây đã cho

Ví dụ

RC.INP
5 3
1 2 3 2 1
3 4 5 6 7
RC.OUT
14
Giải thích Chiều cao của rừng cây là $|C_1 - C_2| + |C_1 - C_3| + |C_1 - C_4| + |C_2 - C_3| + |C_2 - C_5| + |C_3 - C_4| + |C_3 - C_5| + |C_4 - C_5|\ = |3 - 4| + |3 - 5| + |3 - 6| + |4 - 5| + |4 - 7| + |5 - 6| + |5 - 7| + |6 - 7| \ = 1 + 2 + 3 + 1 + 3 + 1 + 2 + 1\ = 14$

Rằng buộc:

Có 60% số test ứng với 60% số điểm có $1\le N \le 1000; 1 \le C_i \le 200;$

20% số test ứng với 20% số điểm có $1\le N \le 10^5; M = 2;$

20% số test còn lại ứng với 20% số điểm không có rằng buộc thêm

Case 1 $N \le 1000;M \ne 2$

Tính tổng kết quả của mỗi một cây, tìm khoảng cách đến các cây khác i != j, với điều kiện B[i] != B[j]

Dộ phức tạp: $O(n^2)$

r=0
for i in range(N):
  for j in range(i):
    if b[i] == b[j]: continue
      r+=abs(c[i]-c[j])

Case 2 $N \le 10^5;M = 2$

Đầu tiên, đặt các cây loại 1 và 2 vào 2 dãy, a và b (cho rằng b là dãy dài hơn a để tối ưu nhất)

Sau đó, sort cả hai dãy a và b luôn

Với mỗi vị trí cây a, kiểm tra độ dài theo những trường hợp sau

Trường hợp 1: $a_i$ lớn hơn hoặc bé hơn mọi phần tử trong mảng `b`

Luận: Tổng khoảng cách từ điểm đầu tiên của dãy đã sắp xếp đến mọi điểm là tổng các giá trị của dãy, với mỗi phần tử trừ đi giá trị bé nhất của khoảng

b.sort()
for a[i] in a:
  tl=sum(b)-b[0]*len(b) # Lưu ý len(b) != n
  if ai < b[0]:
    t+=abs(a[i]-b[0])+tl
  elif ai > b[-1]:
    t+=abs(a[i]-b[-1])+tl
  ... # Trường hợp 2

Trường hợp 2.0: $a_i$ là một phần tử trong mảng `b`

_{hay tức là, có hai cây cao bằng nhau, nhưng khác loại}

Sử dụng binary search để tim ra vị trí của $a_i$ đang xét.

Mảng da là khoảng cách giữa các điểm trong tập hợp đã được sắp xếp

Luận: Trong một tập hợp đã sắp xếp, với một điểm đang xét có giá trị là một phần tử của mảng, ta có:

$\sum_{}{l} \Delta a_x$ là tổng khoảng cách từ bên trái mảng đến $a_i$
$\sum_{|a|}{l} \Delta a_x$ là tổng khoảng cách từ bên phải mảng đến $a_i$, với thứ tự phần tử ngược

Trường hợp 2.1: $a_i$ nằm giữa hai phần tử trong mảng

Vẫn sử dụng binary search, nhưng tìm khoảng tuyệt đối cho hai phần tử gần nhau nhất.

Xét điểm gần nhất về bên trái là l và bên phải là r

$\sum_{x=0}{l} \Delta x*a_x$ là tổng khoảng cách từ bên trái mảng đến $l$
$\sum_{y=|a|}{r} \Delta x*a_y$ là tổng khoảng cách từ bên phải mảng đến $r$
Sau đó, tính $|l-a_i|(x+1)+|r-a_i|(y+1)$

Trường hợp 2: Tổng quát

Ở 2.1 chúng ta đã tính khoảng cách từ điểm $a_i$ đến $l$, nhưng với $l=r=a_i$ khi $a_i$ là phần tử trong mảng nên không thực sự cần thiết

hUwUtao/Bai3.md