Bedao OI Contest 3 - Sort and Mex query

Điểm: 0,70 (OI)

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

Giới hạn bộ nhớ: 1G

Input: mexquery.inp

Output: mexquery.out

Tác giả:

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy gồm $n$ số nguyên không âm $a_{1}, a_{2}, . . ., a_{n}$ .

Bạn được yêu cầu trả lời $q$ truy vấn online:

$1$ $l$ $r$ $t y p e$ : với $t y p e = 1$ , sắp xếp $a_{l}, a_{l + 1}, \dots, a_{r}$ tăng dần. Ngược lại, với $t y p e = 2$ , sắp xếp $a_{l}, a_{l + 1}, \dots, a_{r}$ giảm dần.
$2$ $l$ $r$ : Tìm $M E X (a_{l}, a_{l + 1}, \dots, a_{r})$ .

Chú ý:

$M E X$ của một dãy số nguyên $b$ gồm $(b_{1}, b_{2}, . . ., b_{m})$ là số nguyên không âm nhỏ nhất không xuất hiện trong dãy đó.
Ví dụ: $M E X (0, 1, 2, 4, 5) = 3$ , $M E X (1, 1, 5, 100) = 0$ .

Vào từ file văn bản mexquery.inp:

Dòng đầu tiên gồm số nguyên dương $n$ - độ dài của dãy $a$ $(1 \leq n \leq 3 \cdot 10^{5})$ .

Dòng thứ hai gồm $n$ số nguyên không âm $a_{1}, a_{2}, . . ., a_{n}$ $(0 \leq a_{i} \leq 30)$ .

Dòng thứ ba gồm số nguyên dương $q$ - số truy vấn bạn cần trả lời $(1 \leq q \leq 5 \cdot 10^{4})$ .

Trong $q$ dòng cuối cùng, dòng thứ $i$ $(1 \leq i \leq q)$ có dạng như sau:

$1$ $l$ $r$ $t y p e$ $(1 \leq l, r \leq n, 1 \leq t y p e \leq 2)$ : Với $t y p e = 1$ , sắp xếp $a_{l}, a_{l + 1}, \dots, a_{r}$ tăng dần. Ngược lại, với $t y p e = 2$ , sắp xếp $a_{l}, a_{l + 1}, \dots, a_{r}$ giảm dần.
$2$ $l$ $r$ $(1 \leq l, r \leq n)$ : Tìm $M E X (a_{l}, a_{l + 1}, \dots, a_{r})$ .

In ra file văn bản mexquery.out:

Gồm $k$ dòng tương ứng $k$ truy vấn loại $2$ , dòng thứ $i$ gồm một số nguyên là kết quả của truy vấn thứ $i$ .

Subtask	Điểm	Giới hạn
1	$10 %$	$n \leq 1000, q \leq 1000$ , Chỉ bao gồm truy vấn thứ hai.
2	$20 %$	$n \leq 1000, q \leq 1000$ .
3	$30 %$	Chỉ bao gồm truy vấn thứ hai.
4	$40 %$	Không có ràng buộc gì thêm.

Copy

Copy

4
0
1

Bình luận

Hãy đọc nội quy trước khi bình luận.

0

pppssslc đã bình luận 4:26:20 ch, 29/12/2024

thôi mọi người ko cần check đâu em sửa dc r ạạ

2

DinhVantung0611 đã bình luận 10:25:33 sa, 06/12/2024 ← sửa 3 →

Mình tìm được bài khá giống dạng bài này, mọi người tham khảo: https://codeforces.com/contest/558/problem/E