Description

给定一个序列, 初始为空. 现在我们将 \(1\) 到 \(n\) 的数字插入到序列中, 每次将一个数字插入到一个特定的位置. 每插入一个数字, 我们都想知道此时最长上升子序列长度是多少?

Input

第一行一个整数 \(n\), 表示我们要将 \(n\) 到 \(n\) 插入序列中, 接下是 \(n\) 个数字, 第 \(k\) 个数字 \(X_k\), 表示我们将 \(k\) 插入到位置 \(X_k\), 满足 \((0 \leq X_k \leq k-1, 1 \leq k \leq n)\)

Output

\(n\) 行, 第 \(i\) 行表示 \(i\) 插入 \(X_i\) 位置后序列的最长上升子序列的长度是多少.

Sample Input

3
0 0 2

Sample Output

1
1
2

Data Range

对于 100% 的数据, 满足 \(n \leq 100000\)

Explanation

想不通为什么要用 Treap......

不是应该用 Splay 更方便吗?

但是 Treap 更好写啊~ 所以就当写一遍模板了......

我们发现后加入的元素一定不会使结果更糟, 所以就直接维护 (伪) 平衡树就可以了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 100100;
const int infinit = 1000000000;

class Treap
{
public:
    int n, ncnt, dcnt, root, hash[maxn];
    int size[maxn], lc[maxn], rc[maxn], val[maxn];
    void update(int x) {
        size[x] = size[lc[x]] + size[rc[x]] + 1;
        return ; }
    void lrotate(int &x) {
        int y = rc[x]; rc[x] = lc[y]; lc[y] = x;
        update(x); update(y); x = y;
        return; }
    void rrotate(int &x) {
        int y = lc[x]; lc[x] = rc[y]; rc[y] = x;
        update(x); update(y); x = y;
        return ; }
    void insert(int &x, int rank)
    {
        if (!x) {
            x = ++ncnt; size[x] = 1;
            hash[x] = rand();
            return ;
        }
        size[x] += 1;
        if (size[lc[x]] < rank) {
            insert(rc[x], rank - size[lc[x]] - 1);
            if (hash[rc[x]] < hash[x])
                lrotate(x);
        } else {
            insert(lc[x], rank);
            if (hash[lc[x]] < hash[x])
                rrotate(x);
        }
        return ;
    }
    void insert(int rank) {
        insert(root, rank);
        return ; }
    void dump(int p)
    {
        if (!p) return ;
        dump(lc[p]);
        val[++dcnt] = p;
        dump(rc[p]);
        return ;
    }
    int res[maxn];
    void solve(void)
    {
        static int minn[maxn];
        static int maxx = 0;
        for (int i = 0; i <= n; i++)
            minn[i] = infinit;
        minn[0] = -infinit;
        for (int i = 1; i <= n; i++) {
            int t = upper_bound(minn, minn + maxx + 1, val[i]) - minn; // Magic
            if (minn[t-1] <= val[i]) {
                minn[t] = min(minn[t], val[i]);
                res[val[i]] = t;
                maxx = max(maxx, t);
            }
        }
        return ;
    }
} tr;

int n;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    tr.n = n;
    for (int i = 1, k; i <= n; i++) {
        scanf("%d", &k);
        tr.insert(k);
    }
    tr.dump(tr.root);
    tr.solve();
    for (int i = 1; i <= n; i++) {
        tr.res[i] = max(tr.res[i], tr.res[i-1]);
        printf("%d\n", tr.res[i]);
    }
    return 0;
}