Codeforces Round #271 (Div. 2) Question E Pillars (Segment Tree Maintenance DP)_html/css_WEB-ITnose

Problem address: http://codeforces.com/contest/474/problem/E

This is the first time I encountered this kind of problem using line segment trees to maintain DP. I also encountered it in ASC. At that time, I naturally thought of maintaining DP with line segment trees, but there was a simple method for that question, so I didn't write it. This time I finally wrote it. .

The DP idea of ​​this question is the same as the idea of ​​finding the longest ascending subsequence. However, the search for the previous maximum value here will time out, so you can use a line segment tree to maintain this maximum value, and then because you need to output the path, you need to use a line segment tree to maintain the position information of each number in the sequence.

After a lot of handicaps, I finally debugged it. . .

The code is as follows:

#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|1const 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\n",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\n",max1);    print(pos);    return 0;}