Bài tập

GSFOS chuẩn bị thám hiểm một pháo đài cổ. Pháo đài có \(n\) phòng, nối liên thông với nhau bằng \(n-1\) đường hầm. Đường hầm thứ \(i\) nối hai phòng \(u_i\) và \(v_i\) với nhau và có độ dài \(w_i\).

Để lên kế hoạch thám hiểm, GSFOS cần chọn một đường đi nối hai phòng \(u\) và \(v\) bất kỳ. Gọi tập các đỉnh trên đường này là
\(S=\{u,x_1,x_2,\dots,x_k,v\}\),
theo thứ tự sao cho có cạnh nối lần lượt \(u\text{--}x_1\text{--}x_2\text{--}\dots\text{--}x_k\text{--}v\). Độ dài của đường đi từ \(u\) tới \(v\) được ký hiệu là \(\operatorname{value}(u,v)\).

Sau khi chọn đường \(S\), GSFOS chọn một phòng \(y\) không thuộc \(S\). Định nghĩa

trong đó \(\operatorname{dist}(y,z)\) là khoảng cách giữa hai phòng \(y\) và \(z\). Nếu không tồn tại phòng \(y\) phù hợp (tức mọi phòng đều thuộc \(S\)) thì ta lấy \(\operatorname{distance}(y,S)=0\). Nếu không thể chọn được hai phòng \(u,v\) để tạo thành đường đi thì \(\operatorname{value}(u,v)=0\).

Giá trị của cách chọn là

Hãy tính giá trị lớn nhất có thể đạt được khi tối ưu hóa cả đường \(S\) (tức chọn \(u,v\)) và phòng \(y\).

Input

