NOIP2013 花匠 DP 线段树优化-白红宇

NOIP2013 花匠 DP 线段树优化

阅读量：5059 次

发布时间：2019-06-12

本文共 1390 字，大约阅读时间需要 4 分钟。

网上一堆题解，我写的是N^2优化的那种，nlogn，O(n)的那种能看懂，但是让我自己在赛场写，肯定没戏了

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              using namespace std;typedef long long LL;const int N=1e5+5;int a[N],b[N],n,cnt;int mx[2][N<<2];int now;void add(int rt,int l,int r,int pos,int t){ if(l==r){ mx[now][rt]=max(mx[now][rt],t); return; } int m=(l+r)>>1; if(pos<=m)add(rt<<1,l,m,pos,t); else add(rt<<1|1,m+1,r,pos,t); mx[now][rt]=max(mx[now][rt<<1],mx[now][rt<<1|1]); }int query(int rt,int l,int r,int x,int y){ if(x<=l&&r<=y) return mx[now][rt]; int ans=0; int m=(l+r)>>1; if(x<=m)ans=max(ans,query(rt<<1,l,m,x,y)); if(y>m)ans=max(ans,query(rt<<1|1,m+1,r,x,y)); return ans;}int main(){ scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); cnt=unique(b+1,b+1+n)-b-1; int pos=lower_bound(b+1,b+1+cnt,a[1])-b; int ans=1; now=0; add(1,1,cnt,pos,1); now=1; add(1,1,cnt,pos,1); for(int i=2;i<=n;++i){ pos=lower_bound(b+1,b+1+cnt,a[i])-b; if(pos!=1){ now=0; int tmp=query(1,1,cnt,1,pos-1)+1; ans=max(ans,tmp); now=1; add(1,1,cnt,pos,tmp); } if(pos!=cnt){ now=1; int tmp=query(1,1,cnt,pos+1,cnt)+1; ans=max(ans,tmp); now=0; add(1,1,cnt,pos,tmp); } } printf("%d\n",ans); return 0;}