这个题据说是Splay，或者说是平衡树的模板题，但是我还是不会做……唉……
\(\color{red}{Description}\)
给定一个序列，初始为空。现在我们将\(1\)到\(N\)的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？
输入格式：
第一行一个整数\(N\)，表示我们要将\(1\)到\(N\)插入序列中。
接下是\(N\)个数字，第\(k\)个数字\(X_k\)，表示我们将\(k\)插入到位置\(X_k\) \((0<=X_k<=k-1,1<=k<=N)\)
输出格式：
\(N\)行，第\(i\)行表示\(i\)插入\(X_i\)位置后序列的最长上升子序列的长度是多少。
$\color{purple}{Half -Solution} $
首先很明显的是，我们的权值就是\(i\)，在插入的时候我们就按照他的实际位置插入，然后找它之前的第一个点，把当前节点变成找到的节点右儿子即可。
那么现在有一个问题，我们在维护完这个序列之后，如何确定它的\(LIS\)呢？听\(rqy\)说，是可以在每次插入的时候在线输出的，但是我觉得完全可以把它处理成一个离线问题，最后复制\(Splay\)的中序遍历，然后再对这个数组\(nlogn\)求一遍\(LIS\)。
但我实在不想写了，现在身心俱疲。
于是我就等着什么时候可以学会在线输出的算法，再把这个题\(A\)掉吧。
他们都在复习中考数学，初中奥数，或者说是预习，因为要考推荐生了。而我现在还在和这个题鏖战……不知道推荐生能不能过……唉……
我选择\(\color{silver}{Waiting}\)
#include<iostream>
#include<cstdio>
#define MAXN 100010
#define il inline
using namespace std;
struct tree{
int maxf,v,sub,son[2],f,pos;
}s[MAXN];
bool w;
int f[MAXN],n,root,wz,fnow,now,ffnow,temp[MAXN],base[MAXN];
il void update(int x){
if(x){
s[x].sub=1;
if(s[x].son[0])s[x].sub+=s[s[x].son[0]].sub;
if(s[x].son[1])s[x].sub+=s[s[x].son[1]].sub;
}
}
il void push_up(int x){
maxf=max(f[x])
}
il bool which(int x){
return x==s[s[x].f].son[1];
}
il void rotate(int x){
fnow=s[x].f,ffnow=s[fnow].f;
w=which(x);
s[fnow].son[w]=s[x].son[w^1];
s[s[x].son[w^1]].f=fnow;
s[x].f=ffnow;
if(ffnow){
s[ffnow].son[fnow==s[ffnow].son[1]]=x;
}
s[x].son[w^1]=fnow;
s[fnow].f=x;
update(fnow);
update(x);
}
il void splay(int x,int goal){
for(int qwq;(qwq=s[x].f)!=goal;rotate(x)){
if(s[qwq].f!=goal){
rotate(which(x)==which(qwq)?qwq:x);
}
}
if(!goal){
root=x;
}
}
il void insert(int pos,int x){
if(!root){
wz++;
s[wz].son[1]=s[wz].son[0]=s[wz].f=0;
s[wz].sub=1;
s[wz].v=x;
return ;
}
if(!pos){
wz++;
s[wz].son[1]=root;
s[wz].f=s[wz].son[0]=0;
s[wz].v=x;
root=wz;
update(wz);
return ;
}
int now=root;
while(1){
if(s[now].son[0]&&x<=s[s[now].son[0]].sub)
now=s[now].son[0];
else {
int temp=(s[now].son[0]?s[s[now].son[0].sub]:0)+1;
if(x<=temp)break;
x-=temp;
now=s[now].son[1];
}
}
wz++;
s[wz].son[1]=s[now].son[1];
s[s[now].son[1]].f=wz;
s[now].son[1]=wz;
s[wz].f=now;
update(wz);
update(now);
pushup(wz);
pushup(now);
splay(wz);
cout<<s[wz].maxf<<endl;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>temp[i];
}
for(int i=1;i<=n;i++)}{
insert(temp[i],i);
}
}