描述

先給出n個點, 然后有m個操作, (1, x, y) 表示查詢離(x, y)最近點的曼哈頓距離, (2, x, y) 表示插入點 (x, y).

分析

• 不會做... 又照著別人的代碼打了一遍... CDQ分治總想不到思路
• 比較關鍵的幾個地方是 : 1. 坐標的范圍是小于1000000的所以可以用樹狀數組維護. 2. 距離點(x, y)最近的點和x的方位有四種, 左下左上右下右上, 然后只考慮一個方位, 另外的改變坐標即可. 3. 曼哈頓距離不是歐幾里得距離, 是橫縱坐標之差絕對值的和. dis({x, y}, {x', y'}) = |x-x'| + |y-y'|. 在只考慮(x', y')在(x, y)的左下方時, 可以去掉絕對值 : dis = x+y - (x'+y'), 使x'+y'最大即可.
• 分治時始終保持橫坐標遞增, 分治時考慮左邊對右邊的影響, 上面說了要使dis = x+y - (x'+y')的x'+y'最大, 就按 x' 排序按 y' 用樹狀數組維護x'+y'的最大值. 在樹狀數組中查詢小于y的最大x'+y'值.

代碼
#include #include using namespace std;const int maxn = 1000000 + 10; const int INF = 1000000000;int max_x; int ans[maxn];struct BIT {int c[maxn];int lowbit(int x) {return x & (-x);}void modify(int x, int d) {while(x <= max_x) {c[x] = max(c[x], d);x += lowbit(x);}}int query(int x) {int ret = 0;while(x > 0) {ret = max(ret, c[x]);x -= lowbit(x);}return ret;}void clear(int x) {while(x <= max_x) {c[x] = 0;x += lowbit(x);}} } bit;struct Node {int x, y, k, id;bool operator < (const Node& rhs) const {if(x != rhs.x) return x < rhs.x;return id < rhs.id;} } A[maxn];#define a A[i] #define b A[j]struct CDQ {int n;Node T[maxn];void init(int n) {this->n = n;sort(A+1, A+n+1);}void solve(int L, int R) {if(L >= R) return;int M = (L+R) >> 1;int i, j, p = L, q = M+1;for(i = L; i <= R; i++) if(a.id <= M) T[p++] = a; else T[q++] = a;for(i = L; i <= R; i++) A[i] = T[i];solve(L, M);i = M+1; j = L;for(; i <= R; i++) if(a.k == 2) {for(; j <= M && b.x <= a.x; j++) if(b.k == 1)bit.modify(b.y, b.x+b.y);int t = bit.query(a.y);if(t) ans[a.id] = min(ans[a.id], a.x+a.y-t);}for(i = L; i < j; i++) if(a.k == 1)bit.clear(a.y);solve(M+1, R);merge(A+L, A+M+1, A+M+1, A+R+1, T+L);for(i = L; i <= R; i++) A[i] = T[i];}} cdq;int main() {int n, m;scanf("%d %d", &n, &m);for(int i = 1; i <= n; i++) {scanf("%d %d", &a.x, &a.y);a.x++; a.y++; a.id = i; a.k = 1;max_x = max(max_x, max(a.x, a.y));}for(int i = n+1; i <= n+m; i++) {scanf("%d %d %d", &a.k, &a.x, &a.y);a.x++; a.y++; a.id = i;max_x = max(max_x, max(a.x, a.y));}max_x++; n += m;for(int i = 1; i <= n; i++) ans[i] = INF;cdq.init(n); cdq.solve(1, n);for(int i = 1; i <= n; i++) a.x = max_x - a.x;cdq.init(n); cdq.solve(1, n);for(int i = 1; i <= n; i++) a.y = max_x - a.y;cdq.init(n); cdq.solve(1, n);for(int i = 1; i <= n; i++) a.x = max_x - a.x;cdq.init(n); cdq.solve(1, n);for(int i = 1; i <= n; i++)if(ans[i] != INF) printf("%d\n", ans[i]);return 0; }

總結

以上是生活随笔為你收集整理的BZOJ-2716-天使玩偶angel-CDQ分治的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。