python/TangDou/AcWing/LIS/896_FenWickTree_0.cpp

#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x & -x)
const int N = 1e5 + 10;

int n, a[N];
int b[N], bl; //离散化数组，用于辅助树状数组
int c[N];     //树状数组
int res;      //结果

//计算x值在原序列中的排名
int get(int x) {
    return lower_bound(b, b + bl, x) - b + 1;
}

//单点更新x
void update(int i, int x) {
    for (; i <= bl; i += lowbit(i)) c[i] = max(c[i], x);
}

//求1~i的最大值
int query(int i) {
    int s = 0;
    for (; i; i -= lowbit(i)) s = max(s, c[i]);
    return s;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]), b[i] = a[i];

    //离散化，用于获取 x值->排名k 的关系
    sort(b, b + n);
    // bl：去重后的长度
    bl = unique(b, b + n) - b;
    /*
    测试用例：
    7
    3 1 2 1 8 5 6
    */
    for (int i = 0; i < n; i++) {
        puts("==============================================");
        printf("i:%d a[i]=%d\n", i, a[i]);
        int k = get(a[i]); // a[i]的排名k
        printf("rank:%d rank-1:%d\n", k, k - 1);
        int t = query(k - 1) + 1;
        printf("LIS[rank-1]:%d ", t - 1);
        printf("LIS[rank]:%d\n", t);
        res = max(res, t);
        update(k, t); //第k大的数，会接在第k-1大的数后面，才会获取到更大的连续LIS值
        puts("FenWickTree:");
        for (int i = 1; i <= bl; i++) printf("%d ", c[i]);
        puts("");
    }
    return 0;
}