P1890 - And RMQ

内存限制：512 MB 时间限制：3 S

题面：传统评测方式：文本比较上传者：

提交：11 通过：3

提交提交记录统计 Web Board

https://codeforces.com/gym/103107/problem/A

You are given a sequence consisting of N integers . There will be m different events.

AND l r v – for all elements ai (l≤i≤r), change ai to ai & v, where & means bitwise AND
UPD x v – change to
QUE l r – ask for the maximum value of ai where l≤i≤r

Please write a program to support these events efficiently.

Input

The first line contains two integers N,M (1≤N,M≤400000) denoting the length of sequence and the number of events.

The second line contains N integers a1,a2,⋯,an (1≤ai≤2³⁰−1) denoting the initial elements of the sequence.

For the next lines, each line describes an event. It is guaranteed that 1≤l,r,x≤nand 1≤v≤2³⁰−1.

Output

For each QUE event, print a single line containing an integer, denoting the answer.

It is guaranteed that there is at least one QUE event.

			Example
		

					input
					
						Copy
					
5 11
6 3 5 2 3
AND 2 4 10
UPD 1 8
AND 3 4 7
UPD 1 6
QUE 1 4
AND 3 5 10
AND 3 5 2
UPD 5 1
QUE 2 5
UPD 3 6
QUE 1 5

					output
					
						Copy
					
6
2
6

5 11
6 3 5 2 3
AND 2 4 10
UPD 1 8
AND 3 4 7
UPD 1 6
QUE 1 4
AND 3 5 10
AND 3 5 2
UPD 5 1
QUE 2 5
UPD 3 6
QUE 1 5

6
2
6

1890: And RMQ

题目描述

输入样例复制

输出样例复制

1890: And RMQ

题目描述

输入样例 复制

输出样例 复制

输入样例复制

输出样例复制