BZOJ3173 TJOI2013最長上升子序列(Treap+ZKW線段樹)

傳送門

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[], sz, rnd; } t[MAXN];
unsigned sd = ;
int Sz, a[MAXN], cnt, n, rt, mx[MAXN<<], M, ans[MAXN];
inline int Max(int a, int b) { return a > b ? a : b; }
inline void GET(int &n) {
    n = ; char c;
    do c = getchar(); while('0' > c || c > '9');
    do n = n *  + c - '0', c = getchar(); while('0' <= c && c <= '9');
}
inline unsigned Ran() { return sd = sd * sd + ; }
inline void Upd(int k) { t[k].sz = t[t[k].c[]].sz + t[t[k].c[]].sz + ; }
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 = ; t[k].rnd = Ran(); return; }
    ++ t[k].sz;
    bool f = t[t[k].c[]].sz < sz;
    Insert(t[k].c[f], sz - (t[t[k].c[]].sz+)*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[]);
    a[++ cnt] = u;
    dfs(t[u].c[]);
}
namespace Seg {
    void Insert(int x, int v) {
        for(mx[x += M] = v, x >>= ; x; x >>= )
            mx[x] = Max(mx[x<<], mx[x<<|]);
    }
    int Query(int r) {
        int ans = ; 
        for(r += M + ; r ^ ; r >>= )
            if(r & ) ans = Max(ans, mx[r^]);
        return ans;
    }
}
int main() {
    GET(n); int t;
    for(int i = ; i <= n; ++ i) {
        GET(t);
        Insert(rt, t);
    }
    dfs(rt);
    for(M = ; M < n + ; M <<= );
    for(int i = , tmp; i <= n; ++ i) {
        tmp = Seg::Query(a[i]) + ;
        Seg::Insert(a[i], tmp);
        ans[a[i]] = tmp;
    }
    for(int i = ; i <= n; ++ i) {
        ans[i] = Max(ans[i], ans[i-]);
        printf("%d\n", ans[i]);
    }
    return ;
}