navigation switch
Home
Contests
Notification
Clarification
Problems
Ranklist
Status
HackStatus
×
AC 后请勿重新提交,最终分数以最后一次 AC 时间为准~
毒瘤数据结构题
Accepts: 937
Submissions: 3725
Time Limit: 4000/2000 MS (Java/Others)
Memory Limit: 196608/196608 K (Java/Others)
Problem Description
给你一个长为 $n$,初始全为 $0$ 的序列,有 $n$ 次操作,每次可以: `1 x` 表示把 $x$ 位置修改为 $1$。 `2 x` 表示查询,如果将 $x$ 位置修改为 $1$,求最大的 $i$ 满足序列位置 $1$ 到 $i-1$ 上的值均为 $1$。这里不实际上做出这一次修改。
Input
本题无多组测试数据。 第一行一个数表示 $n$。 之后 $n$ 行,每行两个数,格式如上述,表示一次修改或者查询操作。 保证 $1 \le n \le 5\times 10^6$,每次给出的 $x$ 都在 $[1,n]$ 以内。 数据范围较大,请使用效率较高的读入方式。
Output
对于每个查询操作,输出一行一个数表示答案。
Sample Input
Copy
10 2 4 2 3 1 1 2 1 1 1 2 2 1 3 2 10 1 2 2 5
Sample Output
Copy
1 1 2 3 2 4