bzoj2002 彈飛綿羊

分為sqrt(n)左右塊，next[i]記錄從i跳出目前塊的位置，time[i]記錄相應次數,up傳回目前點所在塊最大值，low傳回最小值。提前把low、up存起來似乎更快。。。開始先把next、time處理出來，有修改隻修改所在的塊，詢問一路跳過去就好。注意最後位置的邊界處理，以及編号從0開始。

我又腦殘地多次打錯下标。。。

const maxn=290099;
var
  j,n,m,i,ans,d,l:longint;
  next,time,k,up,low:array[0..maxn]of longint;
 
function min(a,b:longint):longint;inline;begin if a<b then exit(a);exit(b);end;
//function up(i:longint):longint;inline;begin exit(((i-1)div l+1)*l);end;//
//function low(i:longint):longint;inline;begin exit((i-1)div l*l+1);end;
 
procedure init;
  var i,t:longint;
  begin
    next[n]:=n+1;
    time[n]:=1;
    for i:=1 to n-1 do begin next[i]:=i+k[i];time[i]:=1;end;
    for i:=n-1 downto 1 do
      begin
        t:=i;
        while t<=min(up[i],n) do
          begin
            if i<>t then inc(time[i],time[t]);
            t:=next[t];
          end;
        next[i]:=t;
      end;
  end;
 
procedure change(x,d:longint);
  var i,t:longint;
  begin
    k[x]:=d;
    for i:=min(n-1,up[x]) downto low[x] do begin next[i]:=i+k[i];time[i]:=1;end;
    for i:=min(n-1,up[x]) downto low[x] do//x ! i!
      begin
        t:=i;
        while t<=up[i] do//這樣能過oj資料，但自己随便拍一下，n、m大于10就常常卡死。。很顯然，應該是t<=min(up[i],n)
          begin
            if i<>t then inc(time[i],time[t]);
            t:=next[t];
          end;
        next[i]:=t;
      end;
  end;

begin
  //assign(input,'in');reset(input);
  //assign(output,'out');rewrite(output);
  readln(n);
  for i:=1 to n do read(k[i]);
  l:=trunc(sqrt(n));
  for i:=1 to n do begin up[i]:=((i-1)div l+1)*l;low[i]:=(i-1)div l*l+1;end;
  init;
  readln(m);
  while m<>0 do
    begin
      dec(m);
      read(j);
      case j of
        1:  
          begin
            readln(i);
            inc(i);
            ans:=0;
            while i<=n do
              begin
                inc(ans,time[i]);
                i:=next[i];
              end;
            writeln(ans);
          end;
        2:begin readln(i,d);inc(i);change(i,d);end;
      end;
  end;
  close(input);close(output);
end.