序列划分数
狄尔沃斯定理的划分数和序列长度:
不升(下降)————上升
不降(上升)————下降
#include<bits/stdc++.h> using namespace std; int const N=1e5+7; int n,a[N]; vector<int>v; int main(){ cin >> n; for(int i=1;i<=n;++i) cin >> a[i]; for(int i=1;i<=n;++i){ int z=lower_bound(v.begin(),v.end(),a[i])-v.begin(); if(z==v.size()) v.push_back(a[i]); else v[z]=a[i]; } cout << v.size(); return 0; }
//
#include<bits/stdc++.h> using namespace std; #define ll long long #define low(x) x&(-x) int const N=1e5+7; int n; ll tr[N]; void add(ll w,ll p){ for(;p<=n;p+=low(p)){ tr[p]=max(tr[p],w); } } ll ask(ll p){ ll res=0; for(;p;p-=low(p)) res=max(res,tr[p]); return res; } int main(){ cin >> n; for(int i=1,x;i<=n;++i){ cin >> x; add(ask(x-1)+1,x); } cout << ask(n); return 0; }