問題一覧 > 通常問題

No.925 Kizuna Extra

レベル : / AI推定難易度 : 2725 / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 11
作問者 : lumc_ / テスター : Lemma299 polylogK
お気に入りにしたユーザー ProblemId : 3393 / 自分の提出
問題文最終更新日: 2019-11-08 20:00:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 230 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。