level 1
题目描述
维护一个序列,使它可以进行下面两种操作:
1.在末尾添加一个数字x
2.将整个序列变成第x次操作后的样子
在每次操作后,输出当前序列的最长上升子序列的长度
序列初始时为空
输入
第一行有一个正整数n,表示操作个数。接下来n行每行有两个整数op,x。如果op为0,则表示添加x这个数字;如果op为1,则表示回到第x次操作之后。
输出
对于每次操作,输出一个答案,表示当前最长上升子序列的长度
样例输入
5
0 2
0 0
1 0
1 0
0 5
样例输出
1
1
0
0
1
2015年08月16日 07点08分
1
level 1
【样例说明】
第一次操作后,序列为 2
第二次操作后,序列为2 0
第三次操作后,序列为(空)
第四次操作后,序列为(空)
第五次操作后,序列为 5
【数据规模和约定】
20%的数据没有第二个的操作
30%的数据n<=1000
100%的数据n<=500,000,且所有输入的数字都是长整型范围内的非负整数
2015年08月16日 07点08分
2
level 1
var
n,op,x,i:longint;
a,b,c:array[1..500000]of longint;
begin
readln(n);
readln(op,x);
if op=0 then begin a[1]:=1; b[1]:=1; c[1]:=x; end;
for i:=2 to n do
begin
readln(op,x);
if (op=0) and (x>=c[i-1]) then begin a[i]:=a[i-1]; b[i]:=b[i-1]+1; c[i]:=x; end;
if (op=0) and (x<c[i-1]) then begin a[i]:=a[i-1]; b[i]:=1; c[i]:=x; end;
if (op=1) and (x=0) then begin a[i]:=0; b[i]:=0; c[i]:=0; end;
if (op=1) and (x>0) then begin a[i]:=a[x]; b[i]:=b[x]; c[i]:=c[x]; end;
if a[i]<b[i] then a[i]:=b[i];
end;
for i:=1 to n do writeln(a[i]);
end.
2015年08月16日 07点08分
4