Ước Chung Dãy Số

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

Cho dãy N số nguyên dương. Có hai loại thao tác: thay một phần tử, hoặc hỏi ước chung lớn nhất của một đoạn liên tiếp.

Dữ liệu vào

Dòng đầu chứa hai số nguyên N và Q. Dòng thứ hai chứa N số nguyên a_1..a_N. Q dòng tiếp theo, mỗi dòng là một trong hai dạng:

  • 1 i x: gán a_i = x.
  • 2 l r: truy vấn trên đoạn [l, r].
Dữ liệu ra

Với mỗi truy vấn loại 2, in ra gcd(a_l, ..., a_r).

Ví dụ
Input Output
5 4\n5 6 7 7 7\n2 1 4\n2 1 4\n2 1 4\n2 3 5 1\n1\n1\n7
Giới hạn
  • 1 ≤ N, Q ≤ 10^5
  • 1 ≤ a_i, x ≤ 10^9
Draft saved