先求出最终的序列，然后树状数组求出每一个询问的答案。

1.求最终序列可以用sbt。插入到位置x时如果比左子树的size大就插入到右子树中，否则就插入到左子树中。

1   if x<=size[l[t]] then2     insert(x,l[t])3   else insert(x-size[l[t]]-1,r[t]);

2.求每一个询问的答案。

  f[i]为当前到这个数的最长上升子序列。查询这个数的最终位置之前的最大的f[j]为max，f[i]=max+1;

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

for i:=1 to n do  begin  f[i]:=1+search(se[i]);  change(se[i],f[i]);  ans[i]:=max(ans[i-1],f[i]);  end;

这个题sbt写maintain比bst慢。。。。。

RunID	User	Problem	Result	Memory	Time	Language	Code_Length	Submit_Time
412076			Accepted	4132 kb	1080 ms	/	1452 B	2013-05-14 15:27:29

1 var 2   ans,se,f,b,c,x,l,r,size,a:array[1..100000]of longint; 3   k,nn,root,n,i,j:longint; 4 function max(aa,bb:longint):longint; 5   begin 6   if aa>bb then exit(aa) else exit(bb); 7   end; 8 function new(x:longint):longint; 9   begin10   inc(nn);a[nn]:=x;size[nn]:=1;exit(nn);11   end;12 procedure insert(x:longint; var t:longint);13   begin14   if t=0 then15     begin16     t:=new(x);17     exit;18     end;19   if x<=size[l[t]] then20     insert(x,l[t])21   else insert(x-size[l[t]]-1,r[t]);22   inc(size[t]);23   end;24 procedure print(t:longint);25   begin26   if t=0 then exit;27   print(l[t]);28   inc(k);b[k]:=t;29   print(r[t]);30   end;31 function lowbit(x:longint):longint;32   begin exit(x and (-x));33   end;34 procedure change(x,a:longint);35   begin36   while x<=n do37     begin38     c[x]:=max(c[x],a);39     inc(x,lowbit(x));40     end;41   end;42 function search(x:longint):longint;43   begin44   search:=0;45   while x>0 do46     begin47     search:=max(search,c[x]);48     dec(x,lowbit(x));49     end;50   end;51 begin52   readln(n);53   for i:=1 to n do54     begin55     read(x[i]);56     insert(x[i],root);57     end;58   k:=0;print(root);59   for i:=1 to n do60     se[b[i]]:=i;61   for i:=1 to n do62     begin63     f[i]:=1+search(se[i]);64     change(se[i],f[i]);65     ans[i]:=max(ans[i-1],f[i]);66     end;67   for i:=1 to n do writeln(ans[i]);68   end.