Đế Chế Hùng Mạnh

Buổi 62 — Sqrt Decomposition & Mo
Points
65
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Đế chế có N thành phố xếp thành hàng, thành phố thứ i có dân số a_i. Ban đầu có Q sắc lệnh, mỗi sắc lệnh có dạng:

  • Loại 1: 1 p v — thay đổi dân số thành phố p thành v.
  • Loại 2: 2 l r — hỏi tổng bình phương tần suất của mỗi giá trị dân số trong đoạn [l, r]. Cụ thể, nếu giá trị x xuất hiện f_x lần thì kết quả = Σ(f_x^2).

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 sắc lệnh.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra tổng bình phương tần suất trên một dòng.

Ví dụ
Input Output
5 4\n1 2 1 2 3\n2 1 5\n1 3 2\n2 1 5\n2 1 3 9\n11\n5
Giới hạn
  • 1 ≤ N ≤ 100000
  • 1 ≤ Q ≤ 100000
  • 1 ≤ a_i, v ≤ 100000
  • 1 ≤ p ≤ N
  • 1 ≤ l ≤ r ≤ N
Draft saved