Phần tử trung vị
Tichpx dạy môn xử lý ảnh có thuật toán lọc trung vị, đây là một thuật toán cần phải tìm trung vị của histogram. Trung vị của một dãy n phần tử \(a_1, a_2, ... a_n\) là phần tử mà khi sắp xếp dãy tăng dần thì nó ở giữa dãy đó là \(a[(n+1)/2]\). Chẳng hạn trung vị của dãy {1,3,4,5} có 4 phần tử trung vị là a[(4+1)/2]=a[2]= 3 còn trung vị của dãy {1,3,4,5,5} thì trung vị là a[(5+1)/2]=a[3]=4;
Bài toán đặt ra là bạn lần lượt bổ sung n phần tử vào dãy với mỗi phần tử thứ i bổ sung vào thì xuất ra trung vị của dãy con \(a_1, a_2,... a_i\)
Input
Dòng đầu là số nguyên dương n \((1<= n <=10^6)\)
Dòng tiếp theo chứa n phần tử có giá trị tuyệt đối không vượt quá 32767.
Output
Xuất ra n giá trị trung vị của các dãy con tiếp đầu của dãy đã cho
Ví dụ
Input
9
7 4 2 1 6 8 5 8 7Output
7 4 4 2 4 4 5 5 6Giải thích : Ban đầu dãy rỗng ta bổ sung lần lượt
Bổ sung 7 nên dãy con sau khi săp {7} -> trung vị 7
Bổ sung 4 nên dãy con sau khi săp {4, 7} -> trung vị 4
Bổ sung 2 nên dãy con sau khi sắp {2, 4, 7} -> trung vị 4
Bổ sung 1 nên dãy con sau khi sắp {1, 2, 4, 7} -> trung vị 2
Bổ sung 6 nên dãy con sau khi sắp {1, 2, 4, 6, 7} -> trung vị 4
Bổ sung 8 nên dãy con sau khi sắp {1, 2, 4, 6, 7, 8} -> trung vị 4
Bổ sung 5 nên dãy con sau khi sắp {1, 2, 4, 5, 6, 7, 8} -> trung vị 5
Bổ sung 8 nên dãy con sau khi sắp {1, 2, 4, 5, 6, 7, 8, 8} -> trung vị 5
Bổ sung 7 nên dãy con sau khi sắp {1, 2, 4, 5, 6, 7, 7, 8, 8} -> trung vị 6
Comments
custom binary tree N * log(N): https://ideone.com/jwiM89
Cừ dạo này code cây ác liệt
e đang cày pro bên ss, chủ yếu code tay to, ko dùng thu viện, dùng gì code lại xD nên vào đây test xD
Test 10^6 chặt quá thời gian