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
Test 1
Input
7 3
5 3 1 4 2 6 5
2 4
3 5
6 3Output
3
3
4Note
- Với truy vấn đầu tiên, dãy \(A\) là \([5, 4, 1, 4, 2, 6, 5]\). Một trong những dãy con có độ dài \(3\) là \(A_3, A_5, A_7\).
- Với truy vấn thứ hai, dãy \(A\) là \([5, 3, 5, 4, 2, 6, 5]\). Một trong những dãy con có độ dài \(3\) là \(A_2, A_4, A_6\).
- Với truy vấn thứ hai, dãy \(A\) là \([5, 3, 1, 4, 2, 3, 5]\). Một trong những dãy con có độ dài \(4\) là \(A_3, A_5, A_6, A_7\).
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.
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.