Bedao Mini Contest 16 - QUERY
Xem dạng PDF
Cho một dãy số nguyên ~a~ kích thước ~n~ bao gồm toàn các phần tử không âm.
Người ta thực hiện lần lượt các truy vấn sau thuộc một trong ba dạng sau trên dãy:
~1~ ~l~ ~r~ ~x~: Gán ~a_i=a_i~ AND ~x~ với mọi ~l\le i \le r~.
~2~ ~l~ ~r~ ~x~: Gán ~a_i=x~ với mọi ~l\le i \le r~.
~3~ ~l~ ~r~: Tính giá trị ~a_l~ OR ~a_{l+1}~ OR ~...~ OR ~a_r~.
Trong đó AND là toán tử AND và OR là toán tử OR.
Yêu cầu: Bạn hãy cho biết người ta ở đây là ai trả lời giá trị của
biểu thức ở các truy vấn loại 3 nhé.
Input
Dòng đầu chứa hai số nguyên dương ~n, q~ (~1\le n,q \le 5\cdot10^5~) là kích thước dãy và số truy vấn.
Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~0\le a_i < 2^{30}~) mô tả dãy số.
~q~ dòng tiêp, mỗi dòng chứa một truy vấn thuộc một trong ba dạng kể trên. Trong mọi truy vấn luôn có ~1\le l \le r \le n~; trong truy vấn 1 và 2 luôn có ~0 \le x < 2^{30}~.
Output
In ra nhiều dòng, mỗi dòng là câu trả lời cho các truy vấn loại 3 tương ứng.
Scoring
Có ~20\%~ số test của bài với ~n,q\le 5000~.
Có ~20\%~ số test khác của bài không có các truy vấn loại 1.
Có ~20\%~ số test khác của bài với ~n,q \leq 10^5~
~40\%~ số test còn lại không có điều kiện gì thêm.
Sample Input 1
5 6
1 2 3 4 5
3 1 5
3 2 3
1 1 5 1
3 1 5
2 3 4 4
3 2 3
Sample Output 1
7
3
1
4
Notes
Sau truy vấn loại 1, dãy ~a~ trở thành:
~[1, 0, 1, 0, 1]~
Sau truy vấn loại 2, dãy ~a~ trở thành:
~[1, 0, 4, 4, 1]~
Bình luận
Lạy bố, code "chtholly tree" của bố là O(nq) đấy bố ạ. Chẳng qua AC là do test chưa giết cái thuật đó thôi. Đừng có AI cho ra cái gì cũng tin thế :)))