hdu 5820 Lights(扫描线+主席树)

时间:2023-01-28 00:18:35

题目链接:hdu 5820 Lights

题意:

给定一个网格图,上面有 N个灯 
求任意两个灯之间,是否至少存在一条曼哈顿最短路径 
使得路径上的每一个拐点都有一个灯。

题解:

我们可以对每个点将非法的区域找出来,然后看看这个区域内有没有点,然后就有如下的做法:

hdu 5820 Lights(扫描线+主席树)

这里要从左往右和从右往左都扫一遍,这样就覆盖了全部的情况了。

hdu 5820 Lights(扫描线+主席树)hdu 5820 Lights(扫描线+主席树)
 1 #include<bits/stdc++.h>
 2 #define mst(a,b) memset(a,b,sizeof(a))
 3 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 4 using namespace std;
 5 
 6 const int N=5e5+7,M=5e4+7;
 7 struct node{
 8     int x,y;
 9     bool operator<(const node& b)const{return x!=b.x?x<b.x:y<b.y;}
10 }a[N];
11 struct tr{int l,r,sum;}T[N*30];
12 int n,cnt,root[M],flag,mx[M],my[M];
13 
14 void update(int pos,int v,int &x,int y,int l=1,int r=M)
15 {
16     T[x=++cnt]=T[y],T[x].sum++;
17     if(l==r)return;
18     int mid=l+r>>1;
19     if(pos<=mid)update(pos,v,T[x].l,T[y].l,l,mid);
20     else update(pos,v,T[x].r,T[y].r,mid+1,r);
21 }
22 
23 int query(int L,int R,int x,int y,int l=1,int r=M)
24 {
25     if(L<=l&&r<=R)return T[x].sum-T[y].sum;
26     int mid=l+r>>1,an=0;
27     if(L<=mid)an+=query(L,R,T[x].l,T[y].l,l,mid);
28     if(R>mid)an+=query(L,R,T[x].r,T[y].r,mid+1,r);
29     return an;
30 }
31 
32 void work()
33 {
34     mst(mx,0),mst(my,0),cnt=0;
35     mst(root,0);
36     int last=0;
37     F(i,1,n)
38     {
39         int x2=a[my[a[i].y]].x,y2=a[mx[a[i].x]].y;
40         update(a[i].y,1,root[a[i].x],last);
41         int ans=query(y2+1,a[i].y,root[a[i].x],root[x2]);
42         if(ans>1){flag=0;return;}
43         mx[a[i].x]=i,my[a[i].y]=i,last=root[a[i].x];
44     }
45 }
46 
47 int main(){
48     while(~scanf("%d",&n),n)
49     {
50         F(i,1,n)scanf("%d%d",&a[i].x,&a[i].y);
51         sort(a+1,a+1+n);
52         int ed=1;
53         F(i,2,n)if(a[i].x!=a[ed].x||a[i].y!=a[ed].y)a[++ed]=a[i];
54         n=ed,flag=1,work();
55         if(flag)
56         {
57             F(i,1,n)a[i].x=M-a[i].x;
58             sort(a+1,a+1+n),work();
59         }
60         puts(flag?"YES":"NO");
61     }
62     return 0;
63 }
View Code