K-th nhỏ nhất trong hợp hai đoạn

Buổi 30 — Persistent Segment Tree
Points
45
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho dãy $a_1,\dots,a_n$. Mỗi truy vấn $(l_1,r_1,l_2,r_2,k)$: gộp các phần tử của hai đoạn $[l_1,r_1]$ và $[l_2,r_2]$ thành một đa tập (hai đoạn có thể giao nhau, phần tử được tính hai lần nếu thuộc cả hai). Tìm phần tử nhỏ thứ $k$ của đa tập này.

Dữ liệu vào

Dòng đầu: $n,q$. Dòng hai: $n$ số nguyên. Sau đó $q$ dòng: $l_1,r_1,l_2,r_2,k$ với $1\le k\le (r_1-l_1+1)+(r_2-l_2+1)$.

Dữ liệu ra

Với mỗi truy vấn in đáp án.

Ví dụ

Input

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

Output

-9
3
-9
3
-5
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.
Draft saved