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

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].


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



There are no comments at the moment.