No.925 Kizuna Extra
If you are experiencing an issue where math formulas are not displayed, please take the following steps.
https://twitter.com/yukicoder/status/1191757446596812800?s=20
Note
This problem is an online version, with update queries, of the problem "Kizuna". The constraints are also slightly different.
In this problem, even a correct solution may get TLE in slow languages such as Python (sorry).
Problem Statement
You are given an integer sequence $A$ of length $N$. Initially, the $i$-th value of the sequence $A$ is $A_i$.
A total of $Q$ queries of the following two types are given. Process them online.
$1\ X\ Y$
- Query $1$: Change the value of the element $A_X$ to $Y$.
$2\ L\ R$
- Query $2$: Find the minimum value of the following function $f$.
- $\displaystyle f(x) = \sum_{k = L}^{R} |x - A_k|$
The input is given in encoded form. See "Decoding Method" for details.
Input
$N\ Q$
$A_1\ A_2\ \cdots\ A_{N - 1}\ A_N$
${\rm query}_1$
$\vdots$
${\rm query}_Q$
- $1 \le N, Q < \color{red}{2^{16}}$
- $\color{red} {0} \le A_i < \color{red}{2^{40}}$
- At least one query $2$ is included.
- The $i$-th query ${\rm query}_i$ is given in one of the following formats, with the following constraints.
-
$1\ X\ Y$
- $1 \le X \le N$
- $\color{red} {0} \le Y < \color{red}{ 2^{40}}$
- $X$ and $Y$ are given in encoded form.
-
$2\ L\ R$
- $1 \le L,R \le N$
- $L$ and $R$ are given in encoded form.
- All input values are integers.
The constraints apply to the values before encoding. Note that the values after encoding do not necessarily satisfy the above constraints.
Decoding Method
Decode the encoded values and answer the queries. Decoding is performed as follows.
For a given query, let $s$ be the bitwise-xor of all answers to the queries $2$ before that query (if no query $2$ has been given yet, let $s = 0$).
For that query,
replace each of $L, R, X$ with its bitwise-xor with $s \bmod 2^{16}$.
Replace $Y$ with its bitwise-xor with $s \bmod 2^{40}$.
If $L > R$, swap these $2$ values.
Here, $\bmod$ denotes the integer remainder, and bitwise-xor is the operation that takes the xor of each digit in the base $2$ representation.
Output
For each query $2$, output the answer as an integer on one line.
It can be proved that the answer to query $2$ is always a non-negative integer.
Sample
Sample 1
Input
5 5 1 2 3 4 5 2 1 5 2 4 2 1 7 1 2 7 1 2 7 1
Output
6 2 1 3
In $query_1$, $f(x) = |x-1| + |x-2| + |x-3| + |x-4| + |x-5|$. The minimum value $f(x) = 6$ is achieved at $x = 3$.
In $query_3$, the sequence becomes $A = \{1, 2, 5, 4, 5\}$.
Input (after decoding)
5 5 1 2 3 4 5 2 1 5 2 2 4 1 3 5 2 3 5 2 2 4
Sample 2
Input
5 3 1 3 3 3 3 2 1 3 1 3 3 2 3 3
Output
2 0
Input (after decoding)
5 3 1 3 3 3 3 2 1 3 1 1 1 2 1 1
Sample 3
Input
12 12 297387055196 77695545773 487710247651 968023697408 232897057651 196525168957 345567455566 471000070300 447869301680 760529722399 1046863926892 756936270335 1 11 517903130960 2 7 2 1 64976 1015085258696 2 64983 64981 1 9451 82208228357 1 9448 746558666809 2 9441 9450 1 45940 543898836941 2 45945 45949 2 22880 22889 2 51967 51959 1 54322 410448003839
Output
1294183628244 410014701878 1012725946269 1042494843413 1557941228433 2349585145539
Input (after decoding)
12 12 297387055196 77695545773 487710247651 968023697408 232897057651 196525168957 345567455566 471000070300 447869301680 760529722399 1046863926892 756936270335 1 11 517903130960 2 2 7 1 4 829005310492 2 1 3 1 9 416718987495 1 10 961934269659 2 3 8 1 11 993417964722 2 2 6 2 3 10 2 4 12 1 10 538835769031
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
lumc_
Lemma299