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

　题解: 考虑按照元素升序加入所以对位置在其后的元素LIS无影响然后从前面位置的最大值转移过来就行 ,,,,平衡树无脑模拟

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define link(x) for(edge *j=h[x];j;j=j->next)
#define inc(i,l,r) for(int i=l;i<=r;i++)
#define dec(i,r,l) for(int i=r;i>=l;i--)
const int MAXN=3e5+10;
const double eps=1e-8;
#define ll long long
using namespace std;
struct edge{int t,v;edge*next;}e[MAXN<<1],*h[MAXN],*o=e;
void add(int x,int y,int vul){o->t=y;o->v=vul;o->next=h[x];h[x]=o++;}
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}

int key[MAXN],maxx[MAXN],pre[MAXN],ch[MAXN][2],sz[MAXN];
int rt,n;

void newnode(int x,int t){
    key[x]=maxx[x]=t;pre[x]=ch[x][0]=ch[x][1]=0;sz[x]=1;
}

void up(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    maxx[x]=max(key[x],max(maxx[ch[x][0]],maxx[ch[x][1]]));
}

void rotate(int x,int kind){
    int y=pre[x];
    ch[y][!kind]=ch[x][kind];pre[ch[x][kind]]=y;
    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;
    up(y);
}

void splay(int x,int goal){
    while(pre[x]!=goal){
    if(pre[pre[x]]==goal)rotate(x,ch[pre[x]][0]==x);
    else{
        int y=pre[x];int kind=ch[pre[y]][0]==y;
        if(ch[y][kind]==x)rotate(x,!kind),rotate(x,kind);
        else rotate(y,kind),rotate(x,kind);
    }
    }
    if(goal==0)rt=x;
    up(x);
}

int find1(int x,int k){
    if(k==sz[ch[x][0]]+1)return x;
    else if(k<=sz[ch[x][0]])return find1(ch[x][0],k);
    else return find1(ch[x][1],k-sz[ch[x][0]]-1);
}

void inte(){
    newnode(n+1,0);newnode(n+2,0);
    rt=n+1;ch[rt][1]=n+2;pre[n+2]=rt;up(rt);
}

int query(int id,int x){
    //cout<<find1(rt,x)<<endl;
    splay(find1(rt,x),0);splay(find1(rt,x+1),rt);
    int t=max(maxx[ch[rt][0]],key[rt]);t=max(t+1,1);
    newnode(id,t);pre[id]=ch[rt][1];ch[ch[rt][1]][0]=id;
    up(ch[rt][1]);up(rt);
    return maxx[rt];
}

int main(){
    n=read();
    inte();
    inc(i,1,n){
    int t=read();
    printf("%d
",query(i,t+1));
    }
    return 0;
}

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

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2770 Solved: 1398
[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