[cf 1139] F. Dish Shopping

佚名 6年前 (2019-04-18) 随笔 1776人围观抢沙发百度已收录

题意

给\(m\)个二维点，和\(n\)个等腰直角三角形，求对于每个点，被多少个三角形包含（边界也算）。

三角形给出形式：直角顶点\((p, b)\)，斜边在\(x = s\)上。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

刚开始以为是整体二分之类的，然后被zlhD了一下后发现不用。

我们考虑把一个三角形的贡献拆成若干个不封闭区域的贡献。

具体来说，就是容斥之后，只要对于每个点求一些形如

1.\(y + y_0 = x + x_0\)与\(y + y_0 = -x + x_0\)围成的直角不封闭区域；

2.\(x = x_0\)与\(y + y_0 = -x + x_0\)围成的135°角不封闭区域；

的区域的贡献和即可（容斥的过程中会有开闭区间的问题，不过不难处理）。

不妨只考虑第一种区域（第二种类似）。

我们考虑可以把每一个点变成从这个点射出去的斜率为1和-1的两条射线。

然后考虑一个点被一个区域包含当且仅当这个点射出的射线所形成的新区域。考虑在无穷远处有一堵墙，那么所照到的区间（即区域在\(x = \infty\)处的最下端和最上端形成的区间）一定是包含关系。

那么就变成了对于每个点，求其对应的区间被几个区域对应的区间包含即可。这个可以直接排序后树状数组。

复杂度\(O(n \log n)\)。

#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pi;
typedef long long ll;

inline int read () {
    static int x;
    scanf("%d", &x);
    return x;
}
const int N = 1e5 + 5;
int n, m;
int p[N], s[N], b[N];
int ans[N];
struct P {int x, y, i;} a[N];
bool Pcmp_x (const P &u, const P &v) {return u.x < v.x;}
bool Pcmp_y (const P &u, const P &v) {return u.y < v.y;}
struct bitr {
    int n, c[N << 3];
    void init (int _n) {
        n = _n;
        memset(c, 0, sizeof c);
    }
    void add (int x, int v) {
        assert(abs(v) <= 1);
        assert(x <= n && x >= 1);
        for ( ; x <= n; x += x & (-x)) c[x] += v;
    }
    int sum (int x, int ret = 0) {
        assert(x <= n && x >= 1);
        for ( ; x; x -= x & (-x)) ret += c[x];
        return ret;
    }
};
struct interv {
    int l, r, v;
    bool operator < (const interv &o) const {
        return r == o.r ? v < o.v : r > o.r;
    }
};
struct triangle {int x, y, v;};
bool Tcmp_x (const triangle &u, const triangle &v) {return u.x < v.x;}
bool Tcmp_y (const triangle &u, const triangle &v) {return u.y < v.y;}

int nt; triangle tri[N << 1];
int nf; interv f[N << 2];
int nv, val[N << 3];
bitr t;
namespace Triangles {
    void discrete () {
        nv = 0;
        for (int i = 1; i <= nf; ++i) val[++nv] = f[i].l, val[++nv] = f[i].r;
        sort(val + 1, val + 1 + nv), nv = unique(val + 1, val + 1 + nv) - val - 1;
        for (int i = 1; i <= nf; ++i) {
            f[i].l = lower_bound(val + 1, val + 1 + nv, f[i].l) - val;
            f[i].r = lower_bound(val + 1, val + 1 + nv, f[i].r) - val;
        }
        sort(f + 1, f + 1 + nf);
    }
    void main_solve () {
        sort(a + 1, a + m + 1, Pcmp_x);
        nt = 0;
        for (int i = 1; i <= n; ++i) {
            tri[++nt] = (triangle) {p[i], b[i], 0};
            tri[++nt] = (triangle) {s[i] + 1, b[i] + s[i] - p[i] + 1, -1};
        }
        sort(tri + 1, tri + nt + 1, Tcmp_x);
        int limit = max(a[m].x, tri[nt].x);
        nf = 0;
        for (int i = 1; i <= nt; ++i) f[++nf] = (interv) {tri[i].y - (limit - tri[i].x), tri[i].y + (limit - tri[i].x), tri[i].v};
        for (int i = 1; i <= m; ++i) f[++nf] = (interv) {a[i].y - (limit - a[i].x), a[i].y + (limit - a[i].x), a[i].i};
        discrete();
        t.init(nv);
        for (int i = 1; i <= nf; ++i) {
            if (f[i].v < 1) {
                if (f[i].v == 0) f[i].v = 1;
                t.add(f[i].l, f[i].v);
            } else ans[f[i].v] += t.sum(f[i].l);
        }
    }
}
namespace Htriangles {
    void discrete () {
        nv = 0;
        for (int i = 1; i <= nf; ++i) val[++nv] = f[i].l, val[++nv] = f[i].r;
        sort(val + 1, val + 1 + nv), nv = unique(val + 1, val + 1 + nv) - val - 1;
        for (int i = 1; i <= nf; ++i) {
            f[i].l = lower_bound(val + 1, val + 1 + nv, f[i].l) - val;
            f[i].r = lower_bound(val + 1, val + 1 + nv, f[i].r) - val;
        }
        sort(f + 1, f + 1 + nf);
    }
    void main_solve () {
        sort(a + 1, a + m + 1, Pcmp_x);
        nt = 0;
        for (int i = 1; i <= n; ++i) {
            tri[++nt] = (triangle) {s[i] + 1, b[i] - s[i] - 1 + p[i], 0};
            tri[++nt] = (triangle) {s[i] + 1, b[i] + s[i] + 1 - p[i], -1};
        }
        sort(tri + 1, tri + nt + 1, Tcmp_x);
        int limit = max(a[m].x, tri[nt].x);
        nf = 0;
        for (int i = 1; i <= nt; ++i) f[++nf] = (interv) {tri[i].y - (limit - tri[i].x), -tri[i].x, tri[i].v};
        for (int i = 1; i <= m; ++i) f[++nf] = (interv) {a[i].y - (limit - a[i].x), -a[i].x, a[i].i};
        discrete();
        t.init(nv);
        for (int i = 1; i <= nf; ++i) {
            if (f[i].v < 1) {
                if (f[i].v == 0) f[i].v = 1;
                t.add(f[i].l, f[i].v);
            } else ans[f[i].v] -= t.sum(f[i].l);
        }
    }
}
signed main () {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) p[i] = read();
    for (int i = 1; i <= n; ++i) s[i] = read();
    for (int i = 1; i <= n; ++i) b[i] = read();
    for (int i = 1; i <= m; ++i) a[i].x = read();
    for (int i = 1; i <= m; ++i) a[i].y = read();
    for (int i = 1; i <= m; ++i) a[i].i = i;
    Triangles :: main_solve();
    Htriangles :: main_solve();
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}