Trung Vị Đoạn · canuc80k5103 · Thuật toán Canuc80k

Cho mảng $a_{1}, \dots, a_{n}$ . Mỗi truy vấn xác định một đoạn $[l, r]$ .

Đặt $len = r - l + 1$ . Sắp các phần tử $a_{l}, a_{l + 1}, \dots, a_{r}$ theo thứ tự không giảm và đánh số vị trí từ $1$ . Lower median của đoạn là phần tử ở vị trí

⌊(len + 1) /2 ⌋ .

Như vậy, khi $len$ chẵn, ta chọn phần tử ở giữa bên trái. Hãy in lower median của từng đoạn.

Input

Dòng đầu chứa $n$ và $q$ .
Dòng thứ hai chứa $n$ phần tử của mảng.
$q$ dòng tiếp theo chứa $l$ và $r$ của một đoạn truy vấn.

Output

Với mỗi truy vấn, in lower median trên một dòng.

Constraints

$1 \leq n, q \leq 1 0^{5}$ .
$1 \leq a_{i} \leq 1 0^{5}$ .
$1 \leq l \leq r \leq n$ .
Với độ dài $len$ , lower median là phần tử thứ $⌊(len + 1) /2 ⌋$ trong thứ tự tăng dần, dùng chỉ số $1$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n, q \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

7 4
8 1 6 6 3 9 2
1 7
2 5
3 4
6 6

Output

Giải thích: Toàn mảng sau khi sắp là $1, 2, 3, 6, 6, 8, 9$ nên trung vị là $6$ . Đoạn $1, 6, 6, 3$ có lower median $3$ ; hai truy vấn còn lại lần lượt cho $6$ và $9$ .

Ý tưởng: Một lower median của đoạn dài len là phần tử nhỏ thứ k=(len+1)/2. Với ngưỡng giá trị v, predicate là “đoạn có ít nhất k phần tử không vượt v”, vốn đơn điệu.
Ý tưởng: Nén các giá trị phân biệt tăng dần. Trong mỗi vòng parallel binary search, reset Fenwick rồi quét các rank từ nhỏ đến lớn. Khi đến một rank, kích hoạt mọi vị trí có giá trị ở rank đó bằng +1; tổng Fenwick trên [l,r] khi ấy chính là số phần tử trong đoạn không vượt ngưỡng. Mọi truy vấn có cùng midpoint được kiểm tra ở bucket tương ứng.
Ý tưởng: Nếu số đếm đạt k, hạ cận trên; nếu chưa đạt, nâng cận dưới. Rank nhỏ nhất thỏa predicate ánh xạ ngược thành đúng lower median, kể cả khi độ dài chẵn hoặc có nhiều giá trị trùng.
Độ phức tạp: O((n+q) log n log V) thời gian và O(n+q+V) bộ nhớ, với V là số giá trị phân biệt.