Với mỗi dãy số nguyên gồm phần từ , ta định nghĩa phần tử trung vị của dãy là số đứng ở vị trí thứ sau khi đã sắp xếp lại dãy theo thứ tự không giảm. Ví dụ dãy sau khi sắp xếp không giảm thành dãy có phần tử trung vị là số đứng thứ là , dãy sau khi sắp xếp không giảm được dãy có phần tử trung vị đứng thứ là .
Cho dãy số nguyên được sinh ngẫu nhiên như sau:
;
(chia lấy phần dư).
Với là các số cho trước.
Cho một số . Dãy đã cho có dãy con độ dài gồm các phần tử liên tiếp nhau. Hãy tính tổng tất cả các phần tử trung vị của dãy con này.
Dữ liệu vào:
Dòng đầu chứa số nguyên dương là số bộ test.
dòng tiếp theo, mỗi dòng chứa số nguyên , hai số liên tiếp cách nhau ít nhất một dấu cách.
Dữ liệu ra:
Gồm số nguyên, mỗi số là tổng trung vị tìm được của test tương ứng. Hai số liên tiếp ghi cách nhau một dấu cách.
Ví dụ:
Dữ liệu vào:
2
3 1 1 10 3
10 0 13 5 2
Dữ liệu ra:
60 49
Giải thích:
Test case Dãy sinh ra là . Các trung vị tương ứng là và tổng là .
