2016-08-22

HDU 5820 Lights【主席树，扫描线】

题目链接：

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

题意：

给定网格及$n$盏路灯的坐标。问是否任意两盏灯之间都存在一条道路，使得长度为$|x1–x2|+|y1–y2|$且每个拐弯处都有路灯。

分析：

对于每个点(x, y)，正左方最近的点记为(x’, y)，正上（下）方最近的点记为(x, y’)，如果以这3个点为顶点的矩形内部存在有其它的点(x’’, y’’)，则从(x, y)到(x’’, y’’)不存在good path. 反之，如果整个图中都不存在这种情况，则任意两点间都有good path. 因而可以用扫描线和可持久化线段树来做，从左往右扫描，每个x值对应线段树的一个版本，每遇到一个点(x, y)和它正上（下）方最近的点(x, y’)就在当前版本的线段树和版本为x’的线段树上查询y和y’之间的点数，如果这两个值不相等，则意味着存在上述的点(x’’,y’’). 对于每条扫描线处理完查询之后再将点插入到当前版本的线段树中. 复杂度O(NlogN).

对于每个$x$，在其每个$y$处对线段树进行更新，并记录左边最近的点的横坐标，最后再将该$x$与最后版本的线段树对应起来。从左向右扫一遍，先判断，后更新。

主席树资料：http://www.cnblogs.com/zyf0163/p/4749042.html

代码：

/*************************************************************************
    > File Name: 5820.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/21 10:50:44
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;//[]
const int maxn = 5e5 + 5, maxm = 20 * maxn;
int lson[maxm], rson[maxm], t[maxm], tree[maxm];
int c = 5e4, tot;
//lson,rson记录左右节点标号，t记录每一个前缀构成的线段树的根节点标号，tree记录标号对应区间中数字出现次数
int build(int l, int r)
{
    int root = tot++; tree[root] = 0;
    int mid = l + r >> 1;
    if(l == r) return root;
    lson[root] = build(l, mid);
    rson[root] = build(mid + 1, r);
    return root;
}
int update(int root, int l, int r, int num)
{
	int newroot = tot++;
    tree[newroot] = tree[root] + 1;
    if(l == r) return newroot;
    int mid = l + r >> 1;
    if(num <= mid){
        lson[newroot] = update(lson[root], l, mid, num);//有变动，重新建立
        rson[newroot] = rson[root];//右边不变
        
    }else{
        rson[newroot] = update(rson[root], mid + 1, r, num);//有变动，重新建立
        lson[newroot] = lson[root];//左边不变
    }
	return newroot;
}
int query(int L, int R, int l, int r, int i)
{
	if(l == L && r == R) return tree[i];
	int mid = l + r >> 1;
	if(R <= mid) return query(L, R, l, mid, lson[i]);
	else if(L > mid) return query(L, R, mid + 1, r, rson[i]);
	else return query(L, mid, l, mid, lson[i]) + query(mid + 1, R, mid + 1, r, rson[i]);
}
vector<int>v[maxn];
int pre[maxn];
int main (void)
{
    int n;
	while(~scanf("%d", &n) && n){
		int x, y;
		tot = 0;
		for(int i = 1; i <= c; i++) v[i].clear();
		memset(pre, 0, sizeof(pre));
		for(int i = 0; i < n; i++){
			scanf("%d%d", &x, &y);
			v[x].push_back(y);
		}
		for(int i = 1; i <= c; i++){
			if(!v[i].size()) continue;
			sort(v[i].begin(), v[i].end());
			v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
		}
		int up, down;
		bool flag = true;
		t[0] = build(1, c);//初始化
		for(int i = 1; i <= c; i++){
			t[i] = t[i - 1];
			int sz = v[i].size();
			if(!sz) continue;
			for(int j = 0; j < sz; j++){
				y = v[i][j];
				up = j ? v[i][j - 1]:0;
				down = j == v[i].size() - 1?c + 1:v[i][j + 1];
				int cnt1 = query(up + 1, down - 1, 1, c, t[pre[y]]);
				int cnt2 = query(up + 1, down - 1, 1, c, t[i]);
				if(cnt1 != cnt2) flag = false;
				if(!flag) break;
			}
			if(!flag) break;
			for(int j = 0; j < sz; j++){
				t[i] = update(t[i], 1, c, v[i][j]);
				pre[v[i][j]] = i;
			}
		}
		if(flag) puts("YES");
		else puts("NO");
    }
    return 0;
}