九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/11991119
题意：
n个数 d个距离
下面n个数的序列，求序列中的最长单调递增子序列，保证子序列的每个元素相距要>d (普通的LIS d=0 )
按值建树，从[1,maxsum+1] ，最大可能是10^5 (即ai的最大值,a[i]上界太大不能用值建树,会MT)
思路1：
对于i点, dp[i]= [1- a[i] ) 最大的LIS + 1
而 [1-a[i] ] 的LIS 要延迟更新，防止 i 的LIS影响到 [i-d,i]的LIS ,所以每次保证LIS 都是[1, i-d-1 ] 状态的LIS 值
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <math.h>
#include <queue>
#define N 101000
#define ll int
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1)
using namespace std;
inline ll Min(ll a,ll b){return a>b?b:a;}
inline ll Max(ll a,ll b){return a>b?a:b;}
int p[N],d,dp[N];struct node {int l,r,mx;
}tree[N*4];void build(int l,int r,int id){tree[id].l = l, tree[id].r = r;tree[id].mx=0;if( l == r ) return ;int mid = MID(l,r);build( l, mid, LL(id)); build( mid+1, r, RR(id));}int query_inte(int l, int r, int id){ //查询[l,r]上 LIS的长度if(l <= tree[id].l && tree[id].r <= r)return tree[id].mx;int mid = MID(tree[id].l,tree[id].r);if(r<=mid) return query_inte( l, r, LL(id));if(l>mid) return query_inte( l, r, RR(id));return Max( query_inte( l, r, LL(id)) , query_inte( l, r, RR(id)) );}void updata(int pos,int value,int id){//更新pos所在区间(pos所在的区间一定是往后的)，所有在pos后面的值的子序列长度都增加if(tree[id].l == tree[id].r){ tree[id].mx = Max(tree[id].mx, value); return ;}int mid = MID(tree[id].l, tree[id].r);if(pos<=mid) updata(pos,value,LL(id));else updata(pos,value,RR(id));tree[id].mx = Max( tree[LL(id)].mx, tree[RR(id)].mx);
}int main(){int n,a,b,i;while(~scanf("%d %d",&n,&d)){int maxx=0;for(i=1;i<=n;i++)scanf("%d",&p[i]),maxx=Max(maxx,p[i]);build(1,maxx+1,1); //建树，从1-序列中最大的数 +1是给更新最大的数的子序列用int ans=0;for(i=1;i<=n;i++){//对于i这个点，线段树里记录的是 前i-d-1 个点的状态，即对于数字 p[i]，有多少个数字是小于p[i]且是LISif(i>d+1) updata(p[i-d-1]+1,dp[i-d-1],1);//p[i-d-1]是不能算的，因为是单调递增//updata(p[i],dp[i]) 更新[p[i],+无穷]区间，这个区间的子序列个数最多为dp[i]if(p[i]>0) dp[i] = query_inte(1,p[i],1)+1;//p[i]==0不能递归结束的，要特判一下 1-p[i]段的最长LIS +1else dp[i]=1;//p[i]==0 那么子序列一定只有自己ans=Max(ans,dp[i]);}printf("%d\n",ans);}return 0;
}
转载一个按下标建树的 [1, n ](这个不会被Ai的大小影响, 标准解法 )
先按a[] 小到大排序
对于a[i] ,他的子序列长度=LIS [1,i-d-1] +1 ，更新a[i] 时 , 保证a[]从小更新到大(排序的作用) 然后所有 [1, a[i].id - d -1 ] 的子序列都增加 1
http://www.cnblogs.com/xianxingwuguan/p/3337969.html
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=111111;
#define L(x) 2*x
#define R(x) 2*x+1
struct node
{int l,r,mx;int mid(){return (l+r)>>1;}
}tree[5*maxn];
struct NODE
{int val,id;
}pp[maxn];
bool cmp(NODE a,NODE b)
{if(a.val==b.val)return a.id>b.id;return a.val<b.val;
}
void pushup(int p)
{tree[p].mx=max(tree[L(p)].mx,tree[R(p)].mx);
}
void build(int p,int l,int r)
{tree[p].l=l;tree[p].r=r;tree[p].mx=0;if(l==r)return;int m=tree[p].mid();build(L(p),l,m);build(R(p),m+1,r);pushup(p);
}
void update(int p,int pos,int val)
{if(tree[p].l==tree[p].r){tree[p].mx=max(tree[p].mx,val);return;}int m=tree[p].mid();if(pos<=m)update(L(p),pos,val);else update(R(p),pos,val);pushup(p);
}
int query(int p,int l,int r)
{if(l>r)return 0;if(tree[p].l>=l&&tree[p].r<=r)return tree[p].mx;int m=tree[p].mid();int ans=-1;if(l<=m)ans=max(ans,query(L(p),l,r));if(r>m)ans=max(ans,query(R(p),l,r));return ans;
}
int main()
{int i,j,k,m,n,d;while(~scanf("%d%d",&n,&d)){for(i=1;i<=n;i++)scanf("%d",&pp[i].val),pp[i].id=i;sort(pp+1,pp+n+1,cmp);// for(i=1;i<=n;i++)cout<<pp[i].val<<" ";cout<<endl;build(1,1,n);int ans=0;for(i=1;i<=n;i++){j=pp[i].id;k=query(1,1,j-d-1);ans=max(ans,k+1);update(1,j,k+1);}printf("%d\n",ans);}return 0;
}
