Nguồn: http://codeforces.com/contest/650/problem/D

Gọi:

• ~l_i~ là độ dài dãy con tăng dài nhất của dãy ban đầu kết thúc tại vị trí ~i~
• ~r_i~ là độ dài dãy con tăng dài nhất của dãy ban đầu bắt đầu tại vị trí ~i~
• ~L~ là độ dài dãy con tăng lớn nhất của dãy ban đầu

Với mỗi truy vấn ~(p, x)~, gọi:

• ~x_1~ là độ dài dãy con tăng dài nhất của dãy số đã biến đổi không đi qua ~p~
• ~x_2~ là độ dài dãy con tăng dài nhất của dãy số đã biến đổi đi qua ~p~ Đáp án sẽ là ~max(x_1, x_2)~.

Tính ~x_1~

Nếu tất cả các dãy con tăng dài nhất trong dãy số ban đầu đều đi qua vị trí ~p~ thì ~x_1 = L - 1~. Ngược lại thì ~x_1 = L~.

Để kiểm tra xem tất cả các dãy con tăng dài nhất trong dãy số ban đầu đều đi qua ~p~ hay không, ta kiểm tra hai điều kiện sau:

• ~p~ thuộc ít nhất một dãy con tăng dài nhất trong dãy số ban đầu (hay ~l_i + r_i - 1 = L~)
• Không tồn tại ~i \ne p~ sao cho:
  • ~i~ thuộc ít nhất một dãy con tăng dài nhất trong dãy số ban đầu
  • ~l_i = l_p~

Việc kiểm tra có thể thực hiện trong độ phức tạp ~O(1)~ với tiền xử lí.

Tính ~x_2~ Gọi:

• ~f_l~ là giá trị ~l_i~ lớn nhất sao cho ~1≤i<p~ và ~a_i < x~</li>
• ~f_r~ là giá trị ~l_i~ lớn nhất sao cho ~p<i≤N~ và ~a_i > x~ Khi đó, ~x_2 = f_l + f_r + 1~.</li>

Ta có thể tính các giá trị ~f_l~ cho tất cả các truy vấn trong ~O((N + Q) log(N + Q))~ bằng cách sắp xếp các truy vấn theo thứ tự ~x~ tăng dần, sau đó kết hợp kĩ thuật hai con trỏ và cấu trúc dữ liệu cây phân đoạn. (Việc tính các giá trị ~f_r~ có thể được thực hiện tương tự)

Độ phức tạp: ~O((N + Q) log(N + Q))~