A Fenwick Tree Question

View as PDF

Submit solution

Points: 15
Time limit: 0.6s
Memory limit: 64M

Author:
Problem type

Simple statement. You have a 1-indexed array with N integers, and you want to perform some Q queries on it.

  1. 1 p x: change index p to x, where 1 \le x \le 10^8
  2. 2 l r: perform the OR bitwise operation on all pairs from l to r, inclusive, then sum them
  3. 3 l r: perform the AND bitwise operation on all pairs from l to r, inclusive, then sum them
  4. 4 l r: perform the XOR bitwise operation on all pairs from l to r, inclusive, then sum them

Input Specification

The first line will contain N and Q, 1 \le N \le 10^5, 1 \le Q \le 10^4.

The second line will contain N integers.

The next Q lines will contain valid queries.

For 30% of the points, \{N, x\} \le 10, Q \le 50.

Output Specification

For each query from 2 to 4, output the sum.

Sample Input 1

6 1
4 4 8 10 4 6
2 3 6

Sample Output 1

70

Comments

There are no comments at the moment.