Tổng độ lệch tuyệt đối tới trung vị
Points
36
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề bài
Cho dãy $a_1,\dots,a_n$. Mỗi truy vấn $(l,r)$: gọi $m$ là trung vị dưới của đoạn, tức phần tử nhỏ thứ $\lceil (r-l+1)/2\rceil$. Hãy tính $\sum_{i=l}^{r}|a_i-m|$.
Dữ liệu vào
Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên. Sau đó $q$ dòng: $l,r$.
Dữ liệu ra
Với mỗi truy vấn in đáp án.
Ví dụ
Input
5 5
3 -9 2 10 4
3 5
4 4
5 5
1 5
3 5
Output
8
0
0
21
8
Giới hạn
- $1\le n,q\le 10^5$; $|a_i|\le 10^9$.
- Thời gian: 2 giây; bộ nhớ: 256 MB.
Community Discussion