5049. 【GDOI2017模拟一试4.11】腐女的生日

Description

腐女要过生日了，pty 想给腐女送礼物，但是腐女所在的教室离pty 的教室太远了，于是pty就拜托会动归和A星的djy帮忙送礼物。djy在学校建立了一个平面直角坐标系，他站在了（0，0）点，腐女在（x0,y0）点，djy每次只能往上下左右四个方向移动一步，中间有n栋矩形教学楼，每个教学楼给出两个对角的坐标，并且保证每栋教学楼的周围区域（如图所示）不会有别的教学楼，即djy可以绕一个教学楼走不会碰到任何障碍，现在djy 想知道从起点到终点不碰到任何教学楼，最短需要多少步。

Input

第一行给出X0,y0；
第二行给出n；
下面一行每行x1,y1,x2,y2，表示一对对角的坐标；
保证每个矩形都不相交，且一个矩形的周围区域不会有别的矩形。

Output

输出只有一行：最短的步数

Solutions

一看题目，就可以马上线段树Bfs啊，然后就GG了。进入正题：

因为教学楼都在Y轴的右边，→_→，所以djy不会向左走，只会往右走；

然后用一颗线段树记录每一个高度的上下走最小走多少步，最后结果加上x0就就好了。

代码

  1 const
  2   maxn=1000001;
  3 type
  4   arr=record
  5     x,y,xx,yy:longint;
  6   end;
  7   arrr=record
  8     l,r:longint;
  9   end;
 10 var
 11   x0,y0,n,ans:longint;
 12   a:array [0..200001] of arr;
 13   tree:array [0..8000001] of arrr;
 14 procedure qsort(l,r:longint);
 15 var
 16   i,j,mid:longint;
 17   t:arr;
 18 begin
 19   if l>r then exit;
 20   i:=l; j:=r;
 21   mid:=a[(l+r) div 2].x;
 22   repeat
 23     while a[i].x<mid do inc(i);
 24     while a[j].x>mid do dec(j);
 25     if i<=j then
 26       begin
 27         t:=a[i]; a[i]:=a[j]; a[j]:=t;
 28         inc(i); dec(j);
 29       end;
 30   until i>j;
 31   qsort(i,r);
 32   qsort(l,j);
 33 end;
 34 
 35 procedure init;
 36 var
 37   i:longint;
 38 begin
 39   readln(x0,y0);
 40   y0:=y0+maxn;
 41   readln(n);
 42   for i:=1 to n do
 43     begin
 44       readln(a[i].x,a[i].y,a[i].xx,a[i].yy);
 45       inc(a[i].y,maxn); inc(a[i].yy,maxn);
 46     end;
 47   qsort(1,n);
 48 end;
 49 
 50 procedure down(p:longint);
 51 var
 52   t,k:longint;
 53 begin
 54   if (tree[p].l=0) and (tree[p].r=0) then exit;
 55   if tree[p].r-tree[p].l>0 then begin t:=1; k:=0; end
 56                            else begin t:=-1; k:=1; end;
 57   tree[p*2].l:=tree[p].l;
 58   tree[p*2].r:=(tree[p].l+tree[p].r+k) div 2;
 59   tree[p*2+1].l:=(tree[p].l+tree[p].r+k) div 2+t;
 60   tree[p*2+1].r:=tree[p].r;
 61   tree[p].l:=0; tree[p].r:=0;
 62 
 63 end;
 64 
 65 procedure change(p,l,r,x,y,z,w:longint);
 66 var
 67   mid,k:longint;
 68 begin
 69   if x>y then exit;
 70   if (l=x) and (r=y) then
 71     begin
 72       tree[p].l:=z; tree[p].r:=w;
 73       exit;
 74     end;
 75   down(p);
 76   mid:=(l+r) div 2;
 77   if y<=mid then change(p*2,l,mid,x,y,z,w) else
 78     if x>mid then change(p*2+1,mid+1,r,x,y,z,w) else
 79       begin
 80         if z<w then k:=1
 81                else k:=-1;
 82         change(p*2,l,mid,x,mid,z,z+k*(mid-x));
 83         change(p*2+1,mid+1,r,mid+1,y,z+k*(mid-x+1),w);
 84       end;
 85 end;
 86 
 87 function find(p,l,r,y:longint):longint;
 88 var
 89   mid:longint;
 90 begin
 91   if l=r then exit(tree[p].l);
 92   down(p);
 93   mid:=(l+r) div 2;
 94   if  y<=mid then exit(find(p*2,l,mid,y))
 95              else exit(find(p*2+1,mid+1,r,y));
 96 end;
 97 
 98 procedure main;
 99 var
100   i,x,y,mid:longint;
101 begin
102   change(1,0,maxn*2,maxn+1,maxn*2,1,maxn);
103   change(1,0,maxn*2,0,maxn,maxn,0);
104   for i:=1 to n do
105     begin
106       if a[i].x>x0 then break;
107       x:=find(1,0,maxn*2,a[i].y-1);
108       y:=find(1,0,maxn*2,a[i].yy+1);
109       mid:=(a[i].y+a[i].yy-x+y) div 2;
110       change(1,0,maxn*2,a[i].y-1,mid,x,x+mid-a[i].y+1);
111       if mid<a[i].yy then
112         change(1,0,maxn*2,mid+1,a[i].yy+1,y+a[i].yy-mid,y);
113     end;
114   ans:=find(1,0,maxn*2,y0)+x0;
115   writeln(ans);
116 end;
117 
118 begin
119   init;
120   main;
121 end.