Bản Giao Hưởng Tần Số

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