传送门

Description

给定一个序列，初始为空。现在我们将1到N的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

Input

第一行一个整数N，表示我们要将1到N插入序列中，接下是N个数字，第k个数字Xk，表示我们将k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

Output

N行，第i行表示i插入Xi位置后序列的最长上升子序列的长度是多少。

Sample Input

3

0 0 2

Sample Output

1

1

2

HINT

100%的数据 n<=100000

因为每一次加进来的都是最大的值，所以是不会更新其他的答案的，所以我们可以先把序列搞出来，离线乱搞搞就好了，没事就试了一下zkw线段树，发现还挺快的，不过还是要比树状数组慢不少。

/**************************************************************

    Problem: 3173

    User: geng4512

    Language: C++

    Result: Accepted

    Time:644 ms

    Memory:4712 kb

****************************************************************/

#include<cstdio>

#define MAXN 100005

struct node { int c[2], sz, rnd; } t[MAXN];

unsigned sd = 2333;

int Sz, a[MAXN], cnt, n, rt, mx[MAXN<<2], M, ans[MAXN];

inline int Max(int a, int b) { return a > b ? a : b; }

inline void GET(int &n) {

    n = 0; char c;

    do c = getchar(); while('0' > c || c > '9');

    do n = n * 10 + c - '0', c = getchar(); while('0' <= c && c <= '9');

}

inline unsigned Ran() { return sd = sd * sd + 12580; }

inline void Upd(int k) { t[k].sz = t[t[k].c[0]].sz + t[t[k].c[1]].sz + 1; }

inline void Rot(int &k, bool f) {

    int tmp = t[k].c[f]; t[k].c[f] = t[tmp].c[!f]; t[tmp].c[!f] = k;

    Upd(k); Upd(tmp); k = tmp;

}

void Insert(int &k, int sz) {

    if(!k) { k = ++ Sz; t[k].sz = 1; t[k].rnd = Ran(); return; }

    ++ t[k].sz;

    bool f = t[t[k].c[0]].sz < sz;

    Insert(t[k].c[f], sz - (t[t[k].c[0]].sz+1)*f);

    if(t[k].rnd > t[t[k].c[f]].rnd) Rot(k, f);

}

void dfs(int u) {

    if(!u) return;

    dfs(t[u].c[0]);

    a[++ cnt] = u;

    dfs(t[u].c[1]);

}

namespace Seg {

    void Insert(int x, int v) {

        for(mx[x += M] = v, x >>= 1; x; x >>= 1)

            mx[x] = Max(mx[x<<1], mx[x<<1|1]);

    }

    int Query(int r) {

        int ans = 0;

        for(r += M + 1; r ^ 1; r >>= 1)

            if(r & 1) ans = Max(ans, mx[r^1]);

        return ans;

    }

}

int main() {

    GET(n); int t;

    for(int i = 1; i <= n; ++ i) {

        GET(t);

        Insert(rt, t);

    }

    dfs(rt);

    for(M = 1; M < n + 2; M <<= 1);

    for(int i = 1, tmp; i <= n; ++ i) {

        tmp = Seg::Query(a[i]) + 1;

        Seg::Insert(a[i], tmp);

        ans[a[i]] = tmp;

    }

    for(int i = 1; i <= n; ++ i) {

        ans[i] = Max(ans[i], ans[i-1]);

        printf("%d\n", ans[i]);

    }

    return 0;

}