Dãy Con Tối Ưu

Điểm: 6,00 (OI)

Giới hạn thời gian: 3.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho dãy số nguyên $a = [a_{1}, a_{2}, \dots, a_{n}]$ có độ dài $n$ .

Một dãy con của $a$ là dãy thu được bằng cách xóa đi $0$ hoặc nhiều phần tử của $a$ (không cần liên tiếp).

Với một số nguyên dương $k$ ( $1 \leq k \leq n$ ), dãy con của $a$ được gọi là tối ưu nếu:

Nó có đúng $k$ phần tử và tổng các phần tử lớn nhất có thể trong số mọi dãy con độ dài $k$ .
Trong số mọi dãy con thỏa mãn điều kiện trên, nó có thứ tự từ điển nhỏ nhất.

Bạn được cho $m$ truy vấn, mỗi truy vấn gồm hai số nguyên $k_{j}$ và $p o s_{j}$ ( $1 \leq p o s_{j} \leq k_{j} \leq n$ ). Với mỗi truy vấn, hãy in ra giá trị tại vị trí $p o s_{j}$ của dãy con tối ưu của $a$ ứng với $k = k_{j}$ .

Ví dụ với $a = [10, 20, 30, 20]$ và $k = 2$ , dãy con tối ưu là $[20, 30]$ (giá trị $20$ là phần tử thứ hai của $a$ — vị trí nhỏ hơn so với $20$ ở cuối). Vậy với $k_{j} = 2$ , $p o s_{j} = 1$ thì đáp án là $20$ , và với $p o s_{j} = 2$ thì đáp án là $30$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ — độ dài của dãy.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .
Dòng thứ ba chứa số nguyên $m$ — số truy vấn.
$m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $k_{j}$ và $p o s_{j}$ .

Dữ liệu ra

In ra $m$ dòng, mỗi dòng chứa đáp án cho truy vấn tương ứng.

Ràng buộc

$1 \leq n, m \leq 2 \cdot 10^{5}$
$1 \leq a_{i} \leq 10^{9}$
$1 \leq p o s_{j} \leq k_{j} \leq n$

Ví dụ

Input	Output	Giải thích
3 10 20 10 6 1 1 2 1 2 2 3 1 3 2 3 3	20 10 20 10 20 10	Các dãy con tối ưu: $k = 1$ : $[20]$ ; $k = 2$ : $[10, 20]$ (lấy $a_{1} = 10$ và $a_{2} = 20$ ); $k = 3$ : $[10, 20, 10]$ (cả dãy).
7 1 2 1 3 1 2 1 9 2 1 2 2 3 1 3 2 3 3 1 1 7 1 7 7 7 4	2 3 2 3 2 3 1 1 3	Với $k = 2$ , dãy con tối ưu là $[2, 3]$ (lấy $a_{2}$ và $a_{4}$ ). Với $k = 3$ , dãy con tối ưu là $[2, 3, 2]$ (lấy $a_{2}, a_{4}, a_{6}$ ).

Bình luận

Không có bình luận tại thời điểm này.