# Đề thi Bắc Giang PreVOI 2023 - Ngày thi thứ hai

---

# Bức ảnh (PIC)
Alice đã dán một số bức ảnh hình chữ nhật lên bức tường trong phòng làm việc. Mỗi lần dán, Alice luôn dán sao cho các cạnh của bức ảnh song song với trục ngang hoặc dọc của bức tường và ghi lại tọa độ trái dưới, phải trên của bức ảnh. Mỗi bức ảnh có thể bị che một phần hoặc bị che toàn bộ bởi các bức ảnh khác. Nếu chỉ quan tâm đến những phần phủ lên bức tường thì các bức ảnh tạo thành những hình ảnh độc đáo. Sau lúc làm việc căng thẳng, Alice nhìn lên bức tường và tự hỏi, tổng độ dài đường biên của các hình tạo thành là bao nhiêu.

## Yêu cầu
Cho vị trí dán của $n$ bức ảnh, hãy tính tổng độ dài đường biên của các hình tạo thành.
## Input
- Dòng đất tiên chứa số nguyên $n$ $(1 \le n \le 10^5)$ là số bức ảnh được dán lên tường.
- Dòng thứ $i$ $(1 \le i \le n)$ chứa bốn số nguyên $x_i,y_i,u_i,v_i$ $(-10^9 \le x_i < u_i \le 10^9$; $-10^9 \le y_i < v_i \le 10^9)$, trong đó $x_i,y_i$ là tọa độ trái dưới và $u_i,v_i$ là tọa độ phải trên của hình chữ nhật mô tả bức ảnh được dán lên tường.
## Output
Ghi ra một số nguyên là tổng độ dài đường biên của các hình tạo thành.

## Sample Test 1
**Input**

4
0 1 1 2
1 0 2 1
2 1 3 2
1 2 2 3

**Output**

16

## Sample Test 2
**Input**

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

**Output**

228

## Scoring
- Subtask 1 $(30\%)$: $n \le 100$ và $\lvert x_i \rvert,\lvert y_i \rvert, \lvert u_i \rvert, \lvert v_i \rvert \le 10^2$.
- Subtask 2 $(40\%)$: $n \le 5000$ và $\lvert x_i \rvert,\lvert y_i \rvert, \lvert u_i \rvert, \lvert v_i \rvert \le 10^4$.
- Subtask 3 $(30\%)$: Không có ràng buộc gì thêm.

---

# Đổi chỗ (SWAP)

Alice có một dãy số nguyên $a_1, a_2, \dots, a_n$ là một hoán vị của dãy $1,2,\dots,n$. Dãy $a_1, a_2, \dots, a_n$ được gọi là dãy hình nón tại vị trí $k$ $(1 \le k \le n)$ nếu dãy tăng dần từ đầu đến vị trí $k$ và giảm dần từ vị trí $k$ đến $n$, cụ thể: $a_1 < a_2 < \dots < a_{k-1} < a_k > a_{k + 1} > \dots > a_n$.

Alice nhận thấy, với một vị trí $k$ $(1 \le k \le n)$ bất kì luôn có thể thực hiện một dãy thao tác đổi chỗ hai phần tử cạnh nhau để nhận được dãy hình nón tại vị trí $k$, nhưng để thực hiện với ít thao tác nhất thì không dễ dàng.

## Yêu cầu
Với mỗi vị trí $k$ $(1 \le k \le n)$, hãy giúp Alice thực hiện ít thao tác đổi chỗ hai phần tử cạnh nhau nhất để từ dãy ban đầu nhận được dãy hình nón tại vị trí $k$.

## Input
- Dòng đầu tiên chứa số nguyên $n$ $(1 \le n \le 5 \times 10^5)$ là độ dài của dãy hoán vị.
- Dòng thứ hai ghi $n$ số $a_i$ $(1 \le a_i \le n)$ mô tả dãy hoán vị được cho.

## Output
Ghi ra trên một dòng gồm $n$ số nguyên, với số thứ $k$ là số thao tác đổi ít nhất cần sử dụng để nhận được dãy hình nón tại vị trí $k$.

## Sample Test
**Input**

7
1 6 7 2 5 4 3

**Output**

10 4 3 2 4 7 11

## Scoring
- Subtask 1 $(15\%)$: $n \le 8$.
- Subtask 2 $(15\%)$: $n \le 18$.
- Subtask 3 $(20\%)$: $n \le 100$.
- Subtask 4 $(15\%)$: $n \le 500$.
- Subtask 5 $(15\%)$: $n \le 5000$.
- Subtask 6 $(20\%)$: Không có ràng buộc gì thêm.

---

# Khôi phục cây (RESTORE)
Alice đã tạo dữ liệu kiểm thử cho một bài toán liên quan đến đồ thị có dạng cây. Cụ thể, đồ thị dạng cây có $n$ đỉnh, trong đó $1$ là gốc, có $n-1$ cạnh, cạnh thứ $k$ $(1 \le k \le n-1)$, nối hai đỉnh phân biệt $u_k, v_k$ $(1 \le u_k, v_k \le n)$ với trọng số là $w_k$ (chú ý rằng, $w_k$ có thể âm). Tuy nhiên, dữ liệu về các cạnh đã bị mất mà Alice chỉ nhớ được các thông tin như sau:
- Tổng trọng số của tất cả các cạnh bằng $s$.
- Với đỉnh thứ $i$ $(1 < i \le n)$, tổng trọng số các cạnh đi từ đỉnh gốc $1$ xuống đỉnh $i$ bằng $d_i$.

## Yêu cầu
Hãy giúp Alice khôi phục lại cây.

## Input
- Dòng đầu tiên ghi hai số nguyên $n$ và $s$ $(1 \le n \le 2 \times 10^5;$ $0 \le s \le 2 \times 10^5)$.
- Dòng thứ hai chứa $n$ số nguyên $d_i$ $(\lvert d_1 \rvert + \lvert d_2 \rvert + \dots + \lvert d_n \rvert \le 2 \times 10^5)$.

## Output
Gồm $n-1$ dòng, dòng thứ $k$ $(1 \le k \le n - 1)$ chứa ba số nguyên $u_k, v_k, w_k$.

## Sample Test
**Input**

5 2
0 1 -1 0 0

**Output**

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

## Scoring
- Subtask 1 $(20\%)$: $n \le 10$; $s \le 5000$; $\lvert d_1 \rvert + \lvert d_2 \rvert + \dots + \lvert d_n \rvert \le 5000$.
- Subtask 2 $(20\%)$: Tồn tại cây dạng chuỗi thỏa mãn.
- Subtask 3 $(20\%)$: $n \le 1000$; $s \le 5000$; $\lvert d_1 \rvert + \lvert d_2 \rvert + \dots + \lvert d_n \rvert \le 5000$.
- Subtask 4 $(40\%)$: Không có ràng buộc gì thêm.