103782: [Atcoder]ABC378 C - Repeating
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：15
Solved：0
Description
Score : $300$ points
Problem Statement
You are given a sequence of $N$ positive numbers, $A = (A_1, A_2, \dots, A_N)$. Find the sequence $B = (B_1, B_2, \dots, B_N)$ of length $N$ defined as follows.
- For $i = 1, 2, \dots, N$, define $B_i$ as follows:
- Let $B_i$ be the most recent position before $i$ where an element equal to $A_i$ appeared. If such a position does not exist, let $B_i = -1$.
More precisely, if there exists a positive integer $j$ such that $A_i = A_j$ and $j < i$, let $B_i$ be the largest such $j$. If no such $j$ exists, let $B_i = -1$.
- Let $B_i$ be the most recent position before $i$ where an element equal to $A_i$ appeared. If such a position does not exist, let $B_i = -1$.
Constraints
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\dots$ $A_N$
Output
Print the elements of $B$ in one line, separated by spaces.
Sample Input 1
5 1 2 1 1 3
Sample Output 1
-1 -1 1 3 -1
- $i = 1$: There is no $1$ before $A_1 = 1$, so $B_1 = -1$.
- $i = 2$: There is no $2$ before $A_2 = 2$, so $B_2 = -1$.
- $i = 3$: The most recent occurrence of $1$ before $A_3 = 1$ is $A_1$, so $B_3 = 1$.
- $i = 4$: The most recent occurrence of $1$ before $A_4 = 1$ is $A_3$, so $B_4 = 3$.
- $i = 5$: There is no $3$ before $A_5 = 3$, so $B_5 = -1$.
Sample Input 2
4 1 1000000000 1000000000 1
Sample Output 2
-1 -1 2 1
Output
得分：300分
问题陈述
给定一个由$N$个正数组成的序列，$A = (A_1, A_2, \dots, A_N)$。找出长度为$N$的序列$B = (B_1, B_2, \dots, B_N)$，定义如下。
- 对于$i = 1, 2, \dots, N$，定义$B_i$如下：
- 令$B_i$为$i$之前最近的位置，在该位置上出现了一个等于$A_i$的元素。如果这样的位置不存在，令$B_i = -1$。
更准确地说，如果存在一个正整数$j$使得$A_i = A_j$且$j < i$，令$B_i$为最大的这样的$j$。如果这样的$j$不存在，令$B_i = -1$。
- 令$B_i$为$i$之前最近的位置，在该位置上出现了一个等于$A_i$的元素。如果这样的位置不存在，令$B_i = -1$。
约束条件
- $1 \leq N \leq 2 \times 10^5$
- $1 \leq A_i \leq 10^9$
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出：
$N$ $A_1$ $A_2$ $\dots$ $A_N$
输出
在一行中打印$B$的元素，元素之间用空格分隔。
样本输入 1
5 1 2 1 1 3
样本输出 1
-1 -1 1 3 -1
- $i = 1$：在$A_1 = 1$之前没有1，所以$B_1 = -1$。
- $i = 2$：在$A_2 = 2$之前没有2，所以$B_2 = -1$。
- $i = 3$：在$A_3 = 1$之前最近的1是$A_1$，所以$B_3 = 1$。
- $i = 4$：在$A_4 = 1$之前最近的1是$A_3$，所以$B_4 = 3$。
- $i = 5$：在$A_5 = 3$之前没有3，所以$B_5 = -1$。
样本输入 2
4 1 1000000000 1000000000 1
样本输出 2
-1 -1 2 1