BZOJ 3173: [Tjoi2013]最长上升子序列 [splay DP]

时间：2024-01-06 19:52:14

3173: [Tjoi2013]最长上升子序列

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1613  Solved: 839
[Submit][Status][Discuss]

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

插入的数字是递增的，也就是说插入数字后不会改变其他元素的dp值

有一个离线做法：用treap动态把序列弄出来然后求lis

http://hzwer.com/6254.html

在线用splay，f表示以当前元素结尾的LIS长度，mx表示他的子树里最大的f

把新插入的元素转到根后，f就是左子树mx+1(不可能有非法的因为递增啊)

注意：

1.别忘哨兵

2.别忘更新size时还要+1

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

#define lc t[x].ch[0]

#define rc t[x].ch[1]

#define pa t[x].fa

const int N=1e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,k;

struct node{

    int ch[],fa,size,v,f,mx;

    node():fa(){ch[]=ch[]=;}

}t[N];

int sz,root;

inline int wh(int x){return t[pa].ch[]==x;}

inline void update(int x){

    t[x].size=t[lc].size+t[rc].size+;

    t[x].mx=max(t[x].f,max(t[lc].mx,t[rc].mx));

}

inline void rotate(int x){

    int f=t[x].fa,g=t[f].fa,c=wh(x);

    if(g) t[g].ch[wh(f)]=x;t[x].fa=g;

    t[f].ch[c]=t[x].ch[c^];t[t[f].ch[c]].fa=f;

    t[x].ch[c^]=f;t[f].fa=x;

    update(f);update(x);

}

inline void splay(int x,int tar){

    for(;t[x].fa!=tar;rotate(x))

        if(t[pa].fa!=tar) rotate(wh(x)==wh(pa)?pa:x);

    if(tar==) root=x;

}

inline int kth(int k){

    int x=root,lsize=;

    while(x){

        int _=lsize+t[lc].size;

        if(_<k&&k<=_+) return x;

        else if(k<=_) x=lc;

        else lsize=_+,x=rc;

    }

    return ;

}

inline int nw(int v){

    sz++;t[sz].v=v;t[sz].size=;

    return sz;

}

inline void Sol(int k,int v){//printf("Sol %d %d\n",k,v);

    int f=kth(k+);splay(f,);//puts("hi");

    int x=kth(k+);splay(x,f);//printf("ran %d %d\n",f,x);

    lc=nw(v);t[lc].fa=x;

    update(x);update(f);

    splay(sz,);

    t[sz].f=t[t[sz].ch[]].mx+;update(sz); //printf("f %d %d %d\n",sz,t[sz].ch[0],t[sz].f);

    printf("%d\n",t[sz].mx);

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();

    root=nw();t[root].ch[]=nw(N);t[sz].fa=root;

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

        k=read();

        Sol(k,i);

    }

}

相关文章