NOIP2013 花匠

线段树

我可以说不会正解么？

也相当于DP，对于当前的数值，我们求以这个数为波峰/波谷结尾的最长的波峰、波谷交替的序列，这样就可以用线段树维护值域，每个值对应的是以这个值结尾的最长的满足条件的数列长度

在这里 $\large{\downarrow}$

 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$ 就是以当前数为波谷的数列长度
将这个数值插入线段树时，将上面求的两个值+1再交换（波峰波谷交替）就行了

#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;
}