【LG4309】【BZOJ3173】[TJOI2013]最长上升子序列

题面

洛谷

BZOJ

题解

插入操作显然用平衡树就行了

然后因为后面的插入对前面的操作无影响

就直接在插入完的序列上用树状数组求下每个点为终点的最长上升子序就行了

然而懒得手写平衡树了

直接用了\(rope\)

rope用法

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/rope>

using namespace std;

using namespace __gnu_cxx;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();

    if (ch == '-') w = -1 , ch = getchar();

    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

    return w * data;

}

#define MAX_N 100005

rope<int> seq;

int N, ans[MAX_N];

int c[MAX_N];

inline void chkmax(int &x, int y) { if (x < y) x = y; }

inline int lb(int x) { return x & -x; }

void add(int x, int v) { while (x <= N) chkmax(c[x], v), x += lb(x); }

int sum(int x) { int res = 0; while (x > 0) chkmax(res, c[x]), x -= lb(x); return res; }

int main () {

    N = gi();

    for (int i = 1, t; i <= N; i++) t = gi(), seq.insert(t, i);

    for (int i = 0, t; i < N; i++) t = seq[i], add(t, ans[t] = sum(t) + 1);

    for (int i = 1; i <= N; i++) chkmax(ans[i], ans[i - 1]), printf("%d\n", ans[i]);

    return 0;

}