問題一覧 > 通常問題

No.1786 Maximum Suffix Median (Online)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : chineristACchineristAC / テスター : 👑 Kiri8128Kiri8128
2 ProblemId : 7276 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-25 23:47:42

問題文

$\mathrm{med}(x_1,\ x_2,\ \dots,\ x_n)$ で $x_1,\ x_2,\ \dots,\ x_n$ を昇順に並べた際の $\lfloor\frac{n+1}{2}\rfloor$ 番目の値を表すことにします。ただし、 $\lfloor x \rfloor$ は $x$ 以下の最大の整数を表します。

長さ $N$ の整数列 $A=(A_1,\ A_2,\ \dots,\ A_N)$ が与えられます。

各 $i\ (1 \le i \le N)$ について $\displaystyle ans_i=\max_{1 \le j \le i}\mathrm{med}(A_j,\ A_{j+1},\ \dots,\ A_{i})$ を求めてください。

この問題では $A_i\ (1\le i \le N)$ の代わりに $\displaystyle A'_1=A_1,\ A'_i=A_i \oplus ans_{i-1}\ (2\le i \le N)$ ( $x\oplus y$ で $x,\ y$ のビットごとの排他的論理和を表す)が与えられます。

入力

$N$
$A'_1$
$A'_2$
$\vdots$
$A'_N$
  • $1\le N \le 2 \times 10^5$
  • $0\le A_i < 2^{30}$
  • 与えられる入力はすべて整数

出力

$N$ 行出力してください。

$i$ 行目には $ans_i$ を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
4
3
1
3
3
出力
3
2
2
1

$ans_1=A_1=3$ より $A_2=1\oplus 3 =2$ です。

$ans_2$ については、 $\mathrm{med}(3,\ 2)=2,\ \mathrm{med}(2)=2$ より $ans_2=\max(2,\ 2)=2$ です。よって、$A_3=3 \oplus 2=1$ です。

$ans_3$ については、 $\mathrm{med}(3,\ 2,\ 1)=2,\ \mathrm{med}(2,\ 1)=1,\ \mathrm{med}(1)=1$ より $ans_3=\max(2,\ 1,\ 1)=2$ です。

サンプル2
入力
5
5
1
7
6
2
出力
5
4
4
3
3

サンプル3
入力
20
313880315
1027831872
1016521272
715491090
515143677
167233765
767538848
99016686
531323683
98215187
1072012460
960465505
275131934
1022230062
793158288
930027451
1065190802
1050080658
618013586
51443015
出力
313880315
804656827
325121155
969241489
661718124
780586121
661718124
661718124
953835343
1023474268
953835343
661718124
924265074
661718124
580377474
580377474
501898768
595372930
501898768
519744343

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