BZOJ 3904 最長上升子序列 lkids 線段樹

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<