Bedao OI Contest 3 - Sort and Mex query
Xem dạng PDF
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~ ~type~: với ~type = 1~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ tăng dần. Ngược lại, với ~type = 2~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ giảm dần.
~2~ ~l~ ~r~: Tìm ~MEX(a_l, a_{l+1}, \dots, a_r)~.
Chú ý:
~MEX~ 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ụ: ~MEX(0, 1, 2, 4, 5) = 3~, ~MEX(1, 1, 5, 100) = 0~.
Input
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 \le n \le 3 \cdot 10^5)~.
Dòng thứ hai gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ ~(0 \le a_i \le 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 \le q \le 5 \cdot 10^4)~.
Trong ~q~ dòng cuối cùng, dòng thứ ~i~ ~(1 \le i \le q)~ có dạng như sau:
~1~ ~l~ ~r~ ~type~ ~(1 \le l, r \le n, 1 \le type \le 2)~: Với ~type = 1~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ tăng dần. Ngược lại, với ~type = 2~, sắp xếp ~a_l, a_{l+1}, \dots, a_r~ giảm dần.
~2~ ~l~ ~r~ ~(1 \le l, r \le n)~: Tìm ~MEX(a_l, a_{l+1}, \dots, a_r)~.
Output
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~.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~10\%~ | ~n \le 1000, q \le 1000~, Chỉ bao gồm truy vấn thứ hai. |
| 2 | ~20\%~ | ~n \le 1000, q \le 1000~. |
| 3 | ~30\%~ | Chỉ bao gồm truy vấn thứ hai. |
| 4 | ~40\%~ | Không có ràng buộc gì thêm. |
Sample Input 1
5
1 3 2 0 4
5
2 1 4
1 1 4 1
2 2 5
1 2 5 2
2 1 3
Sample Output 1
4
0
1
Bình luận
thôi mọi người ko cần check đâu em sửa dc r ạạ
mọi người check hộ em code này sao sai vậy ạ
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
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.