BZOJ3173:[TJOI2013]最长上升子序列(Splay)

2023-08-27 15:07:46

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

Solution

设$f[i]$表示以$i$数字为结尾的最长上升子序列长度。

可以发现插入一个数的时候只有当前这个数的$f$会变化，也就是当前这个数前面一段的$max(f)+1$。

用$Splay$维护一下就好了。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (100009)

 using namespace std;

 int n,m,p,ans,Root;

 int Father[N],Son[N][],f[N],Max[N],Size[N];

 inline int read()

 {

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

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

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

     return x*w;

 }

 int Get(int x)

 {

     return Son[Father[x]][]==x;

 }

 void Pushup(int x)

 {

     Max[x]=f[x];

     if (Son[x][]) Max[x]=max(Max[x],Max[Son[x][]]);

     if (Son[x][]) Max[x]=max(Max[x],Max[Son[x][]]);

     Size[x]=Size[Son[x][]]+Size[Son[x][]]+;

 }

 void Rotate(int x)

 {

     int wh=Get(x);

     int fa=Father[x],fafa=Father[fa];

     if (fafa) Son[fafa][Son[fafa][]==fa]=x;

     Father[fa]=x; Son[fa][wh]=Son[x][wh^];

     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;

     Father[x]=fafa; Son[x][wh^]=fa;

     Pushup(fa); Pushup(x);

 }

 void Splay(int x,int tar)

 {

     for (int fa; (fa=Father[x])!=tar; Rotate(x))

         if (Father[fa]!=tar) Rotate(Get(fa)==Get(x)?fa:x);

     if (!tar) Root=x;

 }

 int Next(int now)

 {

     if (!Son[now][]) return now;

     now=Son[now][];

     while (Son[now][]) now=Son[now][];

     return now;

 }

 int Findkth(int x)

 {

     int now=Root;

     while ()

         if (x<=Size[Son[now][]]) now=Son[now][];

         else

         {

             x-=Size[Son[now][]];

             if (x==) {Splay(now,); return now;}

             x--; now=Son[now][];

         }

 }

 int main()

 {

     n=read();

     Max[]=Max[n+]=f[]=f[n+]=-2e9;

     Father[n+]=; Son[][]=n+;

     for (int i=; i<=n+; ++i) Size[i]=;

     Size[]=; Root=;

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

     {

         p=read(); p=Findkth(p+);

         int nxt=Next(Root);

         Splay(,);

         if (nxt!=) Splay(nxt,);

         f[i]=Max[Son[nxt][]]+;

         ans=max(ans,f[i]);

         printf("%d\n",ans);

         Splay(p,);

         if (nxt!=p) Splay(nxt,p);

         Father[i]=nxt; Son[nxt][]=i;

         Max[i]=f[i];

         Splay(i,);

     }

 }

码农公寓