Lấy căn bậc hai trên đoạn

Buổi 27 — Segment Tree cơ bản
Points
50
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho mảng $A$ gồm $n$ số nguyên không âm và $q$ truy vấn thuộc một trong ba loại:

  • 1 l r: Với mọi $l \le i \le r$, thay thế $A[i] \leftarrow \lfloor \sqrt{A[i]} \rfloor$.
  • 2 i x: Gán $A[i] = x$.
  • 3 l r: Tính tổng các phần tử $A[l..r]$.
Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $n, q$.
  • Dòng thứ hai chứa $n$ số nguyên $A[1], A[2], \dots, A[n]$.
  • $q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn.
Dữ liệu ra

Với mỗi truy vấn loại 3, in ra tổng tìm được trên một dòng.

Ví dụ
Input Output
5 5
1 4 9 16 25
3 1 5
1 2 4
3 1 5
2 3 100
3 1 5
55
35
132
Giới hạn
  • $1 \le n, q \le 10^5$
  • $0 \le A[i], x \le 10^{12}$
  • $1 \le l \le r \le n$
Draft saved