LIS离散化 + 树状数组

严格上升子序列正序

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1010;

int n, w[N];
vector<int> nums;
int tr[N];

int get(int val) {
   
    return lower_bound(nums.begin(), nums.end(), val) - nums.begin() + 1;
}

void disc() {
   
    for (int i = 1; i <= n; ++i) nums.push_back(w[i]);
    sort(nums.begin(), nums.end());

    for (int i = 1; i <= n; ++i) w[i] = get(w[i]);
}

int lowbit(int val) {
   
    return val & -val;
}

void update(int u, int val) {
   
    for (int i = u; i < N; i += lowbit(i)) tr[i] = max(tr[i], val);
}

int get_max(int u) {
   
    int res = 0;
    for (int i = u; i; i -= lowbit(i)) res = max(res, tr[i]);
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> w[i];

    disc();

    int res = 1;
    for (int i = 1; i <= n; ++i) {
   
        int curr = get_max(w[i] - 1) + 1;
        res = max(res, curr);
        update(w[i], curr);
    }

    cout << res << "\n";

    return 0;
}

严格上升子序列逆序

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int N = 1010;

int n, w[N];
vector<int> nums;
int tr[N];

int get(int val) {
   
	return lower_bound(nums.begin(), nums.end(), val) - nums.begin() + 1;
}

void disc() {
   
	for (int i = 1; i <= n; ++i) nums.push_back(w[i]);
	sort(nums.begin(), nums.end());

	for (int i = 1; i <= n; ++i) w[i] = get(w[i]);
}

int lowbit(int val) {
   
	return val & -val;
}

void update(int u, int val) {
   
	for (int i = u; i < N; i += lowbit(i)) tr[i] = max(tr[i], val);
}

int get_max(int u) {
   
	int res = 0;
	for (int i = u; i; i -= lowbit(i)) res = max(res, tr[i]);
	return res;
}

int main() {
   
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> w[i];

	disc();

	int res = 1;
	for (int i = n; i >= 1; --i) {
   
		int curr = get_max(n - w[i]) + 1;
		res = max(res, curr);
		update(n - w[i] + 1, curr);
	}

	cout << res << "\n";

	return 0;
}