标签：扫描线，线段树
题目
题目描述
腐女要过生日了，pty 想给腐女送礼物，但是腐女所在的教室离 pty 的教室太远了，于是 pty 就拜托会动归和 A 星的 djy 帮忙送礼物。djy 在学校建立了一个平面直角坐标系，他 站在了（0，0）点，腐女在（x0,y0）点，djy 每次只能往上下左右四个方向移动一步，中 间有 n 栋矩形教学楼，每个教学楼给出两个对角的坐标，并且保证每栋教学楼的周围区域 （如图所示） 不会有别的教学楼，即 djy 可以绕一个教学楼走不会碰到任何障碍，现在 djy 想知道从起点 到终点不碰到任何教学楼，最短需要多少步。
输入
第一行给出 X0,y0； 第二行给出 n； 下面一行每行 x1,y1,x2,y2，表示一对对角的坐标； 保证每个矩形都不相交，且一个矩形的周围区域不会有别的矩形
输出
输出只有一行：最短的步数
样例输入
9 1
2
5 -3 8 3
10 -3 13 3
样例输出
16
提示
保证所有的 y 坐标在[-10^6,10^6] 所有的 x 坐标在[0,10^6] 70%的数据保证：n<=1000 100%的数据保证：n<=10^5
分析
一眼就发现是扫描线，可是不会写qwq，然后敲了个SPFA，鬼畜地建边，然后WA掉
据说直接输出曼哈顿距离40pts!!!
JSOI复现！
mmp写了那么长时间的最短路，还不如直接输出QwQ
以后遇到有关曼哈顿的题目，写暴力还不如直接输出曼哈顿距离
正解：用扫描线+线段树保存当前x位置的情况下到每点的最短路
显然除了第一个矩形以外只能从左往右走
每次遇到一个矩形的左边就把对应的区间[l,r]的值清空，插入那条边
插入的时候对应y的取值范围内不能走
遇到一个矩形的右边就把对应区间[l,r]用l-1和r+1的值去更新（矩形边上的点只能由矩形两角向中间走）
两个点往中心更新答案是每移一格加1，就相当于两个一次函数，斜率为正负1，可以求出交点，知道哪一段的答案是由l-1更新更优，哪一段的答案是由r+1更新更优
code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
//**********head by yjjr**********
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
const int maxn=1e5+6,maxm=2e6+6,mx=1e6;//mx防止负数
int sx[maxm<<2],gc[maxm<<2],sum[maxm<<2],n,m,top,x,X,Y,ans;//sx数组记录距离，gc数组记录扫描的状态
bool pd[maxm<<2];//表示当前位置是否处于扫描的状态
struct node{int x,ca,y1,y2;}ask[maxn<<1];
inline bool cmpa(node a,node b){return a.x==b.x?a.ca>b.ca:a.x<b.x;}
void markad(int x,int v,int d){
if(pd[x])return;
sx[x]+=v;
gc[x]+=d;
}
void markcl(int x){sum[x]=1;sx[x]=gc[x]=0;}
void pushdown(int x,int l,int r){
if(sum[x]){markcl(lson);markcl(rson);sum[x]=0;}
if(sx[x]||gc[x]){
markad(lson,sx[x],gc[x]);
markad(rson,sx[x]+(mid-l+1)*gc[x],gc[x]);
sx[x]=gc[x]=0;
}
}
void modify(int x,int l,int r,int ql,int qr,int v,int d){
if(pd[x]||ql>qr)return;
if(l==ql&&r==qr){markad(x,v,d);return;}
pushdown(x,l,r);
if(qr<=mid)modify(lson,l,mid,ql,qr,v,d);
else if(ql>mid)modify(rson,mid+1,r,ql,qr,v,d);
else{modify(lson,l,mid,ql,mid,v,d);modify(rson,mid+1,r,mid+1,qr,v+d*(mid-ql+1),d);}
}
void clear(int x,int l,int r,int ql,int qr,int v){
if(l==ql&&r==qr){pd[x]=v;if(v)markcl(x);return;}
pushdown(x,l,r);
if(qr<=mid)clear(lson,l,mid,ql,qr,v);
else if(ql>mid)clear(rson,mid+1,r,ql,qr,v);
else{clear(lson,l,mid,ql,mid,v);clear(rson,mid+1,r,mid+1,qr,v);}
}
inline int query(int x,int l,int r,int q){
if(l==r)return sx[x];
pushdown(x,l,r);
if(q<=mid)return query(lson,l,mid,q);else return query(rson,mid+1,r,q);
}
int main(){
X=read(),Y=read();
ask[top=1].x=X;ask[1].y1=Y;
n=read();
rep(i,1,n){
int x1=read(),y1=read(),x2=read(),y2=read();
if(x1>x2)swap(x1,x2),swap(y1,y2);if(y1>y2)swap(y1,y2);//交换顺序，保证x1<x2,y1<y2
ask[++top]=(node){x1,1,y1,y2};
ask[++top]=(node){x2+1,2,y1,y2};//ca为标记值，1表示开始，2表示结束
}
sort(ask+1,ask+1+top,cmpa);//将每个矩形按第一要素为x坐标，第二要素为ca标记值排序
x=0;//扫描线从左往右
modify(1,1,maxm,mx+1,maxm,1,1);
modify(1,1,maxm,1,mx-1,mx-1,-1);
rep(i,1,top){
modify(1,1,maxm,1,maxm,ask[i].x-x,0);
x=ask[i].x;
if(ask[i].ca==0){ans=query(1,1,maxm,ask[i].y1+mx);break;}//找到答案退出
else if(ask[i].ca==1)clear(1,1,maxm,ask[i].y1+mx,ask[i].y2+mx,1);//开始扫描一个矩形
else if(ask[i].ca==2){//扫到矩形的出边
clear(1,1,maxm,ask[i].y1+mx,ask[i].y2+mx,0);//将这个矩形扫过的权值清空
int j=query(1,1,maxm,ask[i].y1-1+mx),k=query(1,1,maxm,ask[i].y2+1+mx);//查找到上下边界的最短距离
int l=ask[i].y2-ask[i].y1+1,t=(k+l+1-j)/2;
if(t<1)modify(1,1,maxm,ask[i].y1+mx,ask[i].y2+mx,k+l,-1);
else if(t>l)modify(1,1,maxm,ask[i].y1+mx,ask[i].y2+mx,j+1,1);//选择一个最短距离更新
else{
modify(1,1,maxm,ask[i].y1+mx,ask[i].y1+t-1+mx,j+1,1);
modify(1,1,maxm,ask[i].y1+t+mx,ask[i].y2+mx,k+l-t,-1);
}
}
}
cout<<ans<<endl;
}
