Biến Đổi Sắc Cầu Vồng
Points
40
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Đề bài
Một dãy N ô, ô thứ i ban đầu có màu a_i. Có Q thao tác gồm hai loại:
- Loại 1:
1 p v— thay đổi màu ô thứ p thành v. - Loại 2:
2 l r— hỏi có bao nhiêu màu khác nhau trong đoạn [l, r].
Sử dụng thuật toán Mo với cập nhật (Mo's algorithm with updates) để giải quyết.
Dữ liệu vào
Dòng đầu chứa hai số nguyên N và Q (1 ≤ N ≤ 100000, 1 ≤ Q ≤ 100000). Dòng thứ hai chứa N số nguyên a_1, a_2, ..., a_N (1 ≤ a_i ≤ 100000). 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 truy vấn loại 2, in ra số lượng màu khác nhau trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 5\n1 2 3 2 1\n2 1 5\n1 3 2\n2 1 5\n1 1 4\n2 1 5 | 3\n2\n3 |
Giới hạn
- 1 ≤ N ≤ 100000
- 1 ≤ Q ≤ 100000
- 1 ≤ a_i, v ≤ 100000
- 1 ≤ p ≤ N
- 1 ≤ l ≤ r ≤ N
Community Discussion