Bản Giao Hưởng Tần Số
Points
75
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Đề bài
Một bản nhạc gồm N nốt xếp liên tiếp, nốt thứ i có cao độ a_i. Có Q truy vấn và U cập nhật xen kẽ:
- Loại 1:
1 p v— thay đổi cao độ nốt thứ p thành v. - Loại 2:
2 l r— hỏi có bao nhiêu cặp (i, j) với l ≤ i < j ≤ r mà a_i = a_j.
Sử dụng Mo's algorithm with updates.
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ố cặp bằng nhau trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 5\n1 2 1 2 3\n2 1 5\n1 3 2\n2 1 5\n1 5 2\n2 1 5 | 2\n3\n6 |
Giới hạn
- 1 ≤ N ≤ 100000
- 1 ≤ Q ≤ 100000
- 1 ≤ a_i, v ≤ 100000
- 1 ≤ p ≤ N
- 1 ≤ l ≤ r ≤ N
Community Discussion