(nlogn求LIS，确定状态唯一性）LIS of Sequence CodeForces

本文主要是介绍(nlogn求LIS，确定状态唯一性）LIS of Sequence CodeForces - 486E，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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 ≤ 105) elements a1, a2, …, an (1 ≤ ai ≤ 105). A subsequence ai1, ai2, …, aik where 1 ≤ i1 < i2 < … < ik ≤ n is called increasing if ai1 < ai2 < ai3 < … < aik. 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:

group of all i such that ai belongs to no longest increasing subsequences.
group of all i such that ai belongs to at least one but not every longest increasing subsequence.
group of all i such that ai 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.

Input
The first line contains the single integer n (1 ≤ n ≤ 105) denoting the number of elements of sequence a.

The second line contains n space-separated integers a1, a2, …, an (1 ≤ ai ≤ 105).

Output
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.

Examples
Input
1
4
Output
3
Input
4
1 3 2 5
Output
3223
Input
4
1 5 2 3
Output
3133
Note
In the second sample, sequence a consists of 4 elements: {a1, a2, a3, a4} = {1, 3, 2, 5}. Sequence a has exactly 2 longest increasing subsequences of length 3, they are {a1, a2, a4} = {1, 3, 5} and {a1, a3, a4} = {1, 2, 5}.

In the third sample, sequence a consists of 4 elements: {a1, a2, a3, a4} = {1, 5, 2, 3}. Sequence a have exactly 1 longest increasing subsequence of length 3, that is {a1, a3, a4} = {1, 2, 3}.

题意：
n个数，每一个数有三种状态：
（1）不位于任何LIS序列上
（2）位于LIS序列上但是不是所有LIS序列上（LIS序列可能很多，如1 3 2 5，其中2在LIS序列1 2 5上，但是1 3 5也是一个LIS序列）
（3）位于唯一LIS序列上（如1 3 2 5中的5和1）
输出每个数表示的状态
思路：
（1）题目数据开到了1e5，首先求LIS的过程就不能直接n^2转移。有两种nlogn求LIS的方法，一种是 $\color{red}{重新建模}$ 。

原有的dp数组定义是dp[i],i代表a[i]结尾的LIS长度。这样的转移方程是dp[i] = max(dp[j] + 1)(i > j && a[i] > a[j])。
新的定义是dp[i]:长度为i的最长上升子序列元素末尾的最小值。例如 1 3 2 5，1 3 和 1 2都能到达5的状态达到3的长度，但是2比3相对更优。在序列长度相同的前提下， $\color{red}{肯定是}$ 结尾数字越小，未来能够匹配的相对更多。该过程可以用二分优化，每次将a[i]更新到能够更新的最后位置。复杂度为nlogn
对于原有模型，麻烦的主要在于那个小于a[i]并且lis值最大的子状态的找寻。学习树状数组写逆序对的时候，为了找寻i > j && a[i] < a[j]的数的个数，我们是将a[i]当做下标，依次更新。同样的，我们需要找寻i > j && a[i] > a[j] && dp[j]最大的j，我们或许也可以通过树状数组求解
我们要满足i > j的条件，直接按顺序for过来就可以了。要满足a[i] > a[j]的条件，类似逆序对的做法，以a[i]/a[j]为下标，下标小于a[i]的所有下标数，都是可选的a[j]。要找寻max{dp[j]},我们则可以将树状数组改为求max的过程，而每一个下标存的是到该位置的最长上升子序列长度。这样寻找子状态过程的复杂度就优化为了nlogn。
比较好的博客：树状数组求LIS[https://www.cnblogs.com/Rosebud/p/9845935.html]

（2）除了求LIS的过程，题目还需要求是否位于LIS上。但是在每一个位置只能得到以位置结尾的LIS。可行的办法是维护两个dp数组，dp1[i]记录i的LIS，dp2[i]记录n到i的最长下降子序列。只要dp1[i] + dp2[i] = LIS + 1（加1是因为a[i]在两个dp数组中都出现了），就说明i在LIS上。但是即使思路得出，计算dp2[i]也是需要技巧的。

我们需要计算n到i的最长下降子序列 -->计算i到n的最长上升子序列 --> 计算原序列翻转后1到i的最长下降子序列（此时dp状态也翻转了） --> 计算现在这个序列大小关系反转后1到i的最长上升子序列。（可以加个负号，但由于是作为下标，不能成为负数，那么就得用一个很大的数和每个数做差），那么由此方法得出的dp数组为dp[i]：1到i的的最长上升子序列，翻转一下就成了计算n到i的最长下降子序列。

（3）题目还要判断是否在唯一的LIS上。在**（2）**中我们已经能够判断出i是否在LIS上了，还是考虑样例1 3 2 5，很明显1和5在唯一的LIS上，而3和2不在唯一的LIS上，一个明显的特点是dp1[i] + dp2[i] - 1 = LIS的情况中，3和2的dp1都为2，或许这里是突破口。由此考虑状态的定义：LIS = max{dp1[k]} = dp1[i] + dp2[i] - 1;其中一定有k >= i，那么dp[k]一定是由dp[i]转移过来的，假设dp[i]不唯一，转移的过程一定不唯一，那么由i转移得到的LIS也一定不唯一，再由此记录一下所有满足在LIS上的dp1[i]判一下重就可以了。

总结： 写的有点啰嗦了，不过还算是把自己解整道题的学习过程给写出来了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>using namespace std;
const int maxn = 1e5+7;
int c[maxn];
int a[maxn];
int dp1[maxn],dp2[maxn];
int res[maxn];
map<int,int> mp;
void add(int i,int val)
{while(i < maxn){c[i] = max(c[i],val);i += (i & (-i));}
}int query(int i)
{int ans = 0;while(i){ans = max(ans,c[i]);i -= (i & (-i));}return ans;
}int main()
{int n;scanf("%d",&n);int LIS = 0;for(int i = 1;i <= n;i++){scanf("%d",&a[i]);dp1[i] = 1 + query(a[i] - 1);add(a[i],dp1[i]);LIS = max(LIS,dp1[i]);}reverse(a + 1,a + 1 + n);memset(c,0,sizeof(c));for(int i = 1;i <= n;i++){a[i] = maxn - a[i] + 1;dp2[i] = 1 + query(a[i] - 1);add(a[i],dp2[i]);dp2[i] = query(a[i] - 1) + 1;}reverse(dp2 + 1,dp2 + 1 + n);for(int i = 1;i <= n;i++){if(dp1[i] + dp2[i] - 1 == LIS){mp[dp1[i]]++;}elseres[i] = 1;}for(int i = 1;i <= n;i++){if(dp1[i] + dp2[i] - 1 == LIS){if(mp[dp1[i]] == 1)res[i] = 3;elseres[i] = 2;}printf("%d",res[i]);}return 0;
}