CodeforcesRound#271(Div.2)E题Pillars（线段树维护DP）_html/css_WEB-ITnose

第一次遇到这种用线段树来维护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 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;="" 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));="" x="bin_seach(a[i]);" y="l_seach(a[i]-dd);" z="r_seach(a[i]+dd);" %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)" if(max1<q_maxv+1)="" max1="q_maxv+1;" pos="i;" printf("%d\n",max1);="" print(pos);="" return="" 0;}<="" script=""></n;></maxv[rt])></set></map></queue></ctype.h></math.h></stdlib.h></cstring></string></cstdio></iostream>