Codeforces ラウンド #271 (ディビジョン 2) 質問 E の柱 (セグメント ツリー メンテナンス DP)_html/css_WEB-ITnose

問題アドレス: 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|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;}