#846. NOST2 - Không Binary index tree

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

Cho một mảng gồm 𝑁 số nguyên dương 𝑎_1, 𝑎_2, … 𝑎_𝑁\ (1 ≤ 𝑎_𝑖 ≤ 10^9) 𝑀 truy vấn trên đó. Mỗi truy vấn thuộc một trong hai loại sau:

  • Loại 1 : Có dạng 1\ 𝐿\ 𝑅\ 𝑃 với ý nghĩa là truy vấn loại 1 , lấy tất cả các số trong đoạn [𝐿, 𝑅] mà chia hết cho 𝑃 đem chia cho 𝑃 , với 𝑃 ∈ {2,3,5} ;
  • Loại 2 : Có dạng 2\ 𝐿\ 𝐷 với ý nghĩa là truy vấn loại 2 , gán số nguyên dương 𝐷 cho phần tử ở vị trí 𝐿 .

Yêu cầu: hãy tin ra mảng cuối cùng nhận được sau M truy vấn.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên dương 𝑁, 𝑀\ (1 ≤ 𝑁, 𝑀 ≤ 5×10^4) ;
  • Dòng tiếp theo chứa 𝑁 số nguyên dương 𝑎_1, 𝑎_2, … 𝑎_𝑁 ;
  • M dòng tiếp theo là mô tả các truy vấn thuộc loại 1 hoặc 2 nêu ở trên.

Dữ liệu ra:

  • Dãy số thu được sau 𝑀 truy vấn.

Ví dụ:

Dữ liệu vào:
3 5
1 2 3
1 2 2 2
1 2 2 2
2 2 3
1 2 3 3
2 1 5
Dữ liệu ra:
5 1 1
Giải thích:

Dãy ban đầu: \{1,2,3\} ;

  • Sau truy vấn 1\ 2\ 2\ 2 ta được: \{1,1,3\} ;
  • Sau truy vấn 1\ 2\ 2\ 2 ta được: \{1,1,3\} ;
  • Sau truy vấn 2\ 2\ 3 ta được: \{1,3,3\} ;
  • Sau truy vấn 1\ 2\ 3\ 3 ta được: \{1,1,1\} ;
  • Sau truy vấn 2\ 1\ 5 ta được: \{5,1,1\} .