Tổng k phần tử nhỏ nhất trong đoạn
Points
20
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,k)$: hãy tính tổng của $k$ phần tử nhỏ nhất trong đoạn $a_l,\dots,a_r$.
Dữ liệu vào
Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên. Tiếp theo $q$ dòng: $l,r,k$ với $1\le k\le r-l+1$.
Dữ liệu ra
Với mỗi truy vấn in tổng cần tìm.
Ví dụ
Input
5 5
9 2 -6 10 -3
2 5 4
2 4 1
3 3 1
3 4 1
2 2 1
Output
3
-6
-6
-6
2
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