[洛谷春令营 D2T1] 祭坛【离散化+扫描线+树状数组】
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 层结界中的祭坛,见下右图。
现在人们想知道:
- 祭坛最佳选址地点所在的结界层数;
- 祭坛最佳的选址地点共有多少个。
输入输出格式
输入格式:
输入的第一行包含两个正整数 n,表示水晶柱的个数
接下来 n 行,每行包含两个非负整数 x,y,表示每个水晶柱的坐标。保证相同的坐标不会重复出现。
输出格式:
第一行一个整数,表示祭坛最多可以位于多少个结界的中心
第二行一个整数,表示结界数最多的方案有多少种。
输入输出样例
输入样例#1:
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
输出样例#1:
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(nlog2n) [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; }
yfs
大神,实话讲,虽然不会影响ac什么的, 但是您的check代码中up和dwn搞反了有碍于蒟蒻阅读哒~
willem
我看了一下,似乎没反啊。扫描是从下往上的。(可怜.jpg)
yfs
大神, 虽然不会影响ac什么的,但是check中up和dwn写反了真的好吗?