Advertisement
konchin_shih

cdq dp

Oct 19th, 2022
875
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.09 KB | None | 0 0
  1. constexpr int maxn=1e4+5;
  2. struct node{int i,val,ans;};
  3. void cdq(V<node>& v,int l,int r){
  4.     if(r-l<=1) return;
  5.     int m=(l+r)>>1;
  6.     cdq(v,l,m);
  7.     sort(v.begin()+l,v.begin()+m,[](node a,node b){
  8.         return a.val<b.val;
  9.         });
  10.         sort(v.begin()+m,v.begin()+r,[](node a,node b){
  11.                 return a.val<b.val;
  12.         });
  13.     int lptr=l-1,curmax=0;
  14.         for(int i=m;i<r;i++){
  15.                 while(lptr+1<m&&v[lptr+1].val<v[i].val)
  16.                         curmax=max(curmax,v[++lptr].ans);
  17.                 if(lptr>=0&&v[lptr].val<v[i].val)
  18.                         v[i].ans=max(v[i].ans,1+curmax);
  19.         }
  20.         sort(v.begin()+m,v.begin()+r,[](node a,node b){
  21.                 return a.i<b.i;
  22.         });
  23.         cdq(v,m,r);
  24. }
  25. static inline void solve(){
  26.     int n;cin>>n;
  27.     V<node> v(n);
  28.     for(int i=0;i<n;i++)
  29.                 cin>>v[i].val,v[i].i=i,v[i].ans=1;
  30.     cdq(v,0,n);
  31.     sort(v.begin(),v.end(),[](node a,node b){
  32.         return a.i<b.i;
  33.     });
  34.     int ans=0;
  35.     for(auto i:v)
  36.                 ans=max(ans,i.ans);
  37.     cout<<ans<<endl;
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement