BZOJ 3904 最长上升子序列 lkids 线段树
2015-03-08 11:11:14         来源：世界

f[i][1]表示第i个数为序列中的较小值的最长子序列

(真简略)

```#include
#include
#include
#include
#define M 200200
using namespace std;
template struct Segtree{
Segtree *ls,*rs;
int val;
Segtree():ls(0x0),rs(0x0),val(_) {}
friend void Update(Segtree *&p,int x,int y,int l,int r,int val)
{
int mid=x+y>>1;
if(!p) p=new Segtree;
if(x==l&&y==r)
{
p->val=max(p->val,val);
return ;
}
if(r<=mid)
Update(p->ls,x,mid,l,r,val);
else if(l>mid)
Update(p->rs,mid+1,y,l,r,val);
else
Update(p->ls,x,mid,l,mid,val) , Update(p->rs,mid+1,y,mid+1,r,val);
}
friend int Get_Ans(Segtree *p,int x,int y,int pos)
{
int mid=x+y>>1;
if(!p) return _;
if(x==y) return p->val;
if(pos<=mid)
return max(Get_Ans(p->ls,x,mid,pos),p->val);
else
return max(Get_Ans(p->rs,mid+1,y,pos),p->val);
}
};
Segtree< 0> *tree0=new Segtree< 0>;
Segtree<-1> *tree1=new Segtree<-1>;
int n,k,ans;
int a[M],f[M][2];
int main()
{
int i;
cin>>n>>k;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]-k>=0)
{
f[i][0]=Get_Ans(tree1,0,100000000,a[i]-k)+1;
Update(tree0,0,100000000,0,a[i],f[i][0]);
}
if(a[i]+k<100000000)
{
f[i][1]=Get_Ans(tree0,0,100000000,a[i]+k)+1;
Update(tree1,0,100000000,a[i],100000000,f[i][1]);
}
ans=max(ans,f[i][0]);
ans=max(ans,f[i][1]);
}
cout<

```