P4309 [TJOI2013] 最长上升子序列题解

正文

单调队列?单调锤子队列！！

本题的操作可以省略成：

• 单点修改
• 区间查询

好极了，此时我们有两种选择：

线段树和树状数组，（平衡树，真不会，下一位

因为不需要其他操作，所以我们还是选择更小巧更可爱的树状数组吧。

关于vector

vector的insert操作支持在某个迭代器位置插入元素、可以插入多个。复杂度与 pos 距离末尾长度成线性而非常数的。

多么优秀，我简直要流泪了。

操作很简单，不解释了。

贴码

#include<bits/stdc++.h>/*1010*/
#define MAXN 1000010
using namespace std;
//ifstream is("lis.in",ios::in);
//ofstream os("lis.in",ios::out);
//#define cin is
//#define cout os
int lowbit(int x){
	return x&(-x);
}
int n,tr[MAXN],ans[MAXN]; 
vector<int> a;
inline void update(int x,int val){
	while(x<=n){
		tr[x]=max(tr[x],val);
		x+=lowbit(x);
	}
} 
inline int query(int x){
	int t=0;
	while(x){
		t=max(t,tr[x]);
		x-=lowbit(x);	
	} 
	return t;
}
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		a.insert(x+a.begin(),i);
	} 
	for(int i=0,mk;i<n;i++){
		mk=a[i];
		ans[mk]=query(mk)+1;
		update(mk,ans[mk]);
	}
	for(int i=1;i<=n;i++){
		ans[i]=max(ans[i],ans[i-1]);
		cout<<ans[i]<<"\n";
	}
	return 0;
}