bzoj 1941 [sdoi 2010] 숨 기기 및 탐색 선분 트 리 / kd - tree
49071 단어 【OJ】BZOJ[데이터 구조] 선분 트 리
제목 전송 문
해법
kd - tree 를 고려 할 수 있 지만 저 는...
#include
#define inf 1 << 29
#define N 200010
using namespace std;
template <typename node> void chkmax(node &x, node y) {x = max(x, y);}
template <typename node> void chkmin(node &x, node y) {x = min(x, y);}
template <typename node> void read(node &x) {
x = 0; int f = 1; char c = getchar();
while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
struct Point {
int x, y, id;
} a[N];
struct SegmentTree {
struct Node {
int lc, rc, mx, mn;
} t[N * 4];
int tot;
void Clear() {tot = 0, memset(t, 0, sizeof(t));}
void ins(int &k, int l, int r, int x, int v) {
if (!k) k = ++tot, t[k].mn = inf, t[k].mx = -inf;
chkmin(t[k].mn, v), chkmax(t[k].mx, v);
if (l == r) return; int mid = (l + r) >> 1;
if (x <= mid) ins(t[k].lc, l, mid, x, v);
else ins(t[k].rc, mid + 1, r, x, v);
}
pair <int, int> query(int k, int l, int r, int L, int R) {
if (!k) return make_pair(-inf, inf);
if (L <= l && r <= R) return make_pair(t[k].mx, t[k].mn);
int mid = (l + r) >> 1;
if (R <= mid) return query(t[k].lc, l, mid, L, R);
if (L > mid) return query(t[k].rc, mid + 1, r, L, R);
pair <int, int> tx = query(t[k].lc, l, mid, L, mid), ty = query(t[k].rc, mid + 1, r, mid + 1, R);
return make_pair(max(tx.first, ty.first), min(tx.second, ty.second));
}
} T;
bool cmp1(Point a, Point b) {return (a.x == b.x) ? a.y < b.y : a.x < b.x;}
bool cmp2(Point a, Point b) {return (a.x == b.x) ? a.y > b.y : a.x < b.x;}
bool cmp3(Point a, Point b) {return (a.x == b.x) ? a.y < b.y : a.x > b.x;}
bool cmp4(Point a, Point b) {return (a.x == b.x) ? a.y > b.y : a.x > b.x;}
int tx[N], mx[N], mn[N];
int main() {
int n, len = 0; read(n);
for (int i = 1; i <= n; i++)
read(a[i].x), read(a[i].y), tx[++len] = a[i].x, tx[++len] = a[i].y, a[i].id = i;
sort(tx + 1, tx + len + 1); len = unique(tx + 1, tx + len + 1) - tx - 1;
map <int, int> h;
for (int i = 1; i <= len; i++) h[tx[i]] = i;
for (int i = 1; i <= n; i++) a[i].x = h[a[i].x], a[i].y = h[a[i].y];
sort(a + 1, a + n + 1, cmp1), T.Clear(); int rt = 0;
for (int i = 1; i <= n; i++) mx[i] = -inf, mn[i] = inf;
for (int i = 1; i <= n; i++) {
pair <int, int> tmp = T.query(rt, 1, len, 1, a[i].y);
chkmax(mx[a[i].id], tx[a[i].x] + tx[a[i].y] - tmp.second);
chkmin(mn[a[i].id], tx[a[i].x] + tx[a[i].y] - tmp.first);
T.ins(rt, 1, len, a[i].y, tx[a[i].x] + tx[a[i].y]);
}
sort(a + 1, a + n + 1, cmp2), T.Clear(); rt = 0;
for (int i = 1; i <= n; i++) {
pair <int, int> tmp = T.query(rt, 1, len, a[i].y, len);
chkmax(mx[a[i].id], tx[a[i].x] - tx[a[i].y] - tmp.second);
chkmin(mn[a[i].id], tx[a[i].x] - tx[a[i].y] - tmp.first);
T.ins(rt, 1, len, a[i].y, tx[a[i].x] - tx[a[i].y]);
}
sort(a + 1, a + n + 1, cmp3), T.Clear(); rt = 0;
for (int i = 1; i <= n; i++) {
pair <int, int> tmp = T.query(rt, 1, len, 1, a[i].y);
chkmax(mx[a[i].id], -tx[a[i].x] + tx[a[i].y] - tmp.second);
chkmin(mn[a[i].id], -tx[a[i].x] + tx[a[i].y] - tmp.first);
T.ins(rt, 1, len, a[i].y, -tx[a[i].x] + tx[a[i].y]);
}
sort(a + 1, a + n + 1, cmp4), T.Clear(), rt = 0;
for (int i = 1; i <= n; i++) {
pair <int, int> tmp = T.query(rt, 1, len, a[i].y, len);
chkmax(mx[a[i].id], -tx[a[i].x] - tx[a[i].y] - tmp.second);
chkmin(mn[a[i].id], -tx[a[i].x] - tx[a[i].y] - tmp.first);
T.ins(rt, 1, len, a[i].y, -tx[a[i].x] - tx[a[i].y]);
}
int ans = inf;
for (int i = 1; i <= n; i++)
chkmin(ans, mx[i] - mn[i]);
cout << ans << "
";
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BZOJ 3676] [APIO 2014] 댓 글 꼬치.[제목 링크] 클릭 하여 링크 열기 [아이디어 포인트] 리 턴 트 리 템 플 릿 문제. 시간 복잡 도 【 코드 】...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.