• Dòng đầu chứa một số nguyên dương \(n\) (\(1\le n \le 3\cdot 10^5\)) --- số phòng trong pháo đài.
• \(n-1\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(u, v, w\) (\(1\le u,v\le n\), \(1\le w\le 10^3\)) --- có một đường hầm giữa phòng \(u\) và \(v\) với độ dài \(w\).

Output

• In ra một số nguyên duy nhất --- giá trị lớn nhất của \(\operatorname{value}(u,v)\times \operatorname{distance}(y,S)\) có thể đạt được.

Example

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

15

Scoring

• Subtask 1 (15%): \(n \le 100\).
• Subtask 2 (20%): \(n \le 3000\).
• Subtask 3 (30%): Mỗi phòng có tối đa \(3\) đường hầm kề.
• Subtask 4 (35%): Không có ràng buộc gì thêm.

Trong một vùng không gian nào đó trong vũ trụ, các tín hiệu năng lượng thu thập từ dãy vệ tinh \(A_1, A_2, \dots, A_N\) được lưu trữ như một chuỗi năng lượng.

Chuỗi này đang được theo dõi để xác định chuỗi con năng lượng tăng ổn định nhất --- chính là chuỗi con dài nhất mà mỗi phần tử đều có năng lượng lớn hơn phần tử trước nó. Ta gọi đó là chuỗi năng lượng tăng. Nói một cách cụ thể hơn, một chuỗi con \(A_{i_1}, A_{i_2}, A_{i_3}, ..., A_{i_k}\) với \(i_1 < i_2 < i_3 < ... < i_k\) được gọi là chuỗi năng lượng tăng khi \(A_{i_1} < A_{i_2} < A_{i_3} < ... < A_{i_k}\).

Tuy nhiên, do tác động của các hố đen không ổn định, trạm điều khiển không gian thực hiện \(Q\) dự đoán, mỗi dự đoán là một mô phỏng việc thay đổi năng lượng tại vị trí \(p_i\) bằng giá trị mới \(x_i\) (một năng lượng giả định từ mô hình AI dự báo) hay gán \(A_{p_i} = x_i\). Nhiệm vụ của bạn là:

Với mỗi dự đoán, giả sử giá trị tại \(A_{p_i}\) bị thay đổi thành \(x_i\), hãy tính lại độ dài chuỗi năng lượng tăng dài nhất (LIS) mới. Lưu ý, mỗi dự đoán là độc lập, sau khi xử lí mỗi dự đoán, chuỗi \(A\) sẽ trở lại chuỗi ban đầu (các phần tử đều không bị thay đổi). Tuy nhiên, nếu trạm điều khiển không gian không đưa ra dự đoán nào (hay \(Q = 0\)), bạn cần phải in ra một dòng duy nhất chính là độ dài lớn nhất của chuỗi năng lượng tăng của chuỗi năng lượng \(A\).

Input

• Dòng đầu tiên chứa hai số nguyên \(N, Q\) \((1 \leq N \leq 3 \times 10^5, 0 \leq Q \leq 3 \times 10^5)\) --- số vệ tinh và số truy vấn.
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) \((1 \leq a_i \leq 10^9)\) --- tín hiệu năng lượng ban đầu từ các vệ tinh.
• \(Q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(p_i, x_i\) \((1 \leq p_i \leq N,\ 1 \leq x_i \leq 10^9)\) --- mô tả truy vấn: giả định thay đổi \(a_{p_i} = x_i\).

Output

In ra \(Q\) dòng tương ứng với yêu cầu bài toán.

Example

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

3
3
4

Scoring

• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q = 0, N \leq 20\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q = 0, N \leq 1000\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q = 0, N \leq 3 \times 10^5\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm có \(Q \leq 20, N \leq 3 \times 10^5\).
• Có \(20\%\) số test tương ứng với \(20\%\) số điểm còn lại không có ràng buộc gì thêm.

Giáo sư 3M vừa mới phát hiện ra sinh vật mới chưa từng xuất hiện trước đây. Sinh vật này rất
kì lạ khi có thể thay đổi mã gen của mình. Mã gen của sinh vật được biển diễn dưới dạng một
dãy các phần tử số nguyên. Được biết trong vòng đời của sinh vật có thể biến đổi duy nhất \(1\)
lần trong đoạn gen từ \(L\) đến \(R\) bằng cách thay đổi các số nguyên trong trên dãy thành \(a_L\).
Giáo sư muốn biết với mã gen đã cho sinh vật này có thể biến đổi thành bao nhiêu mã gen
khác nhau. Các bạn hãy giúp giáo sư 3M nhé.

Input

Vào từ file văn bản GCC.INP:

• Dòng đầu ghi số nguyên dương \(n\) \((1 \leq n \leq 10^6)\)
• Dòng thứ \(2\) ghi \(n\) số nguyên \(a_i\) \((1 \leq |a_i| \leq 10^6)\).

Output

Ghi ra file văn bản GCC.OUT:

• Gồm một số nguyên dương duy nhất là số mã gen khác nhau có thể.

Example

4 1
1 2 3

4

Scoring

• \(10\%\) số test tương ứng với \(10\%\) số điểm của \(n \leq 500\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10^3\), \(1 \leq a_i \leq 9\).
• \(20\%\) số test tương ứng với \(20\%\) số điểm có các phần tử \(a_i\) phân biệt.
• \(20\%\) số test tương ứng với \(20\%\) số điểm của \(n \leq 10000\).
• \(30\%\) số test còn lại tương ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm

Cho dãy số \(a\) gồm \(n\) số nguyên đánh số từ \(1\) đến \(n\). Ban đầu dãy \(a\) gồm toàn số \(0\). Cho \(q\) truy vấn, mỗi truy vấn được cho dưới dạng hai số nguyên \(i\) và \(k\) : tăng \(a_{i}\) lên \(k\) đơn vị, \(a_{i+1}\) lên \(k - 1\) đơn vị,... \(a_{i+k−1}\) lên \(1\) đơn vị.

Hãy in ra dãy \(a\) sau khi thực hiện \(q\) truy vấn này.

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(q\) \((n, q \leq 5 \times 10^5)\).

\(q\) dòng tiếp theo, mỗi dòng tương ứng với một truy vấn là hai số nguyên \(i\) và \(k\) \((1 \leq i \leq n; 1 \leq k \leq n-i+1)\).

Output

Một dòng duy nhất là dãy \(a_{1},a_{2},...,a_{n}\) sau khi thực hiện xong \(q\) truy vấn.

Example

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

12 10 8 6 6 3 2 

Scoring

\(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 1000\).

\(30\%\) số test tương ứng với \(30\%\) số điểm mọi \(k\) trong \(q\) truy vấn bằng nhau.

\(40\%\) số test tương ứng với \(30\%\) số điểm còn lại không có ràng buộc gì thêm.