Hdu5820 Lights

Mean

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

Sol

主席树+扫描线

赛时题意读错了，错得离谱.

直接放官方题解吧，官方题解讲得比较详细。

个人觉得主要方法是把问题的关键点划分到一个小的子问题上，挺妙的。

需要正着扫一遍，再反着扫一遍。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 5e5+10;
struct node{
  int x,y;
}q[N],kep[N];
int kepx[N],kepy[N];
int tot = 0;
#define mid ((l+r)>>1)

struct Node{
  int ls,rs;
  int sum;
}tr[N*60];

int mx;
int root[N];

int build(int l,int r){
  int p = ++tot;
  tr[p].sum = 0;
  if(l==r){
    return p;
  }
  tr[p].ls = build(l,mid);
  tr[p].rs = build(mid+1,r);
  return p;
}

int update(int pos,int loc,int l,int r){
  int p = ++tot;
  tr[p] = tr[pos];
  tr[p].sum ++;
  if(l==r){
    return p;
  }
  if(loc<=mid){
    tr[p].ls = update(tr[pos].ls,loc,l,mid);
  }
  else{
    tr[p].rs = update(tr[pos].rs,loc,mid+1,r);
  }
  return p;
}

int query(int now,int las,int l,int r,int L,int R){
  if(L<=l&&r<=R){
    return tr[now].sum - tr[las].sum;
  }
  int ans = 0;
  if(L<=mid){
    ans = ans + query(tr[now].ls,tr[las].ls,l,mid,L,R);
  }
  if(R>mid){
    ans = ans + query(tr[now].rs,tr[las].rs,mid+1,r,L,R);
  }
  return ans ;
}

bool cmp(node a,node b){
  if(a.x==b.x){
    return a.y<b.y;
  }
  return a.x<b.x;
}
int flag = 0;
#define debug(x) cout<<#x<<" :"<<x<<endl
#define debug1(x) cout<<#x<<" :"<<x<<" "

void work(){
  int las = 0;

  for(int i=1;i<=n;++i){
    int lay = q[kepx[q[i].x]].y;
    int lax = q[kepy[q[i].y]].x;

    root[q[i].x] = update(root[las],q[i].y,0,mx);

    int num = query(root[q[i].x],root[lax],0,mx,lay+1,q[i].y-1);
    
    if(num){
      flag = 0;
      return ;
    }

    kepx[q[i].x]=i;
    kepy[q[i].y]=i;
    las = q[i].x;
  }

}

int main(){
  while(scanf("%d",&n)&&n){
    mx = 0;
    for(int i=1;i<=n;++i){
      scanf("%d%d",&q[i].x,&q[i].y);
      mx = max(mx,q[i].x);
      mx = max(mx,q[i].y);
    }
   
    for(int i=0;i<=tot;++i){
      tr[i].ls=tr[i].rs=tr[i].sum = 0;
    }
    tot = 0;
    for(int i=0;i<=mx;++i){
      root[i] = 0;
      kepx[i]=kepy[i] = 0;
    }

    sort(q+1,q+1+n,cmp);
    int con = 0;
    for(int i=1;i<=n;++i){
      int pos = i;
      while(pos<=n&&q[pos].x==q[i].x&&q[pos].y==q[i].y)pos++;
      kep[++con] = q[i];
      i = pos-1;
    }
    n = con;
    for(int i=1;i<=con;++i){
      q[i]=kep[i];
    } 

    root[0] = build(0,mx);
    flag = 1;
    sort(q+1,q+1+n,cmp);
    work();
    for(int i=1;i<=n;++i){
      q[i].x=mx-q[i].x;
    }
    sort(q+1,q+1+n,cmp);

    for(int i=0;i<=tot;++i){
      tr[i].ls=tr[i].rs=tr[i].sum = 0;
    }
    tot = 0;
    for(int i=0;i<=mx;++i){
      root[i] = 0;
      kepx[i]=kepy[i] = 0;
    }
    work();

    if(flag) puts("YES");
    else puts("NO");
  }
  return 0;
}
/*
2
1 1
3 3
3
1 1
1 3
3 3
0 

*/