ICHB Selection Contest '17 Problem 3 - Parallel Universe

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.2s
Memory limit: 64M

Author:
Problem type

You are locked in a parallel universe and for you to be able to escape you have to answer Q queries on an array named v with N elements. The queries are as follows:

  • U x val - Change the value of v[x] to val.
  • Q x y val - Print val \mathbin{\&} v[x] \mathbin{\&} v[x+1] \mathbin{\&} \cdots \mathbin{\&} v[y]. Here, \& refers to bitwise AND.

Constraints

For all subtasks:

1 \le N, Q \le 100\,000

0 \le val \le 2^{32}-1

1 \le x \le y \le N

Subtask 1 [25%]

1 \le N, Q \le 1\,000

Subtask 2 [30%]

There will be at most 75\,000 Q queries.

Subtask 3 [45%]

No additional constraints.

Input Specification

On the first line, you will find N and Q.
On the second line, you will find N numbers, where the i^\text{th} number is v[i].
On the next Q lines, you will find the queries.

Output Specification

For each Q type query, print each result on a different line.

Sample Input

3 3
5 7 15
Q 1 3 7
U 1 0
Q 1 3 15

Sample Output

5
0

Comments

There are no comments at the moment.