E. Pillars（Codeforces Round #271)

代碼：

//156ms
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1e5+10;
int pre[maxn];//記錄前一個點
long long num[maxn];
long long a[maxn];
int cur;
struct node
{
    int maxcou;//以這個高度結尾的最大長度
    int pos;//以這個高度結尾的元素的位置
}tree[maxn<<2];
void build(int rt,int l,int r)
{
    if(l==r)
    {
        tree[rt].maxcou=0;
        tree[rt].pos=0;
        return;
    }
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    tree[rt].maxcou=0;
    tree[rt].pos=0;
}
int Rfind ( long long x ) {
    int l = 1 , r = cur ;
    while ( l < r ) {
        int m = ( l + r ) / 2 ;
        if ( a[m] >= x ) r = m ;
        else l = m + 1 ;
    }
    return l ;
}

int Lfind ( long long x ) {
    int l = 1 , r = cur ;
    while ( l < r ) {
        int m = ( l + r + 1 ) / 2 ;
        if ( a[m] <= x ) l = m ;
        else r = m - 1 ;
    }
    return r ;
}
void update(int x,int v,int i,int rt,int l,int r)
{
    if(l==r)
    {
        if(v>tree[rt].maxcou)
        {
            tree[rt].maxcou=v;
            tree[rt].pos=i;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
    update(x,v,i,rt<<1,l,mid);
    else
    update(x,v,i,rt<<1|1,mid+1,r);
    if(tree[rt<<1].maxcou>tree[rt<<1|1].maxcou)
    {
        tree[rt].maxcou=tree[rt<<1].maxcou;
        tree[rt].pos=tree[rt<<1].pos;
    }
    else
    {
        tree[rt].maxcou=tree[rt<<1|1].maxcou;
        tree[rt].pos=tree[rt<<1|1].pos;
    }
}
int maxcount,maxpos;
void query(int L,int R,int rt,int l,int r)
{
    if(L>R)
    return;
    if(L<=l&&R>=r)
    {
        if(tree[rt].maxcou>maxcount)
        {
            maxcount=tree[rt].maxcou;
            maxpos=tree[rt].pos;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid)
    query(L,R,rt<<1,l,mid);
    if(R>mid)
    query(L,R,rt<<1|1,mid+1,r);
}
void prin(int u)
{
    if(pre[u]!=0)
    {
        prin(pre[u]);
        printf("%d ",pre[u]);
    }
    return;
}
int main()
{
    int n,k,ids=1,ans=1;
    scanf("%d%d",&n,&k);
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=n;i++)
    {
        scanf("%I64d",&num[i]);
        a[i]=num[i];
    }
    sort(a+1,a+n+1);
    cur=1;
    for(int i=2;i<=n;i++)//離散化，以元素的個數來建樹，每個葉子節點代表一個高度
    if(a[i]!=a[cur])
    {
        a[++cur]=a[i];
    }
    build(1,1,cur);
    update(Lfind(num[1]),1,1,1,1,cur);
    pre[1]=0;
    for(int i=2;i<=n;i++)
    {
        int L=Lfind(num[i]-k);//小於num[i]-k的最大位置
        int R=Rfind(num[i]+k);//大於num[i]+k的最小位置
        maxcount=0,maxpos=0;
        if(a[L]+k<=num[i])
        {
            query(1,L,1,1,cur);
        }
        if(num[i]+k<=a[R])
        {
            query(R,cur,1,1,cur);
        }
        update(Lfind(num[i]),maxcount+1,i,1,1,cur);
        pre[i]=maxpos;
        if(maxcount+1>ans)
        {
            ans=maxcount+1;
            ids=i;
        }
    }
    printf("%d\n",ans);
    prin(ids);
    printf("%d\n",ids);
    return 0;
}

#include 
#include 
#include 
#include 
#include 
#include 
const int maxn=100000+100;
using namespace std;
int main() {
		int n, d;
		scanf("%d%d",&n,&d);
		long long h[maxn];
		int z[maxn],p[maxn];

		for(int i=0; i=d && z[j]+1>z[i]){
					z[i]=z[j]+1;
					p[i]=j;
				}
			}
		}
		int max=-100,index;
		for(int i=0; imax) {
				max=z[i];
				index=i;
			}
		}
		printf("%d\n",max);
		vector  a;
		a.push_back(index);
		max--;
		while(max>0){
			index=p[index];
			a.push_back(index);
			max--;
		}
		for(int i=a.size()-1; i>=0; i--)
		{
		    printf("%d ",a[i]+1);
		}
}