腐女的生日【省选模拟赛】

扫描线+线段树维护+维护一次函数

Posted by yjjr's blog on March 14, 2018

标签:扫描线,线段树

题目

题目描述

腐女要过生日了,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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr