GFSSOC '15 Winter S5 - ORBOT

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Haskell 13.0s
Memory limit: 512M

Authors:
Problem type

As much as ButaneBot's newly recoded OR function is cool, he is still getting bored of storing only numbers in the form 2^x-1 inside of him. Instead, he has been asked to code a much more interesting problem. There are initially N numbers in an array, and Q queries of the form i X. After each query, the i-th number in the array becomes X. Your job is to find the maximum bitwise OR of ANY consecutive subarray, after every single query. Note that ButaneBot is assuming all numbers are represented as a 32-bit signed two's complement number, and that updates are cumulative. He also assumes that your subarray will be of length at least 1.

Input Specification

The first line of input will contain the integers N and Q.

The next line will contain N integers, the initial array.

The next Q lines will each have two numbers i and X which represent the index to be changed and the value of the new number, respectively.

Constraints

N \le 10^5

Q \le 4 \cdot 10^5

1 \le i \le N

At any time, all values in the array will fall in the range [-10^9,10^9].

Subtask 1 [30%]

All integers in the input will be either strictly non negative, or strictly non positive.

Subtask 2 [70%]

No additional constraints.

Output Specification

Output one integer for each query, the maximum bitwise OR of any consecutive subarray given the current state of the array.

Sample Input

3 2
2 3 -1
3 -2
1 -4

Sample Output

3
3

Explanation for Sample Output

The initial array is [2,3,-1]. After the first update, the array becomes [2,3,-2]. The maximum bitwise OR of a subarray is 2 \mathbin{|} 3=3. After the second update, our array becomes [-4,3,-2]. In this case, the best bitwise OR we can get is choosing just the number 3.


Comments

There are no comments at the moment.