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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

  • U x val - Change the value of v[x] to val (0 \le val \le 2^{32} - 1)
  • Q x y val - Print val \mathbin{\&} v[x] \mathbin{\&} v[x + 1] \mathbin{\&} \cdots \mathbin{\&} v[y]. Here, \& refers to bitwise AND. (1 \le x \le y \le N)

Input Specification

On the first line you will find N and Q.
On the second line you will find N numbers, where the i-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.