题目传送门(BZOJ)
>原文链接<

题解 :

由于是按顺序插入, 故后面插入的一定不会对前面的答案产生影响,

我们只需要维护每次插入的点的最大值即可.

设一个点i插入到pos,我们只需要找一个x且到x的最长上升子序列长度最长即可, 那么到i的最长长度就是ans[x]+1

考虑用Splay维护这个过程.

我们维护两个值 :mx[p]t[p],第一个代表子树最大值, 第二个代表到节点的最长上升子序列长度.

对于一次插入, 插入ipos, 我们把当前的pos旋到根, 把pos+1旋到根的右儿子, 这时候就可以把i

插到根右儿子的左子树上了,

我们可以用根和根的左子树来更新这个点的答案, 因为它们都在插入点的左侧, 且都比插入的值小.

注意当插入位置是0或者i-1,需要特判.

每次插入的答案是之前的最大答案和这次的t[i]取个\max

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define ls ch[p][0]#define rs ch[p][1]#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)using namespace std;char buf[100000], *p1, *p2; const int N = 110000;inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = ((x+(x<<2))<<1)+(ch^48), ch = nc(); return x;}int ch[N][2], siz[N], t[N], f[N], mx[N];int ans, cnt, root;#define get(x) (ch[f[x]][1] == x)inline void up(int p) { if(!p) return ; siz[p] = siz[ls]+siz[rs]+1; mx[p] = max(t[p], max(mx[ls], mx[rs]));}inline void rotate(int x) { int y = f[x], z = f[y], k = get(x); ch[y][k] = ch[x][!k]; f[ch[y][k]] = y; ch[x][!k] = y; f[y] = x, f[x] = z; if(z) ch[z][ch[z][1]==y] = x; up(y), up(x); if(root == y) root = x;}inline void splay(int x, int y) { for(int fa; (fa = f[x]) != y; rotate(x)) { if(f[fa] != y) rotate(get(x) == get(fa) ? fa : x); }}int find(int x) { int p = root; while(1) { if(x <= siz[ls]) p = ls; else { x -= siz[ls]+1; if(!x) return p; p = rs; } }}int main() { int n = rd(); for(int i = 1; i <= n; i ++ ) { int u = rd(); if(u == 0) { if(!root) root = i, t[i] = 1, siz[i] = 1, up(i); else { int p = find(1); splay(p, 0); ls = i; f[i] = p; t[i] = 1, siz[i] = 1, up(i), up(p); } } else if(u == i-1) { int p = find(i-1); splay(p, 0); rs = i; f[i] = p; t[i] = mx[p]+1, siz[i] = 1; up(i), up(p); } else { int x, p; x = find(u), p = find(u+1); splay(x, 0), splay(p, x); t[i] = max(mx[ch[x][0]], t[x])+1; siz[i] = 1; f[i] = p; ls = i; up(i), up(p), up(x); } ans = max(ans, t[i]); printf("%d\n", ans); }}