Tổ Hợp Thuật Toán STL

Algorithms Binary-search Buổi 10 — STL Algorithms Implementation sorting
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Cho một dãy gồm $N$ số nguyên. Bạn cần thực hiện $Q$ thao tác, mỗi thao tác thuộc một trong các loại sau:

  • Loại 1: 1 — Sắp xếp toàn bộ dãy hiện tại tăng dần.
  • Loại 2: 2 — Loại bỏ các phần tử trùng lặp liền kề (tương tự unique). Dãy hiện tại phải đã được sắp xếp.
  • Loại 3: 3 — Biến dãy thành hoán vị kế tiếp theo thứ tự từ điển. Nếu đã là hoán vị cuối, quay lại hoán vị đầu.
  • Loại 4: 4 x — In ra vị trí (1-indexed) của phần tử đầu tiên $\ge x$ (dùng lower_bound trên dãy đã sắp xếp). In 0 nếu không tồn tại. Dãy phải đã được sắp xếp.
  • Loại 5: 5 — In ra tổng tất cả phần tử hiện tại.
  • Loại 6: 6 — In ra số phần tử hiện tại.

Sau tất cả thao tác, in ra dãy hiện tại.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N$ và $Q$.
  • Dòng thứ hai chứa $N$ số nguyên.
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một thao tác.
Dữ liệu ra
  • Với mỗi thao tác loại 4, 5, 6: in kết quả trên một dòng.
  • Dòng cuối cùng: in ra dãy hiện tại.
Ví dụ
Input Output
5 5
3 1 4 1 5
1
2
5
4 3
6
13
2
4
1 3 4 5
Giới hạn
  • $1 \le N \le 10^4$
  • $1 \le Q \le 10^4$
  • $|a_i|, |x| \le 10^9$
  • Đảm bảo thao tác 2 và 4 chỉ được gọi khi dãy đã sắp xếp.
Draft saved