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

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

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

1   if x<=size[l[t]] then
2     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	lbz007	3173	Accepted	4132 kb	1080 ms	Pascal/Edit	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   begin
10   inc(nn);a[nn]:=x;size[nn]:=1;exit(nn);
11   end;
12 procedure insert(x:longint; var t:longint);
13   begin
14   if t=0 then
15     begin
16     t:=new(x);
17     exit;
18     end;
19   if x<=size[l[t]] then
20     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   begin
26   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   begin
36   while x<=n do
37     begin
38     c[x]:=max(c[x],a);
39     inc(x,lowbit(x));
40     end;
41   end;
42 function search(x:longint):longint;
43   begin
44   search:=0;
45   while x>0 do
46     begin
47     search:=max(search,c[x]);
48     dec(x,lowbit(x));
49     end;
50   end;
51 begin
52   readln(n);
53   for i:=1 to n do
54     begin
55     read(x[i]);
56     insert(x[i],root);
57     end;
58   k:=0;print(root);
59   for i:=1 to n do
60     se[b[i]]:=i;
61   for i:=1 to n do
62     begin
63     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.

View Code