SAC '22 Code Challenge 2 P5 - Even Colouring

View as PDF

Submit solution


Points: 10 (partial)
Time limit: 1.0s
Java 1.5s
Python 2.0s
Memory limit: 256M

Author:
Problem type

Ever since Mr. DeMello forced you to clean the campus, he has been feeling remorseful, so he only asks you to maintain his new array.

Initially, he has N elements and will make Q queries of 2 types:

1 i j: Update the element at index i to have a value of j.

2 L R: Output the sum of every second element starting at L (and including L) between [L, R].

Constraints

For all subtasks:

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

1 \le i \le N

-1\,000\,000\,000 \le A_i, j \le 1\,000\,000\,000

1 \le L \le R \le N

Subtask 1 [20%]

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

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line will contain N and Q, the number of elements and queries.

The next line will contain N space-separated integers, A_i, the elements of the array.

The next Q lines will contain one of the queries listed above.

Note: Fast I/O might be required to fully solve this problem (e.g., BufferedReader for Java).

Output Specification

For every type 2 query, output the sum as specified.

Sample Input

5 5
1 5 6 9 3
2 1 5
2 2 5
1 2 -4
2 1 5
2 2 5

Sample Output

10
14
10
5

Comments

There are no comments at the moment.