# **Ghi chú** Bài 1, 2, 3 là 3 bài khối 10 Bài 2, 3, 4 là 3 bài khối 11 # **Bài 1. Dữ liệu** Dữ liệu tài chính của một công ty trong $n$ ngày được biểu diễn bằng một dãy số $t_1, t_2, \ldots, t_n$, trong đó $t_i(1 \leq i \leq n)$ là lượng tiền thu về của ngày thứ $i$. Lãnh đạo công ty thường xuyên yêu cầu thống kê số liệu về tổng tiền lớn nhất thu được của hai ngày liên tiếp trong các ngày từ ngày $L$ đến ngày $R(L<R)$, nghĩa là cần tìm giá trị lớn nhất trong các giá trị $\left(t_i+t_{i+1}\right)$ với $L \leq i<R$. Một nhân viên đã truy cập trái phép dữ liệu của công ty và trước mỗi lần lãnh đạo công ty yêu cầu thống kê số liệu, nhân viên sẽ tìm cách đảo ngược một đoạn dữ liệu nào đó trong các ngày từ ngày $L$ đến ngày $R$ với mục đích khi thống kê dữ liệu trong đoạn từ ngày $L$ đến ngày $R$ thì giá trị trả về càng lớn càng tốt. Vi dụ, nếu đảo ngược đoạn từ ngày $i$ đến ngày $j$ $(1 \leq L \leq i \leq j \leq R \leq n)$ trên dữ liệu ban đầu $t_1, t_2, \ldots, t_i, t_{i+1}, \ldots, t_j, \ldots, t_n$ thì dữ liệu thay đổi là $t_1, t_2, \ldots, t_j, t_{j-1}, \ldots, t_i, \ldots, t_n$. Sau khi thống kê số liệu xong, người này sẽ lại thay đổi dữ liệu như ban đầu. **Yêu cầu:** Cho biết dữ liệu ban đầu là $t_1, t_2, \ldots, t_n$ và $q$ lần yêu cầu thống kê dữ liệu, hãy cho biết số liệu thống kê trả về khi bị can thiệp vào dữ liệu. **Dữ liệu:** Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng: - Dòng đầu chứa hai số nguyên dương $n, q$; - Dòng thứ hai chứa $n$ số nguyên không âm $t_1, t_2, \ldots, t_n\left(t_i \leq 10^9\right)$; - Dòng thứ $k(1 \leq k \leq q)$ trong $q$ dòng sau, mỗi dòng chứa hai số nguyên mô tà yêu cầu thống kê dữ liệu $L, R(1 \leq L<R \leq n)$. **Kết quả:** Ghi ra thiết bị ra chuẩn (màn hình) gồm $q$ dòng, mỗi dòng chứa một số nguyên là giá trị mà lãnh đạo công ty nhận được khi yêu cầu thống kê dữ liệu tương ứng trong file dữ liệu vào. | Input | Output | |---------------------|--------| | 5 2 <br/> 5 2 3 1 3 <br/> 1 5 <br/> 4 5| 8 <br/> 4 | **Giải thích** Với yêu cầu thống kê thứ nhất, đảo ngược đoạn từ ngày 1 đến ngày 2 đề có dữ liệu mới: 2 **5 3** 1 3, kết quả thống kê được là 8. Với yêu cầu thống kê thứ hai, đảo ngược đoạn từ ngày 4 đến ngày 5 để có dữ liệu mới 5 2 3 **3 1**, kết quả thống kê được là 4. **Subtask 1 (50 điểm):** $n, q \leq 50$; **Subtask 2 (25 điểm):** $n, q \leq 5000$; **Subtask 3 (25 điểm):** $n, q \leq 10^5$; # **Bài 2. Bảng số** Cho mảng $A$ gồm $m$ phần tử (các phần tử được đánh số từ 1 đến $m$) và mảng $B$ gồm $n$ phần tử (các phần tử được đánh số từ 1 đến $n$), mỗi phần tử của hai mảng chỉ nhận một trong ba giá trị $-1,0,1$. Tiến hành tạo bảng $C$ kích thước $m \times n$, trong đó phần tử $(i, j)$ nhận giá trị $C[i][j]=A[i] \times B[j]$ với $1 \leq i \leq m$ và $1 \leq j \leq n$. Một bảng con vuông kích thước $s$ của bảng $C$ có phần tử trái trên là $(x, y)$ và phần tử phải dưới là $(x+s-1, y+s-1)$ với $1 \leq x \leq m-s+1$ và $1 \leq y \leq n-s+1$ được gọi là bảng con vuông "cân bằng" nếu: 1) Các phần tử thuộc đường chéo chính đều nhận giá trị bằng 1. Cụ thể, các phần tử $(x, y),(x+1, y+1), \ldots,(x+s-1, y+s-1)$ có giá trị bằng 1. 2) Tổng tất các các phần tử trong bảng con vuông bằng 0. **Yêu cầu:** Cho hai mảng $A$ và $B$, đếm số bảng con vuông "cân bằng" trong bảng $C$. **Dữ liệu:** Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng: - Dòng đầu chứa hai số nguyên dương $m, n$; - Dòng thứ hai gồm $m$ số mô tả mảng $A$; - Dòng thứ ba gồm $n$ số mô tả mảng $B$. **Kết quả:** Ghi ra thiết bị ra chuẩn (màn hình) một dòng chứa một số là số bảng con vuông "cân bằng" trong bảng $C$. | Input | Output | |---------------------|--------| | 3 4 <br/> 1 -1 1<br/> 1 0 -1 1 | 1 | **Giải thích** ![](https://hackmd.io/_uploads/Byl868-52.png) Chỉ có duy nhất 1 bảng con vuông "cân bằng" là bảng con kích thước 2 có phần tử trái trên là (2,3) (Hình vẽ) **Subtask 1 (20 điểm):** $m, n \leq 30$; **Subtask 2 (30 điểm):** $m, n \leq 300$; **Subtask 3 (30 điểm):** $m, n \leq 1000$; **Subtask 4 (20 điểm):** $m \times n \leq 5 \times 10^6$. # **Bài 3. Cứu hộ** Vũ trụ $\mathrm{Z}$ có $n$ hành tinh, các hành tinh được đánh số từ 1 đến $n$. Một hệ thống gồm $m$ đường dịch chuyển, đường dịch chuyển thứ $k(1 \leq k \leq m)$ sẽ giúp di chuyển từ hành tinh $i_k$ đến hành tinh $j_k$ và mất chi phí là $e\left(i_k, j_k\right)$. Một vụ nổ trong vũ trụ đã làm ảnh hưởng lớn đến tất cả các hành tinh, trừ hành tinh số 1. Hành tinh số 1 lên kế hoạch cứu hộ cho $n-1$ hành tinh còn lại. Các nhà khoa học ở hành tinh số 1 đã tìm ra cách di chuyển giúp đội cứu hộ có thể di chuyển đến một hành tinh khác với chi phí nhỏ hơn. Cụ thể, với số nguyên không âm $a$ mà các nhà khoa học thiết đặt, giả sử đội cứu hộ lần lượt di chuyển qua dãy gồm $p$ hành tinh $1=x_1, x_2, \ldots, x_p$. Như vậy, đội cứu hộ sẽ phải sử dụng $p-1$ đường dịch chuyển, gọi $s_1$ là tổng chi phí của $p-1$ đường dịch chuyển, gọi $r_1$ là tổng chi phí của $a$ đường dịch chuyển có chi phí lớn nhất trong $p-1$ đường dịch chuyển (nếu $a>p-1$ thì tính tổng chi phí của $p-1$ đường dịch chuyển), khi đó đội cứu hộ sẽ mất chi phí là $s_1-r_1$. Về phía các hành tinh, các nhà khoa học cũng đã tính toán ra số nguyên không âm $b$ dựa trên mức độ ảnh hưởng của vụ nổ để xác định được chi phí di chuyển của cư dân. Cụ thể, nếu cư dân hành tinh $i$ phải di chuyển qua dãy gồm $q$ hành tinh $i=y_1, y_2, \ldots, y_q$, gọi $s_2$ là tổng chi phí của $q-1$ đường dịch chuyển, gọi $r_2$ là tổng chi phí của $b$ đường dịch chuyển có chi phí nhò nhất trong $q-1$ đường dịch chuyển (nếu $b>q-1$ thì tính tổng chi phí của $q-1$ đường dịch chuyển), khi đó cư dân sẽ mất chi phí là $s_2+r_2$. Chi phí để đội cứu hộ gặp được cư dân của hành tinh $i$ là tổng chi phí di chuyển của đội cứu hộ cộng với tổng chi phí của cư dân hành tinh $i$ di chuyển đề họ gặp được nhau. **Yêu cầu:** Với mỗi hành tinh $i(2 \leq i \leq n)$, hãy tính chi phí nhỏ nhất để đội cứu hộ xuất phát từ hành tinh 1 có thể gặp cư dân của hành tỉnh $i$. **Dữ liệu:** Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng: - Dòng đầu chứa bốn số $n, m, a, b$; - Dòng thứ $k(1 \leq k \leq m)$ trong $m$ dòng tiếp theo chứa ba số nguyên dương $i_k, j_k, e\left(i_k, j_k\right)$, trong đó $1 \leq i_k \neq j_k \leq n$ và $e\left(i_k, j_k\right) \leq 10^9$. Dữ liệu đảm bảo từ hành tinh $i$ không có quá một đường dịch chuyển tới $j$ và không tới chính nó. **Kết quả:** Ghi ra thiết bị ra chuẩn (màn hình) gồm một dòng chứa $n-1$, số thứ $i$ số là chi phí nhỏ nhất để đội cứu hộ có thể gặp cư dân của hành tinh $i+1$, nếu đội cứu hộ không thể gặp được cư dân thì đưa ra số -1 tương ứng. | Input | Output | |---------------------|--------| |4 4 1 1 <br/> 1 2 1 <br/> 2 3 2<br/>3 4 3<br/>4 2 1 | 0 1 2 | ![](https://hackmd.io/_uploads/HyHdDXZch.png) **Subtask 1 (25 điểm):** $n \leq 100 ; m \leq 1000 ; a=b=0$; **Subtask 2 (25 điểm):** $n \leq 100 ; m \leq 1000 ; a=b=1$; **Subtask 3 (25 diểm):** $n \leq 10^5 ; m \leq 10^5 ; a=b=0$; **Subtask 4 (25 điểm):** $n \leq 10^5 ; m \leq 10^5 ; 0 \leq a, b \leq 3$; # **Bài 4. Thay đổi dữ liệu** Dữ liệu tài chính của một công ty trong $n$ ngày được biểu diễn bằng một dãy số $t_1, t_2, \ldots, t_n$, trong đó $t_i(1 \leq i \leq n)$ là dữ liệu cho ngày thứ $i$, nếu $t_i \geq 0$ tức là ngày $i$ công ty thu về $t_i$ đồng, ngược lại $t_i<0$ tức là ngày $i$ công ty phải chi $\left|t_i\right|$ đồng. Lãnh đạo công ty thường thống kê số liệu về tổng thu chi của một dãy ngày liên tiếp mà có biến động lớn nhất, mức đánh giá biến động từ ngày $L$ đến ngày $R$ được tính bằng $\left|\sum_{i=L}^R t_i\right|$. Một nhân viên đã truy cập trái phép dữ liệu của công ty trước khi lãnh đạo công ty thống kê số liệu, nhân viên đã thay đổi số liệu của một dãy các ngày liên tiếp từ ngày $u$ đến ngày $v(1 \leq u \leq v \leq n)$ một lượng $c$, cụ thể với ngày $i(u \leq i \leq v)$ giá trị $t_i$ được thay đổi bằng $t_l+c$. Sau khi thống kê số liệu xong, nhân viên này sẽ lại thay đổi dữ liệu như ban đầu. **Yêu cầu:** Cho biết dữ liệu ban đầu là $t_1, t_2, \ldots, t_n$ và $q$ giả định thay đổi số liệu, với mỗi giả định hãy cho biết giá trị $\left|\sum_{i=L}^R t_i\right|$ lớn nhất với $1 \leq L \leq R \leq n$. **Dữ liệu:** Vào từ thiết bị vào chuẩn (bàn phím) có khuôn dạng - Dòng đầu chứa hai số nguyên dương $n, q$; - Dòng thứ hai chứa $n$ số nguyên $t_1, t_2, \ldots, t_n\left(\left|t_l\right| \leq 10^9\right)$; - Dòng thứ $k(1 \leq k \leq q)$ trong $q$ dòng sau, mỗi dòng chứa ba số nguyên mô tả giả định thay đổi số liệu $u, v, c\left(1 \leq u \leq v \leq n ;|c| \leq 10^9\right)$. **Kết quả:** Ghì ra thiết bị ra chuẩn (màn hình) gồm $q$ dòng, mỗi dòng chứa một số nguyên 1 giả trì ma lãnh đạo công ty thống kê được tương ứng với giả định trong file dữ liệu vào. | Input | Output | |---------------------|--------| |5 2 <br/> 1 -1 2 1 1 <br/> 2 2 -2 <br/> 2 4 -2 | 5 <br/> 4 | **Giải thích** Dữ liệu thay đổi theo giả định thứ nhất: 1 -3 2 1 1, kết quà thống kê đưọc là 4 (đoạn từ 3 đến 5). Dữ liệu thay đổi theo giả định thứ hai: 1 -3 0 -1 1, kết quả thống kê được là 4 (đoạn từ 2 đến 4). **Subtask 1 (15 điểm):** $n, q \leq 20$; **Subtask 2 (15 điểm):** $n, q \leq 5000$; **Subtask 3 (20 điểm):** $n, q \leq 10^5$ và cả $q$ giả định có $v-u \leq 20$; **Subtask 4 (20 điểm):** $n, q \leq 10^5$ và số cặp $(u, v)$ khác nhau trong $q$ giả định không quá 20 cặp; **Subtask 5 (20 điểm):** $n, q \leq 10^5$.