python/TangDou/AcWing/LIS/3662.cpp

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

const int N = 1e5 + 10;
typedef long long LL;
#define lowbit(x) (x & -x)

int n, a[N];
int b[N], bl;
LL f[N], tr[N];

void add(int x, LL c) {
    // 放是往上放
    for (; x <= bl; x += lowbit(x)) tr[x] = max(tr[x], c);
}

LL query(int x) {
    // 查是往下查
    LL res = 0;
    for (; x; x -= lowbit(x)) res = max(res, tr[x]);
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        b[i] = a[i];
    }
    // 离散化
    sort(b, b + n);
    bl = unique(b, b + n) - b; // 此处bl的含义是b.size()

    for (int i = 0; i < n; i++) {
        int x = lower_bound(b, b + bl, a[i]) - b + 1;
        f[i] = query(x - 1) + a[i];
        add(x, f[i]);
    }

    // 方法1：
    LL res = 0;
    for (int i = 0; i < n; i++) res = max(res, f[i]);
    printf("%lld\n", res);

    // 方法2：
    // printf("%lld\n", query(bl));
    return 0;
}