Sắp xếp nổi bọt là một thuật toán sắp xếp dãy số. Xét dãy \(A_0,A_1,\ldots,A_{N-1}\) có độ dài \(N\), cần sắp xếp theo thứ tự không giảm. Thuật toán đổi chỗ hai số kề nhau nếu chúng chưa đúng thứ tự, bằng cách thực hiện nhiều lượt duyệt qua dãy. Cụ thể, trong một lượt, lần lượt xét \(i=0,1,\ldots,N-2\) theo đúng thứ tự này; nếu \(A_i>A_{i+1}\) thì đổi chỗ \(A_i\) và \(A_{i+1}\).

Mọi dãy đều có thể được sắp xếp không giảm sau một số lượt như vậy. Số lượt duyệt của sắp xếp nổi bọt là số lượt cần thực hiện để dãy trở thành không giảm. Nếu dãy đã không giảm thì số lượt là \(0\); không tính thêm một lượt chỉ để kiểm tra rằng dãy đã được sắp xếp.

JOI có một dãy \(A\) độ dài \(N\) và sẽ xử lý \(Q\) truy vấn thay đổi giá trị trong dãy. Ở truy vấn thứ \(j+1\), với \(0 \le j \le Q-1\), giá trị \(A_{X_j}\) được thay bằng \(V_j\). Các thay đổi được giữ lại cho những truy vấn tiếp theo.

Hãy tìm số lượt duyệt của sắp xếp nổi bọt đối với dãy ngay sau mỗi truy vấn. Việc xét sắp xếp chỉ nhằm tính số lượt, không làm thay đổi dãy dùng cho các truy vấn tiếp theo.

Cài đặt

Với C++, nộp tệp cài đặt hàm sau và khai báo #include "bubblesort2.h":

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V);

• A là mảng số nguyên độ dài \(N\), chứa dãy ban đầu.
• X và V là hai mảng số nguyên độ dài \(Q\), mô tả các truy vấn.
• Hàm trả về mảng số nguyên S độ dài \(Q\). Với mỗi \(0 \le j \le Q-1\), S[j] là số lượt duyệt của sắp xếp nổi bọt đối với dãy ngay sau truy vấn thứ \(j+1\).

Trên LQDOJ, nộp đúng một tệp C++ cài đặt hàm theo chữ ký trên. Có thể cài đặt thêm các hàm phụ. Chương trình không được đọc đầu vào chuẩn, ghi đầu ra chuẩn hoặc tương tác với bất kỳ tệp nào khác; được phép ghi ra luồng lỗi chuẩn. Gói đính kèm chính thức vẫn được giữ để tham khảo, nhưng trình chấm của bài này chỉ hỗ trợ C++. Thông báo kỳ thi gốc quy định tối đa \(50\) lần nộp cho mỗi bài.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau; chương trình của bạn nhận dữ liệu qua tham số hàm:

• Dòng đầu chứa \(N,Q\).
• Dòng thứ hai chứa \(A_0,A_1,\ldots,A_{N-1}\).
• Dòng thứ \(3+j\) chứa \(X_j,V_j\), với \(0 \le j \le Q-1\).

Dữ liệu ra

Trình chấm mẫu in mảng do countScans trả về: dòng thứ \(1+j\) chứa \(S_j\), với \(0 \le j \le Q-1\).

Ràng buộc

• \(1 \le N \le 500000\); \(1 \le Q \le 500000\).
• \(1 \le A_i \le 1000000000\) với \(0 \le i \le N-1\).
• \(0 \le X_j \le N-1\) và \(1 \le V_j \le 1000000000\) với \(0 \le j \le Q-1\).
• Giới hạn thời gian: \(5\) giây. Giới hạn bộ nhớ: \(512\) MB.

Phân nhóm

1. \(17\) điểm: Giới hạn \(N\): \(1 \le N \le 2000\); Giới hạn \(Q\): \(1 \le Q \le 2000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 1000000000\)
2. \(21\) điểm: Giới hạn \(N\): \(1 \le N \le 8000\); Giới hạn \(Q\): \(1 \le Q \le 8000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 1000000000\)
3. \(22\) điểm: Giới hạn \(N\): \(1 \le N \le 50000\); Giới hạn \(Q\): \(1 \le Q \le 50000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 100\)
4. \(40\) điểm: Giới hạn \(N\): \(1 \le N \le 500000\); Giới hạn \(Q\): \(1 \le Q \le 500000\); Giới hạn giá trị: \(1 \le A_i,V_j \le 1000000000\)

Các điều kiện trên áp dụng cho mọi chỉ số hợp lệ \(0 \le i \le N-1\) và \(0 \le j \le Q-1\).

Ví dụ giao tiếp

Cho \(N=4\), \(A=\{1,2,3,4\}\) và \(Q=2\) truy vấn với \(X=\{0,2\}\), \(V=\{3,1\}\).

Sau truy vấn thứ nhất, thay \(A_0\) bằng \(3\), ta có \(A=\{3,2,3,4\}\). Sau truy vấn thứ hai, thay \(A_2\) bằng \(1\), ta có \(A=\{3,2,1,4\}\).

Với dãy \(\{3,2,3,4\}\), dãy chưa được sắp xếp nên bắt đầu lượt thứ nhất. Vì \(A_0>A_1\), đổi chỗ chúng để được \(\{2,3,3,4\}\). Vì \(A_1 \le A_2\) và \(A_2 \le A_3\), không có lần đổi chỗ nào khác. Dãy đã không giảm, nên thuật toán kết thúc sau \(1\) lượt.

Với dãy \(\{3,2,1,4\}\), trong lượt thứ nhất, đổi chỗ \(A_0,A_1\) để được \(\{2,3,1,4\}\), rồi đổi chỗ \(A_1,A_2\) để được \(\{2,1,3,4\}\). Không đổi chỗ \(A_2,A_3\) vì \(A_2 \le A_3\). Dãy vẫn chưa được sắp xếp, nên bắt đầu lượt thứ hai: đổi chỗ \(A_0,A_1\) để được \(\{1,2,3,4\}\); không đổi chỗ hai cặp còn lại vì chúng đã đúng thứ tự. Dãy đã không giảm, nên thuật toán kết thúc sau \(2\) lượt.

Nguồn

JOI Open 2018 - Bubble Sort 2, đề tiếng Anh, thông báo cài đặt và gói mã mẫu chính thức. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.