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