大数据LIS （贪心+二分优化/树状数组优化）

P1439 【模板】最长公共子序列 - 洛谷 

题目描述（原线性dp）

给出 1,2,…,n 的两个排列 P1​ 和 P2​ ，求它们的最长公共子序列。

输入格式

第一行是一个数 n。

接下来两行，每行为 n 个数，为自然数 1,2,…,n 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

输入输出样例

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

3

说明/提示

• 对于 50%50% 的数据， n≤103；
• 对于 100%100% 的数据， n≤105。

思路：

两个序列求最长公共子序列，根据题意，两个序列都是1-n的全排列，我们可以利用map进行重排，把第一个序列改成上升序列，那么原问题就转化为了求序列的最长上升子序列 

贪心+二分优化：

我们枚举map重排后的新数列，维护一个答案数组是上升子序列，如果当前元素大于答案数组最后一个元素，直接加进去答案数组

否则，在答案数组里找见第一个大于当前元素的元素，将其修改为当前元素

因为如果要这个元素构造出的新数列比没有这个元素的答案数列长，那么这个元素之前的元素和答案数列前面的元素相同，后面的与答案数列无关，直接替换掉第一个大于它的元素即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int main(){cin>>n;vector<int>a(n+1);map<int,int>m;for(int i=1;i<=n;i++){int t;cin>>t;m[t]=i;     //map重排}for(int i=1;i<=n;i++){int t;cin>>t;a[i]=m[t];}vector<int>ans;ans.push_back(a[1]);for(int i=2;i<=n;i++){if(a[i]>ans[ans.size()-1])ans.push_back(a[i]);  //添加至最长递增子序列末端else{int t=upper_bound(ans.begin(),ans.end(),a[i])-ans.begin();  //找第一个大于的数ans[t]=a[i];    //更改为a[i]}}cout<<ans.size();return 0;
}

 树状数组优化

之前思路一样，然后利用树状数组储存当前元素为 i 时的最大的序列长度

每次枚举新数列，修改大于这个数的 f [ i ] 为当前数列的长度+1

用当前数列长度更新答案即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;int f[100005];      //树状数组 f[i] 记录当前元素为i时LIS序列的元素个数int query(int x){   //查询小于等于x的序列个数int ans=0;while(x){ans=max(ans,f[x]);x-=(x&(-x));}return ans;
}void modify(int x,int y){while(x<100005){f[x]=max(f[x],y);x+=x&(-x);}
}int main(){cin>>n;vector<int>a(n+1);map<int,int>m;      //映射处理，使数组1变成上升序列for(int i=1;i<=n;i++){int t;cin>>t;m[t]=i;}for(int i=1;i<=n;i++){      //求数组2的LISint t;cin>>t;a[i]=m[t];}int ans=0;for(int i=1;i<=n;i++){modify(a[i],query(a[i])+1);     //大于等于a[i]的数存的序列长度为当前长度+1ans=max(ans,query(a[i]));       //查询小于等于当前值的序列长度}cout<<ans;return 0;
}