线段树 95分 WA on #19 求调

#include <bits/stdc++.h>
using namespace std;

const int maxn=2e6+5;
#define ls id<<1
#define rs id<<1|1
int n,lt[maxn],rt[maxn],f,ans;
int a[maxn],tr[maxn],lz[maxn],u[maxn];
void pushup(int id){
	tr[id]=max(tr[ls],tr[rs]);
}
void addtag(int id,int x){
	tr[id]=x;
	lz[id]=x;
}
void pushdown(int id){
	if(lz[id]) addtag(ls,lz[id]);
	if(lz[id]) addtag(rs,lz[id]);
	lz[id]=0;
}
void build(int l,int r,int id){
	lt[id]=l,rt[id]=r;
	if(l==r) return ;
	int mid=l+r>>1;
	build(l,mid,ls);
	build(mid+1,r,rs);
}
void add(int id,int l,int r,int x){
	if(l<=lt[id] && rt[id]<=r){
		addtag(id,x);
		return ;
	}
	int mid=lt[id]+rt[id]>>1;
	pushdown(id);
	if(l<=mid) add(ls,l,r,x);
	if(r>mid) add(rs,l,r,x);
	pushup(id);
}
int query(int id,int l,int r){
	if(l<=lt[id] && rt[id]<=r) return tr[id];
	int mid=lt[id]+rt[id]>>1;
	pushdown(id);
	int ret=0;
	if(l<=mid) ret=max(ret,query(ls,l,r));
	if(r>mid) ret=max(ret,query(rs,l,r));
	return ret;
}
int main(){
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	build(1,5e5,1);
	memset(u,-1,sizeof(u));
	for(int i=1;i<=n;i++){
		int x=a[i];
		f=u[x]+1;
		add(1,x,x,max(query(1,x,x),f));
		u[x]=max(query(1,1,x-1),query(1,x+1,5e5))+1;
		ans=max(ans,f);
	}
	cout << ans << "\n";
	return 0;
}