1 条题解

  • 0
    @ 2026-9-26 18:13:19

    这道题咋没有题解，调了我好久

    题意：二维平面上有 zz 个点，给定 pp 个询问，每次两个点 P1P1、P2P2，求距离 P1P1 更近的点的个数、距离 P2P2 更近的点的个数以及与 P1P1、P2P2 距离相同的点的个数。距离为曼哈顿距离，横坐标值域为 [1,n][1,n]，纵坐标值域为 [1,m][1,m]。

    首先发现只需要考虑处理距离 P1P1 更近的点即可，因为问题的对称性。

    以下记点 AA 的横坐标为 XAX_A，纵坐标为 YAY_A。对于 zz 个点中的任意一个点 AA，我们列出关系式：$|X_A - X_{P1}| + |Y_A - Y_{P1}| < |X_A - X_{P2}| + |Y_A - Y_{P2}|$。

    根据初中数学知识，XAX_A、YAY_A 都有 3 种情况，一共 9 种情况，我们把它们在图像中表示出来。假设给定的 XP1≤XP2X_{P1} \le X_{P2}，YP1≤YP2Y_{P1} \le Y_{P2}。

    rt，显然区域 2、4、6、8，区域 1、9，区域 3、7，区域 5 为四种不同情况，以下进行分讨：

    记 a=XP2−XP1a = X_{P2} - X_{P1}，b=YP2−YP1b = Y_{P2} - Y_{P1}

    1. 区域 2、4、6、8

    以区域 8 为例，$\operatorname{dist}(P1,A) = \Delta y + (a - \Delta x) + b$，dist⁡(P2,A)=Δx+Δy\operatorname{dist}(P2,A) = \Delta x + \Delta y。

    要保证 $\operatorname{dist}(P1,A) < \operatorname{dist}(P2,A)$，即要保证 $\Delta y + (a - \Delta x) + b < \Delta x + \Delta y$，即 Δx>a+b2\Delta x > \frac{a + b}{2}，带入 Δx=XP2−XA\Delta x = X_{P2} - X_A 得 XA<XP2−a+b2X_A < X_{P2} - \frac{a + b}{2}。

    因而该区域满足条件的点 AA 需满足 $X_A \in [X_{P1},X_{P2}] \cap [0,X_{P2} - \frac{a + b}{2})$，YA∈(YP2,m]Y_A \in (Y_{P2}, m]。

    1. 区域 1、9

    以区域 9 为例，显然 $\operatorname{dist}(P1,A) > \operatorname{dist}(P2,A)$。（当然 P1 = P2 的情况需要特判）

    因此该区域所有点均不满足。

    1. 区域 3、7

    以区域 7 为例，$\operatorname{dist}(P1,A) = \Delta x + \Delta y + b$，$\operatorname{dist}(P2,A) = \Delta x + \Delta y + a$。

    可以发现当 b<ab < a 时 $\operatorname{dist}(P1,A) < \operatorname{dist}(P2,A)$。

    所以当 b<ab < a 时该区域所有点均满足。

    1. 区域 5

    区域 5 中，$\operatorname{dist}(P1,A) = (a - \Delta x) + (b - \Delta y)$，dist⁡(P2,A)=Δx+Δy\operatorname{dist}(P2,A) = \Delta x + \Delta y。

    要保证 $\operatorname{dist}(P1,A) < \operatorname{dist}(P2,A)$，即要保证 $(a - \Delta x) + (b - \Delta y) < \Delta x + \Delta y$，即 Δx+Δy>a+b2\Delta x + \Delta y > \frac{a + b}{2}，带入 Δy=YP2−YA\Delta y = Y_{P2} - Y_A、Δx=XP2−XA\Delta x = X_{P2} - X_A 得 XA+YA<XP2+YP2−a+b2X_A + Y_A < X_{P2} + Y_{P2} - \frac{a + b}{2}。

    因而该区域满足条件的点 AA 需满足 XA∈[XP1,XP2]X_A \in [X_{P1},X_{P2}]，YA∈[YP1,YP2]Y_A \in [Y_{P1}, Y_{P2}]，$X_A + Y_A \in [0, X_{P2} + Y_{P2} - \frac{a + b}{2})$。

    到这儿分类讨论结束。

    如果 P1P1、P2P2 不是偏序关系怎么办？一开始我想的是再分讨一次，但是太麻烦，我们可以考虑将整个平面反转。具体的，我们考虑翻转 (1,1)(n,m)(1,1)(n,m) 这个矩形，若是左右翻转则所有横坐标 XX 变为 n+1−Xn + 1 - X，若是上下翻转则所有纵坐标 YY 变为 m+1−Ym + 1 - Y。

    现在尝试维护答案。我们发现前三类只与 XAX_A，YAY_A 有关，且均为一段区间，考虑二维偏序，扫描线 + 树状数组即可。

    第 4 类（即区域 5）另外有个 XA+YAX_A + Y_A 的限制，是三维偏序。第一次打的时候用了二维线段树，空间爆炸喜提暴力分，于是专门新学了 KD-Tree 来用。

    不幸的是，KD-Tree 常数过大，加上代码自带大常数，无法 AC。

    尝试优化。我们在统计答案的时候换一个思路：统计 $\operatorname{dist}(P1,A)<\operatorname{dist}(P2,A)$、与 $\operatorname{dist}(P1,A)\le\operatorname{dist}(P2,A)$ 的点的数量 a1a1、a2a2。后者只是在原先的推导上，将小于改为小于等于。那么其实它们有很多询问是重叠的，甚至是相同的，可以在相同的时候一块维护。

    注意三个答案要变为 a1a1，z−a2z - a2，a2−a1a2 - a1。

    另外，KD-Tree 的询问速度较慢，可以把询问排一下序，相邻相同的询问使用同一个答案。

    最后再加上一些各类广为人知的卡常技巧就可以 AC 啦。

    ```cpp
#include <bits/stdc++.h>
#define mem(a, b) memset(a, b, sizeof(a))
#define re register
using namespace std;
namespace fastio {
    char *p1, *p2, buf[100000];
    #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
    void read(int &x) {
        x = 0; re int f = 1, ch = nc();
        while (ch < 48 || ch > 57) { if (ch == '-') f = -1; ch = nc(); }
        while (ch >= 48 && ch <= 57) { x = x * 10 + ch - 48; ch = nc(); }
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
inline const int &min(const int &x, const int &y) { return x < y ? x : y; }
inline const int &max(const int &x, const int &y) { return x > y ? x : y; }
const int N = 1e5 + 5, M = 8e5 + 5, inf = INT_MAX;
struct point { int x, y; };
bool operator==(const point &a, const point &b) { return a.x == b.x && a.y == b.y; }
int n, m, z, p;
point a[N], p1[N], p2[N];

namespace DS1 {
    struct kd_tree {
        static const int N = 1e5 + 5;
        const double A = 0.7;
        #define ls tr[p].lc
        #define rs tr[p].rc
        #define mid (l + r >> 1)
        int rt, tot, cnt;
        using point = array<int, 2>;
        struct node {
            int lc, rc, siz, sum, w;
            point v, a, b;
        } tr[N];
        void maintain(int p) {
            tr[p].siz = tr[ls].siz + tr[rs].siz + 1;
            tr[p].sum = tr[ls].sum + tr[rs].sum + tr[p].w;
            tr[p].a = tr[p].b = tr[p].v;
            if (ls) {
                tr[p].a[0] = min(tr[p].a[0], tr[ls].a[0]);
                tr[p].a[1] = min(tr[p].a[1], tr[ls].a[1]);
                tr[p].b[0] = max(tr[p].b[0], tr[ls].b[0]);
                tr[p].b[1] = max(tr[p].b[1], tr[ls].b[1]);
            }
            if (rs) {
                tr[p].a[0] = min(tr[p].a[0], tr[rs].a[0]);
                tr[p].a[1] = min(tr[p].a[1], tr[rs].a[1]);
                tr[p].b[0] = max(tr[p].b[0], tr[rs].b[0]);
                tr[p].b[1] = max(tr[p].b[1], tr[rs].b[1]);
            }
        }
        int g[N];
        int rebuild(int l, int r, int k) {
            if (l > r) return 0;
            nth_element(g + l, g + mid, g + r + 1, [&](int x, int y) {
                return tr[x].v[k] < tr[y].v[k];
            });
            tr[g[mid]].lc = rebuild(l, mid - 1, k ^ 1);
            tr[g[mid]].rc = rebuild(mid + 1, r, k ^ 1);
            maintain(g[mid]);
            return g[mid];
        }
        void dfs(int p) { if (p) g[++tot] = p, dfs(ls), dfs(rs); }
        void check(int &p, int k) {
            if (A * tr[p].siz < max(tr[ls].siz, tr[rs].siz))
                tot = 0, dfs(p), p = rebuild(1, tot, k);
        }
        void newnode(int x, int y, int w) { ++cnt, tr[cnt].v = {x, y}, tr[cnt].w = w; }
        void insert(int &p, int k) {
            if (!p) { p = cnt; maintain(p); return; }
            if (tr[cnt].v[k] < tr[p].v[k]) insert(ls, k ^ 1);
            else insert(rs, k ^ 1);
            maintain(p), check(p, k);
        }
        int query(int p, point a, point b) {
            if (!p) return 0;
            int a0 = tr[p].a[0], a1 = tr[p].a[1], b0 = tr[p].b[0], b1 = tr[p].b[1];
            if (b[0] < a0 || a[0] > b0 || b[1] < a1 || a[1] > b1) return 0;
            if (a[0] <= a0 && b0 <= b[0] && a[1] <= a1 && b1 <= b[1]) return tr[p].sum;
            int res = query(ls, a, b) + query(rs, a, b);
            int v0 = tr[p].v[0], v1 = tr[p].v[1], w = tr[p].w;
            if (a[0] <= v0 && v0 <= b[0] && a[1] <= v1 && v1 <= b[1]) res += w;
            return res;
        }
        void clear() { rt = cnt = 0; mem(tr, 0); }
    } tr;
    void update(int x, int y) { tr.newnode(x, y, 1), tr.insert(tr.rt, 0); }
    int query(int x0, int x1, int y0, int y1) { return tr.query(tr.rt, {x0, y0}, {x1, y1}); }
    void clear() { tr.clear(); }
}

namespace DS2 { // 求二维偏序
    static const int N = 3.2e6 + 5;
    struct BIT {
        #define lb(i) (i&-i)
        int c[N];
        void add(re int i, re int v) { for (; i < M; i += lb(i)) c[i] += v; }
        int query(re int i) { int r = 0; for (; i; i -= lb(i)) r += c[i]; return r; }
        void clear(int n) {
            for (re int i = 1; i <= n; i++) c[i] = 0;
        }
    } tr;
    int ori[N], tot, res[N];
    int qu[N], cnt;
    struct node {
        bool type; // 0: update(x, y v); 1: query(1, x, y)
        int ori_id, x, y;
        friend bool operator==(const node &a, const node &b) { return a.type == b.type && a.x == b.x && a.y == b.y; }
    } dat[N];
    void init_query(re int x0, re int x1, re int y0, re int y1, re int id) {
        if (x1 < x0 || y1 < y0) return;
        x0--, y0--;
        qu[cnt] = id;
        dat[++cnt] = {1, cnt, x1, y1}; dat[++cnt] = {1, cnt, x0, y1};
        dat[++cnt] = {1, cnt, x1, y0}; dat[++cnt] = {1, cnt, x0, y0};
        ori[++tot] = y0; ori[++tot] = y1;
    }
    void init_update(re int x, re int y) {
        dat[++cnt] = {0, cnt, x, y};
        ori[++tot] = y;
    }
    int gethash(re int y) {
        int l = 1, r = tot;
        while (l <= r) {
            if (ori[mid] == y) return mid;
            else if (y < ori[mid]) r = mid - 1;
            else l = mid + 1;
        }
        assert(0);
    }
    void init_hash() {
        sort(ori + 1, ori + tot + 1);
        tot = unique(ori + 1, ori + tot + 1) - ori - 1;
    }
    void solve(int *ans, int *ans2) {
        init_hash();
        sort(dat + 1, dat + cnt + 1, [](const node &x, const node &y) {
            if (x.x != y.x) return x.x < y.x;
            return x.type < y.type;
        });
        for (re int i = 1; i <= cnt; i++) {
            auto [type, ori_id, x, y] = dat[i];
            if (type == 0) tr.add(gethash(y), 1);
            else res[ori_id] = tr.query(gethash(y));
        }
        for (re int i = 0; i + 4 <= cnt; i++) {
            re int j = qu[i], t = res[i + 1] - res[i + 2] - res[i + 3] + res[i + 4];
            if (j) {
                if (j > p) ans[j - p] += t, ans2[j - p] += t;
                else if (j > 0) ans[j] += t;
                else ans2[-j] += t;
            }
        }
        tr.clear(tot);
    }
    void clear() { cnt = tot = 0; mem(qu, 0); }
}

struct node {
    bool type; // 0: add(x0, y0, xy), 1: query(x0, x1, y0, y1, xy)
    int id;
    int x0, x1, y0, y1, xy;
    friend bool operator==(const node &x, const node &y) { return x.type == y.type && x.x0 == y.x0 && x.x1 == y.x1 && x.y0 == y.y0 && x.y1 == y.y1; }
} dat[M];
int tot, vis[N]; // vis[i]: 第i个询问有没有处理
#define Le(x) ((int)floor(x))
#define Lt(x) ((int)ceil(x) - 1)
inline int le(int x, int y) { return x - (y + 1 >> 1); } // Le(x - y / 2) = floor(x - y / 2)
inline int lt(int x, int y) { return x - (y >> 1) - 1; } // Lt(x - y / 2) = ceil(x - y / 2) - 1
void solve(int *ans, int *ans2) {
    DS1::clear(), DS2::clear();
    tot = 0;
    for (re int i = 1; i <= p; i++) if (!vis[i]) {
        if (p1[i] == p2[i]) {
            vis[i] = 1;
            DS2::init_query(1, n, 1, m, -i);
        } else if (p1[i].x <= p2[i].x && p1[i].y <= p2[i].y) {
            vis[i] = 1;
            re int a = p2[i].x - p1[i].x, b = p2[i].y - p1[i].y, c, d;
            // 1
            DS2::init_query(1, p1[i].x - 1, 1, p1[i].y - 1, i + p);
            // 2
            c = min(lt(p2[i].x, a - b), p2[i].x), d = min(le(p2[i].x, a - b), p2[i].x);
            if (d >= p1[i].x) {
                if (c == d) DS2::init_query(p1[i].x, c, 1, p1[i].y - 1, i + p);
                else DS2::init_query(p1[i].x, c, 1, p1[i].y - 1, i),
                    DS2::init_query(p1[i].x, d, 1, p1[i].y - 1, -i);
            }
            // 3
            if (a < b) DS2::init_query(p2[i].x + 1, n, 1, p1[i].y - 1, i + p);
            else if (a == b) DS2::init_query(p2[i].x + 1, n, 1, p1[i].y - 1, -i);
            // 4
            c = min(lt(p2[i].y, b - a), p2[i].y), d = min(le(p2[i].y, b - a), p2[i].y);
            if (d >= p1[i].y) {
                if (c == d) DS2::init_query(1, p1[i].x - 1, p1[i].y, c, i + p);
                else DS2::init_query(1, p1[i].x - 1, p1[i].y, c, i),
                    DS2::init_query(1, p1[i].x - 1, p1[i].y, d, -i);
            }
            // 5
            c = lt(p2[i].x + p2[i].y, a + b), d = le(p2[i].x + p2[i].y, a + b);
            if (c == d)  dat[++tot] = {1, i + p, p1[i].x, p2[i].x, p1[i].y, p2[i].y, c};
            else dat[++tot] = {1, i, p1[i].x, p2[i].x, p1[i].y, p2[i].y, c},
                dat[++tot] = {1, -i, p1[i].x, p2[i].x, p1[i].y, p2[i].y, d};
            // 6
            c = min(lt(p2[i].y, b + a), p2[i].y), d = min(le(p2[i].y, b + a), p2[i].y);
            if (d >= p1[i].y) {
                if (c == d) DS2::init_query(p2[i].x + 1, n, p1[i].y, c, i + p);
                else DS2::init_query(p2[i].x + 1, n, p1[i].y, c, i),
                    DS2::init_query(p2[i].x + 1, n, p1[i].y, d, -i);
            }
            // 7
            if (b < a) DS2::init_query(1, p1[i].x - 1, p2[i].y + 1, m, i + p);
            else if (b == a) DS2::init_query(1, p1[i].x - 1, p2[i].y + 1, m, -i);
            // 8
            c = min(lt(p2[i].x, a + b), p2[i].x), d = min(le(p2[i].x, a + b), p2[i].x);
            if (d >= p1[i].x) {
                if (c == d) DS2::init_query(p1[i].x, c, p2[i].y + 1, m, i + p);
                else DS2::init_query(p1[i].x, c, p2[i].y + 1, m, i),
                    DS2::init_query(p1[i].x, d, p2[i].y + 1, m, -i);
            }
        }
    }
    for (re int i = 1; i <= z; i++) DS2::init_update(a[i].x, a[i].y);
    for (re int i = 1; i <= z; i++) dat[++tot] = {0, -1, a[i].x, 0, a[i].y, 0, a[i].x + a[i].y};
    sort(dat + 1, dat + tot + 1, [](const node &a, const node &b) {
        return a.xy == b.xy ? a.type < b.type : a.xy < b.xy;
    });
    for (re int i = 1, t; i <= tot; i++) {
        auto [type, id, x0, x1, y0, y1, xy] = dat[i];
        if (type == 0) DS1::update(x0, y0);
        else {
            if (!(dat[i] == dat[i - 1])) t = DS1::query(x0, x1, y0, y1);
            if (id > p) ans[id - p] += t, ans2[id - p] += t;
            else if (id > 0) ans[id] += t;
            else ans2[-id] += t;
        }
    }
    DS2::solve(ans, ans2);
}
#define opx(x) (n + 1 - (x))
#define opy(y) (m + 1 - (y))
int ans[N], ans2[N]; // dist1<dsti2 / dist1<=dist2
void get_ans(int *ans, int *ans2) {
    solve(ans, ans2);
    for (re int i = 1; i <= z; i++) a[i].y = opy(a[i].y);
    for (re int i = 1; i <= p; i++) p1[i].y = opy(p1[i].y), p2[i].y = opy(p2[i].y);
    solve(ans, ans2);
}
int swp[N];
signed main() {
    using fastio::read, fastio::write;
    read(n), read(m), read(z), read(p);
    for (re int i = 1; i <= z; i++) read(a[i].x), read(a[i].y);
    for (re int i = 1; i <= p; i++) read(p1[i].x), read(p1[i].y), read(p2[i].x), read(p2[i].y);
    for (re int i = 1; i <= p; i++) if (p1[i].x > p2[i].x) swap(p1[i], p2[i]), swp[i] = 1;
    get_ans(ans, ans2);
    for (re int i = 1; i <= p; i++) {
        int a = ans[i], b = z - ans2[i], c = ans2[i] - ans[i];
        if (swp[i]) swap(a, b);
        write(a), putchar(' ');
        write(b), putchar(' ');
        write(c), putchar('\n');
    }
    return 0;
}
    • 1

    [POI 2009] STR-Fire Brigade消防队

    信息

    ID
    2773
    时间
    6500ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    58
    已通过
    3
    上传者
    1. Language
    2. 兼容模式
    3. 主题
    3. Worker 0, 11ms
    4. Powered by Hydro v5.0.7 Community