题目大意：给定一个序列，求以较小数开始的锯齿子序列，，使相邻两项之间差值不小于k
令f[i][0]表示第i个数为序列中的较大值的最长子序列
f[i][1]表示第i个数为序列中的较小值的最长子序列
暴力转移是O(n^2)的
我们发现决策点的值都是连续的一段区间 因此用线段树维护一下就行了
(真简略)
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 200200using namespace std;template<int _> 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);elseUpdate(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);elsereturn 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<<ans<<endl;return 0;}
变幻原是永恒，我们唯有用永恒的诺言制约世事的变幻。
