Biến Đổi Sắc Cầu Vồng

Buổi 62 — Sqrt Decomposition & Mo
Points
40
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Submissions
Đề 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
Draft saved