首页 > 试题广场 >

对于一个1到𝑛的排列𝑃（即1到𝑛中每一个数在𝑃中出现

[填空题]

对于一个1到𝑛的排列𝑃（即1到𝑛中每一个数在𝑃中出现了恰好一次），令𝑞𝑖为
第𝑖个位置之后第一个比𝑃𝑖值更大的位置，如果不存在这样的位置，则𝑞𝑖 = 𝑛 +1。
举例来说，如果𝑛 = 5且𝑃为1 5 4 2 3，则𝑞为2 6 6 5 6。

下列程序读入了排列𝑃，使用双向链表求解了答案。试补全程序。（第二空2 分，其余3 分）

数据范围 1 ≤ 𝑛 ≤ 10⁵。

var
  n, i, x : longint;
  L, R, a : array[0..100010] of longint;
begin
  read(n);
  for i := 1 to n do
  begin
    read(x);
    1;
  end;
  for i := 1 to n do
  begin
    R[i] := 2;
    L[i] := i - 1;
  end;
  for i := 1 to n do
  begin
    L[3] := L[a[i]];
    R[L[a[i]]] := R[4];
  end;
  for i := 1 to n do
  begin
    write(5);
    write(' ');
  end;
  writeln;
end.

查看正确选项