동규 안의 편 서

동 규 이전 은 흔히 일련의 조건 을 만족 시 켜 야 한다. 그 중에서 단조 로 운 편 서 관 계 를 만족 시 킬 수 있 기 때문에 동 귀 이론 이 복잡 도가 시간 을 초과 할 때 우 리 는 이런 편 서 관 계 를 쓰 거나 데이터 구조, 또는 경사 율 등 일련의 방법 으로 이런 편 서 관 계 를 유지 하고 복잡 도 를 낮 출 수 있다.
예제:
길이 가 N 인 정수 서열 A1, A2... AN 을 드 리 겠 습 니 다. 몇 개 를 차 야 합 니 다.
방정식 을 쉽게 생각해 낼 수 있 습 니 다. f [i]: = max {f [j]} + 1 (f [i] 는 a [i] 를 새로운 서열 의 a [i] 항목 으로 최대 몇 개의 숫자 가 조건 을 만족 시 킬 수 있 습 니 다).
편차 관계: 1, i > j
                        2、a[i]>a[j]
                        3、i-j>=a[i]-a[j] ——> i-a[i]>=j-a[j]
3 차원 편 서 처럼 보이 지만 2, 3 이 1 을 내 놓 을 수 있 음 을 알 수 있 기 때문에 우 리 는 2, 3 의 편 서 관 계 를 유지 해 야 한다.
2. 빠 른 배열 로 초기 화 할 수 있 습 니 다. 3. 좌표 축 을 매 핑 할 수 있 습 니 다. 선분 트 리 나 트 리 배열 로 log n 시간 내 에 전 이 를 완성 하고 문제 도 해결 할 수 있 습 니 다.
비록 지금 우 리 는 곧 알고리즘 을 구성 할 수 있 지만 lmd 학우 들 이 시험 을 볼 때 도 편 서 관 계 를 찾 았 지만 3 차원 편 서 라 고 생각 하여 알몸 으로 할 수 밖 에 없다.
따라서 우 리 는 우리 가 무엇 을 유지 하고 무엇 을 요구 하 는 지 명 확 히 해 야 한다. 가장 좋 은 것 은 쓰 고 내부 관 계 를 탐색 하 는 것 이다. 목적 없 이 알고리즘 을 생각해 서 는 안 된다.

var a,b:array[1..100000]of longint;
    f:array[1..262144]of longint;
    n,ans,m1:longint;
procedure qsort(l,r:longint);
var i,j,x,y,c:longint;
begin
 i:=l;j:=r;x:=a[(l+r)>>1];y:=b[(l+r)>>1];
 repeat
  while (a[i]<x)or((a[i]=x)and(b[i]>y)) do inc(i);
  while (x<a[j])or((x=a[j])and(y>b[j])) do dec(j);
  if not(i>j) then begin
   c:=a[i];a[i]:=a[j];a[j]:=c;
   c:=b[i];b[i]:=b[j];b[j]:=c;
   inc(i);dec(j)
  end
 until i>j;
 if i<r then qsort(i,r);
 if l<j then qsort(l,j)
end;
procedure change(x,y:longint);
begin
 x:=x+m1;
 while (x<>0)and(f[x]<y) do begin
  f[x]:=y;
  x:=x>>1
 end
end;
function ask(r:longint):longint;
var l:longint;
begin
 l:=1+m1-1;r:=r+m1+1;ask:=0;
 while not(l xor r=1) do begin
  if l and 1=0 then if f[l+1]>ask then ask:=f[l+1];
  if r and 1=1 then if f[r-1]>ask then ask:=f[r-1];
  l:=l>>1;r:=r>>1
 end
end;
procedure origin;
begin
 m1:=1;
 while m1<n+2 do m1:=m1<<1;m1:=m1-1
end;
procedure init;
var i,max:longint;
begin
 readln(n);
 for i:=1 to n do begin read(a[i]);b[i]:=i end;
 qsort(1,n);
 origin;
 ans:=0;
 for i:=1 to n do
 if b[i]>=a[i] then begin
  max:=ask(b[i]-a[i]+1)+1;
  change(b[i]-a[i]+1,max);
  if max>ans then ans:=max
 end;
 writeln(ans)
end;
begin
assign(input,'easyIV.in');reset(input);
assign(output,'easyIV.out');rewrite(output);
 init;
close(input);close(output)
end.