学步园

【题意】

一共有n个空位，初始全为空，会有两种操作，一种是询问是否有r个连续的空位，若有，则将最左端有r个连续的空位的地方全部填满，若没有则不填，另一种是将从u开始的d个位置全部清空

【输入】

第一行两个数n、m(<=50000)，表示n个空位，m次操作

接下来m行每行表示一次操作，

若该行第一个数字为1，接下来是一个数字，表示操作一

若该行第一个数字为2，接下来是两个数字，表示操作二

【输出】

对于每个操作一，若存在r个连续的空位，则输出最靠左的r个连续空位的起点，若不存在则输出0

线段树

每个节点记录三个值，从该节点左端往右有多少个连续的空位，从该节点右端往左有多少个连续的空位，该区间内最长连续空位长度为多少

program poj3667;
var
  tot,n,m,i,j,k,r,o,s,e:longint;
  left,right,x,y,point:array [0..200001] of longint;

function max (a,b:longint):longint;
begin
  if a>b then exit(a)
         else exit(b);
end;

procedure down (now,l,r:longint);
begin
  if left[now]=0 then
    begin
      inc(tot);
      left[now]:=tot;
    end;
  if right[now]=0 then
    begin
      inc(tot);
      right[now]:=tot;
    end;
  if point[now]=r-l+1 then
    begin
      x[left[now]]:=(l+r) div 2 - l + 1;
      y[left[now]]:=(l+r) div 2 - l + 1;
      point[left[now]]:=(l+r) div 2 - l + 1;
      x[right[now]]:=r-(l+r) div 2;
      y[right[now]]:=r-(l+r) div 2;
      point[right[now]]:=r-(l+r) div 2;
    end;
  if point[now]=0 then
    begin
      x[left[now]]:=0;
      y[left[now]]:=0;
      point[left[now]]:=0;
      x[right[now]]:=0;
      y[right[now]]:=0;
      point[right[now]]:=0;
    end;
end;

procedure fill (s,e,p,l,r,now:longint);
var
  mid:longint;
begin
  if (s=l)and(e=r) then
    begin
      if p=0 then
        begin
          x[now]:=r-l+1;
          y[now]:=r-l+1;
          point[now]:=r-l+1;
        end
             else
        begin
          x[now]:=0;
          y[now]:=0;
          point[now]:=0;
        end;
      exit;
    end;
  mid:=(l+r) div 2;
  down(now,l,r);
  if e<=mid then fill(s,e,p,l,mid,left[now])
            else
  if s>=mid+1 then fill(s,e,p,mid+1,r,right[now])
              else
    begin
      fill(s,mid,p,l,mid,left[now]);
      fill(mid+1,e,p,mid+1,r,right[now]);
    end;
  if x[left[now]]=mid-l+1 then x[now]:=x[left[now]]+x[right[now]]
                          else x[now]:=x[left[now]];
  if y[right[now]]=r-mid then y[now]:=y[right[now]]+y[left[now]]
                         else y[now]:=y[right[now]];
  point[now]:=max(y[left[now]]+x[right[now]],max(point[left[now]],point[right[now]]));
end;

function find (p,l,r,now:longint):longint;
begin
  if (p=point[now])and(r-l+1=point[now]) then exit(l);
  down(now,l,r);
  if point[left[now]]>=p then exit(find(p,l,(l+r) div 2,left[now]))
                         else
  if (y[left[now]]<>0)and(y[left[now]]+x[right[now]]>=p) then exit((l+r) div 2 + 1 - y[left[now]])
                                                         else exit(find(p,(l+r) div 2 + 1,r,right[now]));
end;

begin
  read(n,m);
  tot:=0;
  x[0]:=n;
  y[0]:=n;
  point[0]:=n;
  for i:=1 to m do
    begin
      read(o);
      if o=1 then
        begin
          read(r);
          if point[0]<r then
            writeln(0)

                        else
            begin
              k:=find(r,1,n,0);
              writeln(k);
              fill(k,k+r-1,1,1,n,0);
            end;
        end
             else
        begin
          read(s,e);
          e:=s+e-1;
          fill(s,e,0,1,n,0);
        end;
    end;
end.