@zzzc18 2017-10-25T23:22:51.000000Z 字数 2193 阅读 859

# NOIP2013 花匠

线段树

 for(i=2;i<=N;i++){        int val_f=num[i]-1>=1?F.getmax_f(1,1,num[i]-1):0;        int val_g=num[i]+1<=n?F.getmax_g(1,num[i]+1,n):0;        F.modify(1,num[i],val_g+1,val_f+1);    }

$f$ 就是以当前数为波峰的数列长度
$g$ 就是以当前数为波谷的数列长度

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int MAXN = 100000+9;int b[MAXN];int num[MAXN];int n,N;class Segment_Tree{    private:        struct T{            int ls,rs,left_range,right_range;            int val_f;            int val_g;        }tree[MAXN*4];        int lazy_min[MAXN*4];        int lazy_max[MAXN*4];        int cnt;        void update(int x){            tree[x].val_f=max(tree[tree[x].ls].val_f,tree[tree[x].rs].val_f);            tree[x].val_g=max(tree[tree[x].ls].val_g,tree[tree[x].rs].val_g);        }    public:        int Build(int l,int r){            int now=++cnt;            tree[now].left_range=l;            tree[now].right_range=r;            if(l==r){                return now;            }            int mid=l+r>>1;            tree[now].ls=Build(l,mid);            tree[now].rs=Build(mid+1,r);            update(now);            return now;        }        int getmax_f(int k,int l,int r){            if(l<=tree[k].left_range && tree[k].right_range<=r){                return tree[k].val_f;            }            int mid=tree[k].left_range+tree[k].right_range>>1;            int re=-1;            if(l<=mid)re=max(re,getmax_f(tree[k].ls,l,r));            if(r>=mid+1) re=max(re,getmax_f(tree[k].rs,l,r));            return re;        }        int getmax_g(int k,int l,int r){            if(l<=tree[k].left_range && tree[k].right_range<=r){                return tree[k].val_g;            }            int mid=tree[k].left_range+tree[k].right_range>>1;            int re=-1;            if(l<=mid)re=max(re,getmax_g(tree[k].ls,l,r));            if(r>=mid+1) re=max(re,getmax_g(tree[k].rs,l,r));            return re;        }        void modify(int k,int pos,int val1,int val2){            if(tree[k].left_range==tree[k].right_range){                tree[k].val_f=val1;                tree[k].val_g=val2;                return;            }            int mid=tree[k].left_range+tree[k].right_range>>1;            if(pos<=mid)modify(tree[k].ls,pos,val1,val2);            else modify(tree[k].rs,pos,val1,val2);            update(k);        }}F;int main(){    scanf("%d",&N);    int i;    for(i=1;i<=N;i++){        scanf("%d",&num[i]);        b[i]=num[i];    }    sort(b+1,b+N+1);    n=unique(b+1,b+N+1)-(b+1);    for(i=1;i<=N;i++)        num[i]=lower_bound(b+1,b+n+1,num[i])-b;    F.Build(1,n);    F.modify(1,num[1],1,1);    int ans;    for(i=2;i<=N;i++){        int val_f=num[i]-1>=1?F.getmax_f(1,1,num[i]-1):0;        int val_g=num[i]+1<=n?F.getmax_g(1,num[i]+1,n):0;        F.modify(1,num[i],val_g+1,val_f+1);    }    printf("%d\n",max(F.getmax_f(1,1,n),F.getmax_g(1,1,n)));    return 0;}

• 私有
• 公开
• 删除