[洛谷春令营 D2T1] 祭坛【离散化+扫描线+树状数组】

• 2018-02-18
• 0
• 3

Problem:

题目背景

在遥远的Dgeak大陆，生活着一种叫做Dar-dzo-nye的怪物。每当这种怪物降临，人们必须整夜对抗怪物而不能安睡。为了乞求这种怪物不再降临，人们决定建造祭坛。

题目描述

Dgeak大陆可以看成一个用平面直角坐标系表示的巨大平面。在这个平面上，有 n 个Swaryea水晶柱，每个水晶柱可以用一个点表示。

如果 4 个水晶柱依次相连可以构成一个四边形，满足其两条对角线分别平行于 x 轴和 y 轴，并且对角线的交点位于四边形内部（不包括边界），那么这 4 个水晶柱就可以建立一个结界。其中，对角线的交点称作这个结界的中心。

例如下左图中，水晶柱 ABCD 可以建立一个结界，其中心为 O。

为了起到抵御Dar-dzo-nye的最佳效果，人们会把祭坛修建在最多层结界的保护中。其中不同层的结界必须有共同的中心，这些结界的边界不能有任何公共点，并且中心处也不能有水晶柱。这里共同中心的结界数量叫做结界的层数。

为了达成这个目的，人们要先利用现有的水晶柱建立若干个结界，然后在某些结界的中心建立祭坛。

例如上右图中，黑色的点表示水晶柱（注意 P 和 O 点不是水晶柱）。祭坛的一个最佳位置为 O 点，可以建立在 3 层结界中，其结界的具体方案见下左图。当然，建立祭坛的最佳位置不一定是唯一，在上右图中，O 点左侧 1 单位的点 P 也可以建立一个在 3 层结界中的祭坛，见下右图。

现在人们想知道：

1. 祭坛最佳选址地点所在的结界层数；
2. 祭坛最佳的选址地点共有多少个。

输入输出格式

输入格式：

输入的第一行包含两个正整数 n,表示水晶柱的个数

接下来 n 行，每行包含两个非负整数 x,y，表示每个水晶柱的坐标。保证相同的坐标不会重复出现。

输出格式：

第一行一个整数，表示祭坛最多可以位于多少个结界的中心

第二行一个整数，表示结界数最多的方案有多少种。

输入输出样例

26
0 5
1 1
1 5
1 9
3 5
3 10
4 0
4 1
4 2
4 4
4 6
4 9
4 11
5 0
5 2
5 4
5 8
5 9
5 10
5 11
6 5
7 5
8 5
9 10
10 2
10 5

3
2

说明

对于30%的数据 n <= 1000

另外30%的数据 n <= 10000

剩下的40%数据 n <= 100000

保证 0 <= x, y <= n

Solution:

先离散化，预处理出横坐标为 i 的点的个数 x[i]，将纵坐标为 i 的点存在 vector y[i] 中并排序。

二分层数 k，按 y 坐标从小到大扫描。

我们发现当 y[i] 的大小 ys ≥ 2 * k 时，区间 (y[i][k-1], y[i][ys-k]) 上的点都有可能符合要求。

考虑维护数组 up[i], dwn[i] 表示当前扫描线上下方横坐标为 i 的点。

那么当某一点的 dwn[i] ≥ k 且 up[i] ≥ k 时，该点才可能符合要求，用树状数组求区间和即可。

注意有水晶柱的点不能建立祭坛，所以每次若这些点被树状数组计入答案，则先将它们的贡献删除，并用栈记录，询问完答案后将其恢复即可。

Code: O(nlog²n) [9457K, 536MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 100002;

struct Coord {int x, y;} cr[MAXN];
int n, xc[MAXN], xs, yc[MAXN], ys;
int x[MAXN], up[MAXN], dwn[MAXN];
int stk[MAXN], tops = 0;
vector<int> y[MAXN];

struct BIT{
	int node[100002];
	
	inline void clear() {memset(node, 0, sizeof(node));}
	
	inline void add(register int u, register int v)
		{while(u < 100002) node[u] += v, u += u & -u;}
	
	inline int query(register int u)
		{int res = 0; while(u) res += node[u], u -= u & -u; return res;}
	
	inline int query(register int l, register int r)
		{return query(r) - query(l - 1);}
} b;

inline int check(int k, bool md = 0){
	memcpy(up, x, sizeof(up)), memset(dwn, 0, sizeof(dwn)), b.clear();
	int res = 0;
	for(register int i = 1; i <= ys; i++){
		if(i > 1){
			int dwnsz = y[i - 1].size();
			for(register int j = 0; j < dwnsz; j++){
				int &cur = y[i - 1][j];
				if(++dwn[cur] == k && x[cur] >= (k << 1)) b.add(cur, 1);				
			}
		}
		int sz = y[i].size();
		for(register int j = 0; j < sz; j++){
			int &cur = y[i][j];
			if(up[cur]-- == k && x[cur] >= (k << 1)) b.add(cur, -1);
			if(b.query(cur, cur) == 1) b.add(cur, -1), stk[tops++] = cur;
		}
		if(sz >= (k << 1)) res += b.query(y[i][k - 1] + 1, y[i][sz - k] - 1);
		while(tops) b.add(stk[--tops], 1);
		if(!md && res) return 1;
	}
	return res;
}

int main(){
	scanf("%d", &n);
	for(register int i = 1; i <= n; i++){
		scanf("%d%d", &cr[i].x, &cr[i].y);
		xc[i] = cr[i].x, yc[i] = cr[i].y;
	}
	sort(xc + 1, xc + n + 1), sort(yc + 1, yc + n + 1);
	xs = unique(xc + 1, xc + n + 1) - xc - 1;
	ys = unique(yc + 1, yc + n + 1) - yc - 1;
	for(register int i = 1; i <= n; i++){
		cr[i].x = lower_bound(xc + 1, xc + xs + 1, cr[i].x) - xc;
		cr[i].y = lower_bound(yc + 1, yc + ys + 1, cr[i].y) - yc;
		x[cr[i].x]++, y[cr[i].y].push_back(cr[i].x);
	}
	for(register int i = 1; i <= ys; i++)
		if(y[i].size() > 1) sort(y[i].begin(), y[i].end());
	
	int L = 0, R = n >> 2;
	while(L < R){
		int Mid = L + R + 1 >> 1;
		if(check(Mid)) L = Mid;
		else R = Mid - 1;
	}
	printf("%d\n%d\n", L, check(L, 1));
	return 0;
}