题目地址：http://codeforces.com/contest/474/problem/E
第一次遇到这样的用线段树来维护DP的题目。ASC中也遇到过，当时也非常自然的想到了线段树维护DP，可是那题有简单方法，于是就没写。这次最终写出来了。。
这题的DP思想跟求最长上升子序列的思想是一样的。仅仅只是这里的找前面最大值时会超时，所以能够用线段树来维护这个最大值，然后因为还要输出路径，所以要用线段树再来维护一个每一个数在序列中所在的位置信息。
手残了好多地方，最终调试出来了。。。
代码例如以下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
#define LL __int64
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int INF=0x3f3f3f3f;
const int MAXN=100000;
int maxv[MAXN<<2], cnt, pre[MAXN+10], f[MAXN+10], q_maxp, maxp[MAXN<<2], q_maxv;
LL a[MAXN+10], c[MAXN+10], d[MAXN+10];
void PushUp(int rt)
{
maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
if(maxv[rt<<1]>=maxv[rt<<1|1])
maxp[rt]=maxp[rt<<1];
else
maxp[rt]=maxp[rt<<1|1];
}
void update(int p, int x, int i, int l, int r, int rt)
{
if(l==r)
{
maxv[rt]=x;
maxp[rt]=i;
return ;
}
int mid=l+r>>1;
if(p<=mid) update(p,x,i,lson);
else update(p,x,i,rson);
PushUp(rt);
}
void query(int ll, int rr, int l, int r, int rt)
{
if(ll<=l&&rr>=r)
{
if(q_maxv<maxv[rt])
{
q_maxv=maxv[rt];
q_maxp=maxp[rt];
}
return ;
}
int mid=l+r>>1, ans=0;
if(ll<=mid) query(ll,rr,lson);
if(rr>mid) query(ll,rr,rson);
}
int bin_seach(LL x)
{
int low=0, high=cnt-1, mid;
while(low<=high)
{
mid=low+high>>1;
if(d[mid]==x) return mid;
else if(d[mid]>x) high=mid-1;
else low=mid+1;
}
}
int l_seach(LL x)
{
int low=0, high=cnt-1, mid, ans=-1;
while(low<=high)
{
mid=low+high>>1;
if(d[mid]<=x)
{
ans=mid;
low=mid+1;
}
else high=mid-1;
}
return ans;
}
int r_seach(LL x)
{
int low=0, high=cnt-1, mid, ans=-1;
while(low<=high)
{
mid=low+high>>1;
if(d[mid]>=x)
{
ans=mid;
high=mid-1;
}
else low=mid+1;
}
return ans;
}
void print(int x)
{
if(x==-1) return ;
print(pre[x]);
printf("%d ",x+1);
}
int main()
{
int n, dd, i, x, ans, y, z, max1=-1, pos, tot;
scanf("%d%d",&n,&dd);
for(i=0; i<n; i++)
{
scanf("%I64d",&a[i]);
c[i]=a[i];
}
sort(c,c+n);
d[0]=c[0];
cnt=1;
for(i=1; i<n; i++)
{
if(c[i]!=c[i-1])
{
d[cnt++]=c[i];
}
}
/*for(i=0;i<cnt;i++)
{
printf("%d ",c[i]);
}
puts("");*/
memset(maxv,0,sizeof(maxv));
memset(pre,-1,sizeof(pre));
for(i=0; i<n; i++)
{
x=bin_seach(a[i]);
y=l_seach(a[i]-dd);
z=r_seach(a[i]+dd);
//printf("%d %d %d
",x,y,z);
q_maxp=-1;
q_maxv=-1;
if(y!=-1)
query(0,y,0,cnt-1,1);
if(z!=-1)
query(z,cnt-1,0,cnt-1,1);
update(x,q_maxv+1,i,0,cnt-1,1);
pre[i]=q_maxp;
if(q_maxv==0)
pre[i]=-1;
if(max1<q_maxv+1)
{
max1=q_maxv+1;
pos=i;
}
}
printf("%d
",max1);
print(pos);
return 0;
}