bzoj 1941 [sdoi 2010] 숨 기기 및 탐색 선분 트 리 / kd - tree

표제 면
제목 전송 문
해법
kd - tree 를 고려 할 수 있 지만 저 는...
  • 모든 i i 에 대해 우 리 는 m a x (8739 ° x [i] - x [j] 8739 ° + 8739 ° y [i] - y [j] 8739 °) max (| x [i] | y [i]] - y [i] - y [i] | y] - y [j] |) max (8739 ° x [i] - 8739 ° y + 8739 ° y [i] - 8739 ° y [i] - 8739 ° y], m i n min 유사
  • 4144 가지 상황 을 고려 하면 절대 치 를 뜯 는 것
  • x [j] ≤ x [i] x [j] ≤ x [i] x [i] x [i] x [i] x [j] ≤ x [i] 및 y [j] ≤ y [i] y [j] ≤ y [i] y [j] ≤ y [i] 의 경우, 기타 3 가지 상황 은 유사 하 다
  • 절대 치 를 펼 친 것 을 발견 하면 (x [i] + y [i]) − (x [j] + y [j]) (x [i] + y [i]) - (x [j] + y [j]) - (x [j] + y [j]) - (x [j] + y [j]), 그러면 우 리 는 x x x x x 에서 작은 것 부터 큰 것 까지 순 서 를 매기 고 x x x x x 와 같은 때 y y 에 따라 작은 것 부터 큰 것 까지
  • 그리고 우 리 는 i i 를 매 거 하여 j < i j < i j < i, 그리고 선분 나무 로 만족 y [j] y [j] y [j] y [j] 구간 [1, y [i] [1, y [i]] [1, y [i]] 의 x [j] + y [j] x [j] + y [j] x [j] + y [j] + y [j] + y [j] 의 최소 값
  • 을 유지 합 니 다.
  • 이런 상황 에서 도 j j j 는 i i 에 의 해 통계 되 지 않 을 수 있 지만 다른 상황 에서 j j j 는 반드시 i i i 에 의 해 통계 되 기 때문에 알고리즘 이 정확 하 다
  • 는 것 을 알 수 있다.
  • 꼭 선분 수 를 사용 해 야 하 는 것 은 아니다. 나무 모양 의 배열 도 이 일 을 완성 할 수 있 을 것 같다
  • 시간 복잡 도: O (n log ⁡ n) O (n \ log n) O (nlogn)
  • 코드
    #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; }

    좋은 웹페이지 즐겨찾기