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

• 2018-02-18
• 0
• 3

## Problem:

### 题目描述

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

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

```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```

## 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);
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 2020-03-31 03:06回复

大神，实话讲，虽然不会影响ac什么的, 但是您的check代码中up和dwn搞反了有碍于蒟蒻阅读哒~

• ###### willem 2020-07-20 12:19回复

我看了一下，似乎没反啊。扫描是从下往上的。（可怜.jpg）

• ###### yfs 2020-03-31 03:07回复

大神, 虽然不会影响ac什么的，但是check中up和dwn写反了真的好吗?

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai