BZOJ 3904 最长上升子序列 lkids 线段树

题目大意：给定一个序列，求以较小数开始的锯齿子序列，使相邻两项之间差值不小于k

令f[i][0]表示第i个数为序列中的较大值的最长子序列

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

暴力转移是O(n^2)的

我们发现决策点的值都是连续的一段区间 因此用线段树维护一下就行了

(真简略)

#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<