Levve Loves Segment Trees

View as PDF

Submit solution

All submissions

Best submissions

Points: 15

Time limit: 1.0s

Java 2.0s

Python 4.0s

Memory limit: 1G

Author:

Blackgaurdian3

Problem type

Levve loves segment trees, so he has given you the following task:

You are given an array of $N$ $N$ zeroes and $Q$ $Q$ operations of the following forms:

C x v: Change the element's value at index $x$ $x$ to $v$ $v$ .
S l r: Output the sum of all elements between indices $l$ $l$ and $r$ $r$ , inclusive.
M l r: Output the maximum of all elements between indices $l$ $l$ and $r$ $r$ , inclusive.

Levve doesn't like cheesing, so you will not be given $l_i$ $l_{i}$ , $r_i$ $r_{i}$ , $x_i$ $x_{i}$ or $v_i$ $v_{i}$ directly. Instead of $l_i$ $l_{i}$ , you will be given $l'_i$ $l_{i}^{'}$ , which can be decrypted using the formula $l_i = l'_i \oplus lastAns$ $l_{i} = l_{i}^{'} \oplus l a s t A n s$ where $lastAns$ $l a s t A n s$ represents the output to the previous S or M query, and $\oplus$ $\oplus$ represents the bitwise xor operation. If there is no previous output, $lastAns = 0$ $l a s t A n s = 0$ .

Similarly:

$r_i = r'_i \oplus lastAns$ $r_{i} = r_{i}^{'} \oplus l a s t A n s$
$x_i = x'_i \oplus lastAns$ $x_{i} = x_{i}^{'} \oplus l a s t A n s$
$v_i = v'_i \oplus lastAns$ $v_{i} = v_{i}^{'} \oplus l a s t A n s$

Constraints

$1 \le N \le 10^{18}$ $1 \leq N \leq 10^{18}$

$1 \le Q \le 4 \times 10^5$ $1 \leq Q \leq 4 \times 10^{5}$

$1 \le x \le N$ $1 \leq x \leq N$

$0 \le v \le 10^9$ $0 \leq v \leq 10^{9}$

$1 \le l \le r \le N$ $1 \leq l \leq r \leq N$

Input Specification

The first line contains two space-separated integers, $N$ $N$ and $Q$ $Q$ .

The following $Q$ $Q$ lines each contain a query of one of the previously described forms.

Output Specification

For each S or M query, output its result on a new line.

Sample Input

Copy

Sample Input (Unencrypted)

Copy

Sample Output

Copy

1
8

Comments

0

maxcruickshanks commented on Aug. 8, 2022, 4:49 p.m.

Since the original data were weak, an additional test case was added, and all submissions were rejudged.