Bedao Mini Contest 16 - QUERY

Xem dạng PDF

Gửi bài giải


Điểm: 0,70 (OI)
Giới hạn thời gian: 2.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.