No.1786 Maximum Suffix Median (Online)
タグ : / 解いたユーザー数 19
作問者 :
chineristAC
/ テスター :
Kiri8128
問題文
$\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もしくは右上の雲マークをクリックしてアカウントを作成してください。