分别求最长上升子序列和最长下降子序列。O(nlogn)

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;
    vector<int>v(n), dp_up, dp_down;
    for(auto &i : v) cin >> i;

    dp_up.emplace_back(v[0]);
    for(int i = 0; i < n; i++){
        if(v[i] > *max_element(dp_up.begin(), dp_up.end())){
            dp_up.emplace_back(v[i]);
        }
        else{
            int l = -1, r = dp_up.size();
            while(l + 1 != r){
                int mid = l + r >> 1;
                if(dp_up[mid] >= v[i]) r = mid;
                else l = mid;
            }
            dp_up[r] = v[i];
        }
    }

    dp_down.emplace_back(v[0]);
    for(int i = 0; i < n; i++){
        if(v[i] < *min_element(dp_down.begin(), dp_down.end())){
            dp_down.emplace_back(v[i]);
        }
        else{
            int l = -1, r = dp_down.size();
            while(l + 1 != r){
                int mid = l + r >> 1;
                if(dp_down[mid] <= v[i]) r = mid;
                else l = mid;
            }
            dp_down[r] = v[i];
        }
    }
    cout << max(dp_up.size(), dp_down.size()) << '\n';
}

int main(){
    int t; cin >> t;
    while(t--) solve();
    return 0;
}