2016-08-23

HDU 5820 Lights【zkw线段树，扫描线】

题目链接：

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

题意：

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

分析：

主席树+扫描线版本
在判断矩形内是否有其他点的时候可以用线段树做。
因为纵坐标最大$5e4$，所以可以用线段树保存每个纵坐标对应的最大的$x$，这样从左向右，从上向下扫，到达点$(x,y)$判断正上方，正下方，正左方组成的矩形区域内是否有其他点，即在正上方和正下方之间是否存在一个纵坐标，其对应的横坐标大于$(x,y)$的正左方点的横坐标。大体和主席树的处理一样，对于每个$x$，先查询，再更新。单点更新，区间查询，套个zkw线段树就行，比主席树好想，最后也快很多。

代码：

/*************************************************************************
    > File Name: 5820_2.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/23 13:45: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 = 5e4 + 1;
int T[maxm * 8];
int M, n;
void add(int a, int x)
{
	T[a += M] = x;
	for(a >>= 1;a;a >>= 1){
		T[a] = max(T[a << 1], T[a << 1|1]);
	}
}
int query(int l, int r)
{
	l = l + M - 1, r = r + M + 1;
	int ans = 0;
	for(; l^r^1; l >>= 1, r >>= 1){
		if(~l & 1) ans = max(T[l ^ 1], ans);
		if(r & 1) ans = max(T[r ^ 1], ans);
	}
	return ans;
}
vector<int>v[maxm];
int main (void)
{
	for(M = 1; M <= maxm + 1; M <<= 1);	
	while(~scanf("%d", &n) && n){
		int x, y;
		for(int i = 0; i < maxm; i++) v[i].clear();
		for(int i = 0; i < n; i++){
			scanf("%d%d", &x, &y);
			v[x].push_back(y);
		}
		for(int i = 1; i < maxm; 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;
		memset(T, 0, sizeof(T));	
		for(int i = 1; i < maxm; i++){
			if(!v[i].size()) continue;
			int sz = v[i].size();
			for(int j = 0; j < sz; j++){
				up = j ? v[i][j - 1]:0;
				down = j == v[i].size() - 1? maxm + 1:v[i][j + 1];
				if(query(up + 1, down - 1) > T[v[i][j] + M]) flag = false;
				if(!flag) break;
			}
			if(!flag) break;
			for(int j = 0; j < sz; j++){
				add(v[i][j], i);
			}
		}
		flag?puts("YES"):puts("NO");
	}
	return 0;
}