Description

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

Input

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

Output

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

Sample Input

【样例输入1】 9 1 2 5 -3 8 3 10 -3 13 3 【样例输入2】 12 0 5 2 -1 3 1 6 -7 8 -1 6 1 8 6 4 3 4 5 10 -5 10 3

Sample Output

【样例输出1】 16 【样例输出2】 24

Data Constraint

保证所有的y坐标在[-10^6,10^6] 所有的x坐标在[0,10^6] 70%的数据保证：n<=1000 100%的数据保证：n<=10^5

分析

扫描线+线段树 我们把矩阵拆成两部分，左端点插入，右端点删除。插入的时候对应的y不能走，所以要赋成inf，删除的时候要重新计算答案。如果对应的y是[l,r]，那我们只会由l-1,r-1两个位置的答案更新当前区间的答案。l-1对应的答案是tmp1，r+1对应的答案是tmp2，那他们两个点往中心更新答案是每移一格加1，那就是两个一次函数，斜率为正负1，可以很快地求出交点，知道哪一段的答案是由l-1更新更优，哪一段的答案是由r+1更新更优

代码

#include <bits/stdc++.h> #define N 200009 #define M 8000009 #define MAX 100001 #define INF 0x7fffffff struct NOTE { int lazy[2]; }t[M]; struct NODE { int x,l,r,op; }num[N]; void pushDown(int p) { int tmp = (t[p].lazy[0] < t[p].lazy[1]) ? 1 : -1; t[p * 2].lazy[0] = t[p].lazy[0]; t[p * 2].lazy[1] = (t[p].lazy[0] + t[p].lazy[1] + (tmp < 0)) / 2; t[p * 2 + 1].lazy[0] = (t[p].lazy[0] + t[p].lazy[1] + (tmp < 0)) / 2 + tmp; t[p * 2 + 1].lazy[1] = t[p].lazy[1]; t[p].lazy[0] = t[p].lazy[1] = 0; } void insert(int p,int l,int r,int x,int y,int xx,int yy) { if (l == x && r == y) { t[p].lazy[0] = xx; t[p].lazy[1] = yy; return; } int mid = (l + r) >> 1; if ((l != r) && (t[p].lazy[0] || t[p].lazy[1])) pushDown(p); if (y <= mid) insert(p * 2,l,mid,x,y,xx,yy); else if (x > mid) insert(p * 2 + 1,mid + 1,r,x,y,xx,yy); else { insert(p * 2,l,mid,x,mid,xx,((yy > xx) ? 1 : -1) * (mid - x) + xx); insert(p * 2 + 1,mid + 1,r,mid + 1,y,((yy > xx) ? 1 : -1) * (mid - x + 1) + xx,yy); } } int qury(int p,int l,int r,int v) { int mid = (l + r) >> 1; if (l == r) return t[p].lazy[0]; if (t[p].lazy[0] || t[p].lazy[1]) pushDown(p); if (v <= mid) return qury(p * 2,l,mid,v); else return qury(p * 2 + 1,mid + 1,r,v); } bool cmp(NODE x,NODE y) { return (x.x < y.x) || (x.x == y.x) && (x.op > y.op); } int cnt; void add(int x1,int y1,int x2,int y2) { num[++cnt].x = x1; num[cnt].l = y1; num[cnt].r = y2; num[cnt].op = 1; num[+cnt].x = x2; num[cnt].l = y1; num[cnt].r = y2; num[cnt].op = -1; } int main() { freopen("bl.in","r",stdin); freopen("bl.out","w",stdout); int x0,y0; scanf("%d%d",&x0,&y0); int n; scanf("%d",&n); for (int i = 1; i <= n; i++) { int x1,x2,y1,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); add(x1,y1,x2,y2); } std::sort(num + 1, num + cnt + 1, cmp); insert(1,-MAX,MAX,-MAX,0,MAX,0); insert(1,-MAX,MAX,1,MAX,1,MAX); for (int i = 1; i <= cnt; i++) { if (num[i].x > x0) break; if (num[i].op == -1) { int tmp1 = qury(1,-MAX,MAX,num[i].l - 1); int tmp2 = qury(1,-MAX,MAX,num[i].r + 1); int tmp = (num[i].l + num[i].r + tmp2 - tmp1) / 2; insert(1,-MAX,MAX,num[i].l - 1,tmp,tmp1,tmp1 + tmp - num[i].l + 1); if (tmp < num[i].r) { insert(1,-MAX,MAX,tmp + 1,num[i].r + 1,tmp2 + num[i].r - tmp,tmp2); } } } printf("%d\n",qury(1,-MAX,MAX,y0) + x0); }