LIS的三种O(nlogn)解法

题目链接：LIS - 洛谷

1.最常见的做法，用栈来处理

#include 
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pii pair
#define int long long
#define ls o<<1
#define rs o<<1|1
const int N = 1e5+5;
int n, st[N], tot=0;void solve(){cin>>n;FOR(i,1,n){int x; cin>>x;if(x>st[tot]) st[++tot]=x; //最大长度更新else{int p=lower_bound(st+1,st+tot+1,x)-st; //求最大不降子序列st[p]=x; //替换最优的最后数字}}cout<>T;while(T--) solve();
}

2.栈的做法的优化，更加好写，看下代码就能懂，原理和栈那个一样

#include 
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pii pair
const int N = 1e5+5, inf=0x3f3f3f3f;
int n, h[N];
void solve(){cin>>n;memset(h,0x7f,sizeof(h));FOR(i,1,n){int x; cin>>x;int p=lower_bound(h+1,h+n+1,x)-h;h[p]=x;}int p=lower_bound(h+1,h+n+1,inf)-h;cout<>T;while(T--) solve();
}

3.权值线段树的解法

#include 
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pii pair
#define int long long
#define ls o<<1
#define rs o<<1|1
const int N = 1e5+5;
int n, t[N<<2];void upd(int o,int l,int r,int pos,int val){if(l==r) {t[o]=val; return;}int mid = l+r>>1;if(pos<=mid) upd(ls,l,mid,pos,val);else upd(rs,mid+1,r,pos,val);t[o] = max(t[ls],t[rs]);
}
int query(int o,int l,int r,int x,int y){if(x<=l && r<=y) return t[o];int mid = l+r>>1, mx=0;if(x<=mid) mx=max(mx, query(ls,l,mid,x,y));if(y>mid)  mx=max(mx, query(rs,mid+1,r,x,y));return mx;
}
void solve(){cin>>n;FOR(i,1,n){int x; cin>>x;int mx = query(1,1,n,1,x);upd(1,1,n,x,mx+1);}cout<>T;while(T--) solve();
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！