序列划分数

狄尔沃斯定理的划分数和序列长度：
不升（下降）————上升
不降（上升）————下降

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