Lights（主席树）

原题： http://acm.hdu.edu.cn/showproblem.php?pid=5820

题意：

有n个点，两个点之间的路径为：长度为曼哈顿距离，每个拐角有一个其他点。求是否所有点之间都有路径

解析：

对于点x，其左边最近的点x1，上面x2（若不存在x1，x2，则无限延伸），若这三个点组成的矩形内（不包含边）有其他点，那么这个点与x便没有路径。其他方向一样。

上图中，8往左上方延伸的矩形中有点3，则3与8之间不存在路径。

接下来就容易想了，上面点代表的版本减去左边点代表的版本，即可判断这个矩阵中是否存在数即可。

结束版本为第i-1次操作，保证不会多加点到矩阵中（同一列会在矩阵上方）。起始版本这里用的是左边最近点的那次操作，原因同。

有个大bug，开始把insert(ls[last],ls[now]=++cnt,l,mid,pos);写成insert(ls[now],ls[now]=++cnt,l,mid,pos);，我以为是值传递，就算之后改变了也没关系。但是实际上，这样写第一个ls[now]传进去的也是++cnt。

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define mid (l+r>>1)
const int maxn=500000+5;
struct node{
    int a,b;
}e[maxn];
bool cmp1(node a,node b){
    if(a.a!=b.a)return a.a<b.a;
    return a.b>b.b;
}bool cmp2(node a,node b){
    if(a.a!=b.a)return a.a>b.a;
    return a.b>b.b;
}
int tmpb[maxn];

int rt[maxn],ls[maxn*20],rs[maxn*20],siz[maxn*20],cnt;
void build(int rt,int l,int r){//建空树 rt[0]=0
    siz[rt]=0;
    if(l==r)return;
    build(ls[rt]=++cnt,l,mid);
    build(rs[rt]=++cnt,mid+1,r);
}
void insert(int last,int now,int l,int r,int pos){
    siz[now]=siz[last]+1;
    ls[now]=ls[last],rs[now]=rs[last];
    if(l==r)return;
    if(pos<=mid)insert(ls[last],ls[now]=++cnt,l,mid,pos);
    else insert(rs[last],rs[now]=++cnt,mid+1,r,pos);
}
int query(int rt,int l,int r,int L,int R){
    if(l>=L&&r<=R)return siz[rt];
    int res=0;
    if(L<=mid)res+=query(ls[rt],l,mid,L,R);
    if(R>mid)res+=query(rs[rt],mid+1,r,L,R);
    return res;
}

int pre[maxn];//左边第一个点
void init(int num){
    cnt=0;
    build(0,1,num);
    rep(i,1,num)pre[i]=0;
}
bool deal(int num,int n){
    init(num);
    rep(i,1,n){
        insert(rt[i-1],rt[i]=++cnt,1,num,e[i].b);
        if((e[i].a==e[i-1].a&&e[i-1].b-e[i].b==1)||e[i].b==num){
            pre[e[i].b]=i;
            continue;
        }
        int up=num+1;
        if(e[i].a==e[i-1].a){
            up=e[i-1].b;
        }
        int sub=query(rt[i-1],1,num,e[i].b+1,up-1)
            -query(rt[pre[e[i].b]],1,num,e[i].b+1,up-1);
        if(sub<0)while(1){}
        if(sub)return 1;
        pre[e[i].b]=i;
    }
    return 0;
}
int main(){
    int n;while(cin>>n){
        if(n==0)break;
        //离散化
        rep(i,1,n){
            scanf("%d%d",&e[i].a,&e[i].b);
            tmpb[i]=e[i].b;
        }
        sort(tmpb+1,tmpb+1+n);
        int num=unique(tmpb+1,tmpb+1+n)-tmpb-1;
        rep(i,1,n){
            e[i].b=lower_bound(tmpb+1,tmpb+1+num,e[i].b)-tmpb;
        }
        sort(e+1,e+1+n,cmp1);
        //去重
        int nn=0;
        rep(i,1,n){
            if(!(e[i].a==e[i-1].a&&e[i].b==e[i-1].b))e[++nn].a=e[i].a,e[nn].b=e[i].b;
        }
        n=nn;

        if(deal(num,n))printf("NO\n");
        else{
            sort(e+1,e+1+n,cmp2);
            if(deal(num,n))printf("NO\n");
            else printf("YES\n");
        }
    }
}