問題一覧 > 通常問題

No.1786 Maximum Suffix Median (Online)

レベル : / AI推定難易度 : 2250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : chineristAC / テスター : Kiri8128
お気に入りにしたユーザー ProblemId : 7276 / 自分の提出
問題文最終更新日: 2021-12-25 23:47:42
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
Advent Calendar Contest 2021 (順位表) の他の問題:

Problem Statement

Let $\mathrm{med}(x_1,\ x_2,\ \dots,\ x_n)$ denote the $\lfloor\frac{n+1}{2}\rfloor$-th value when $x_1,\ x_2,\ \dots,\ x_n$ are sorted in ascending order. Here, $\lfloor x \rfloor$ denotes the largest integer not exceeding $x$.

You are given an integer sequence $A=(A_1,\ A_2,\ \dots,\ A_N)$ of length $N$.

For each $i\ (1 \le i \le N)$, find $\displaystyle ans_i=\max_{1 \le j \le i}\mathrm{med}(A_j,\ A_{j+1},\ \dots,\ A_{i})$.

In this problem, instead of $A_i\ (1\le i \le N)$, you are given $\displaystyle A'_1=A_1,\ A'_i=A_i \oplus ans_{i-1}\ (2\le i \le N)$ (where $x\oplus y$ denotes the bitwise XOR of $x,\ y$).

Input

$N$
$A'_1$
$A'_2$
$\vdots$
$A'_N$
  • $1\le N \le 2 \times 10^5$
  • $0\le A_i < 2^{30}$
  • All input values are integers.

Output

Print $N$ lines.

On the $i$-th line, print $ans_i$.

Print a newline at the end.

Sample

Sample 1
Input
4
3
1
3
3
Output
3
2
2
1

Since $ans_1=A_1=3$, we have $A_2=1\oplus 3 =2$.

For $ans_2$, since $\mathrm{med}(3,\ 2)=2,\ \mathrm{med}(2)=2$, we have $ans_2=\max(2,\ 2)=2$. Therefore, $A_3=3 \oplus 2=1$.

For $ans_3$, since $\mathrm{med}(3,\ 2,\ 1)=2,\ \mathrm{med}(2,\ 1)=1,\ \mathrm{med}(1)=1$, we have $ans_3=\max(2,\ 1,\ 1)=2$.

Sample 2
Input
5
5
1
7
6
2
Output
5
4
4
3
3

Sample 3
Input
20
313880315
1027831872
1016521272
715491090
515143677
167233765
767538848
99016686
531323683
98215187
1072012460
960465505
275131934
1022230062
793158288
930027451
1065190802
1050080658
618013586
51443015
Output
313880315
804656827
325121155
969241489
661718124
780586121
661718124
661718124
953835343
1023474268
953835343
661718124
924265074
661718124
580377474
580377474
501898768
595372930
501898768
519744343

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。