A9747. LIS of Sequence
编程题
普及/提高-
知识点
题目描述
The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.
Nam created a sequence $a$ consisting of $n$ ( $1<=n<=10^{5}$ ) elements $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{5}$ ). A subsequence $a_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<i_{k}<=n$ is called increasing if $a_{i1}<a_{i2}<a_{i3}<...<a_{ik}$ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences.
Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $i$ ( $1<=i<=n$ ), into three groups:
1. group of all $i$ such that $a_{i}$ belongs to no longest increasing subsequences.
2. group of all $i$ such that $a_{i}$ belongs to at least one but not every longest increasing subsequence.
3. group of all $i$ such that $a_{i}$ belongs to every longest increasing subsequence.
Since the number of longest increasing subsequences of $a$ may be very large, categorizing process is very difficult. Your task is to help him finish this job.
Nam created a sequence $a$ consisting of $n$ ( $1<=n<=10^{5}$ ) elements $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{5}$ ). A subsequence $a_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<i_{k}<=n$ is called increasing if $a_{i1}<a_{i2}<a_{i3}<...<a_{ik}$ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences.
Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $i$ ( $1<=i<=n$ ), into three groups:
1. group of all $i$ such that $a_{i}$ belongs to no longest increasing subsequences.
2. group of all $i$ such that $a_{i}$ belongs to at least one but not every longest increasing subsequence.
3. group of all $i$ such that $a_{i}$ belongs to every longest increasing subsequence.
Since the number of longest increasing subsequences of $a$ may be very large, categorizing process is very difficult. Your task is to help him finish this job.
输入格式
The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.
Nam created a sequence $a$ consisting of $n$ ( $1<=n<=10^{5}$ ) elements $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{5}$ ). A subsequence $a_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<i_{k}<=n$ is called increasing if $a_{i1}<a_{i2}<a_{i3}<...<a_{ik}$ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences.
Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $i$ ( $1<=i<=n$ ), into three groups:
1. group of all $i$ such that $a_{i}$ belongs to no longest increasing subsequences.
2. group of all $i$ such that $a_{i}$ belongs to at least one but not every longest increasing subsequence.
3. group of all $i$ such that $a_{i}$ belongs to every longest increasing subsequence.
Since the number of longest increasing subsequences of $a$ may be very large, categorizing process is very difficult. Your task is to help him finish this job.
Nam created a sequence $a$ consisting of $n$ ( $1<=n<=10^{5}$ ) elements $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{5}$ ). A subsequence $a_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<i_{k}<=n$ is called increasing if $a_{i1}<a_{i2}<a_{i3}<...<a_{ik}$ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences.
Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $i$ ( $1<=i<=n$ ), into three groups:
1. group of all $i$ such that $a_{i}$ belongs to no longest increasing subsequences.
2. group of all $i$ such that $a_{i}$ belongs to at least one but not every longest increasing subsequence.
3. group of all $i$ such that $a_{i}$ belongs to every longest increasing subsequence.
Since the number of longest increasing subsequences of $a$ may be very large, categorizing process is very difficult. Your task is to help him finish this job.
输出格式
Print a string consisting of $n$ characters. $i$ -th character should be '1', '2' or '3' depending on which group among listed above index $i$ belongs to.
输入输出样例
输入 #1
1 4
输出 #1
3
输入 #2
4 1 3 2 5
输出 #2
3223
输入 #3
4 1 5 2 3
输出 #3
3133
说明/提示
The next "Data Structures and Algorithms" lesson will be about Longest Increasing Subsequence (LIS for short) of a sequence. For better understanding, Nam decided to learn it a few days before the lesson.
Nam created a sequence $a$ consisting of $n$ ( $1<=n<=10^{5}$ ) elements $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{5}$ ). A subsequence $a_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<i_{k}<=n$ is called increasing if $a_{i1}<a_{i2}<a_{i3}<...<a_{ik}$ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences.
Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $i$ ( $1<=i<=n$ ), into three groups:
1. group of all $i$ such that $a_{i}$ belongs to no longest increasing subsequences.
2. group of all $i$ such that $a_{i}$ belongs to at least one but not every longest increasing subsequence.
3. group of all $i$ such that $a_{i}$ belongs to every longest increasing subsequence.
Since the number of longest increasing subsequences of $a$ may be very large, categorizing process is very difficult. Your task is to help him finish this job.
Nam created a sequence $a$ consisting of $n$ ( $1<=n<=10^{5}$ ) elements $a_{1},a_{2},...,a_{n}$ ( $1<=a_{i}<=10^{5}$ ). A subsequence $a_{i1},a_{i2},...,a_{ik}$ where $1<=i_{1}<i_{2}<...<i_{k}<=n$ is called increasing if $a_{i1}<a_{i2}<a_{i3}<...<a_{ik}$ . An increasing subsequence is called longest if it has maximum length among all increasing subsequences.
Nam realizes that a sequence may have several longest increasing subsequences. Hence, he divides all indexes $i$ ( $1<=i<=n$ ), into three groups:
1. group of all $i$ such that $a_{i}$ belongs to no longest increasing subsequences.
2. group of all $i$ such that $a_{i}$ belongs to at least one but not every longest increasing subsequence.
3. group of all $i$ such that $a_{i}$ belongs to every longest increasing subsequence.
Since the number of longest increasing subsequences of $a$ may be very large, categorizing process is very difficult. Your task is to help him finish this job.