Description

给定 $n$ 个互不重合的点 $(x_i,y_i)$，点有颜色 $c_i$。

$q$ 次查询 $(A,B,C)$，求出半平面 $Ax+By+C<0$ 包含的所有点中，选出两个点 $i\le j$，$c_i=c_j$ 的方案数。保证半平面不退化。

Limitations

$1\le n\le 5\times 10^4$

$1\le q\le 5\times 10^5$

$|x_i|,|y_i|,|A|,|B|,|C|\le 10^9$

保证 $x_i,y_i$ 随机。

$8\text{s},512\text{MB}$

Solution

基于随机的做法。

先把点和半平面反过来，那么查询会有 $A<0,A=0,A>0$ 三种情况，分开做就行。

然后答案就是对于每个颜色 $c$，设这个点被颜色为 $c$ 的所有半平面覆盖 $k$ 次，$k^2$ 的和。

这是个半平面数点，先建出 KDT。对每个颜色的半平面，在 KDT 上找出对应的节点打 $\text{tag}$，更新完后统一下放，这样 $\text{tag}$ 间不会互相影响。那么最后对于一个点，答案可以直接加 $\text{tag}^2$。

由于数据随机，复杂度为 $O(n\sqrt q)$，但是 KDT 常数太大在 LG 上过不去。

考虑将 KDT 上面几层先划分出来，然后对每个叶子分别做，这样可以大大减小常数，然后就可以 $5\text{s}$ 左右过了。

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
    if(a < b){ a = b; return true; }
    return false;
}

template<class T>
bool chmin(T &a, const T &b){
    if(a > b){ a = b; return true; }
    return false;
}

namespace Fastio {}
using Fastio::qin;
using Fastio::qout;

constexpr f8 eps = 1e-8;
struct Point {
    int x, y;
    Point() {}
    Point(int x, int y) : x(x), y(y) {}
};

struct Query {
    f8 x, y; int id;
    Query() {}
    Query(f8 x, f8 y, int id) : x(x), y(y), id(id) {}
};

bool cmpx(const Query& a, const Query& b) { return a.x < b.x; } 
bool cmpy(const Query& a, const Query& b) { return a.y < b.y; }

struct Node {
    int son[2], id, vis;
    unsigned t1, mt1, t2, mt2;
    f8 p[2], l[2], r[2];
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, q;
    qin >> n >> q;

    vector<vector<Point>> pts(n);
    for (int i = 0, x, y, c; i < n; i++) {
        qin >> x >> y >> c;
        c--, pts[c].emplace_back(x, y);
    }

    vector<vector<Query>> qry(3);
    for (int i = 0, A, B, C; i < q; i++) {
        qin >> A >> B >> C;
        if (A == 0) qry[2].emplace_back(B, C, i);
        else qry[A < 0].emplace_back(1.0 * B / A, 1.0 * C / A, i);
    }

    for (int i = 0; i < n; i++) {
        sort(pts[i].begin(), pts[i].end(), [&](auto a, auto b) { return a.y < b.y; });
    }

    vector<Node> t;
    auto create = [&]() {
        t.emplace_back();
        return t.size() - 1;
    };

    auto build = [&](auto&& self, vector<Query>& vec, int l, int r, int o) -> int {
        if (l > r) return -1;
        const int mid = (l + r) >> 1, u = create();
        nth_element(vec.begin() + l, vec.begin() + mid, vec.begin() + r + 1, o == 0 ? cmpx : cmpy);
        t[u].id = vec[mid].id, t[u].p[0] = vec[mid].x, t[u].p[1] = vec[mid].y;
        t[u].t2 = t[u].mt2 = t[u].t1 = t[u].mt1 = t[u].vis = 0;
        t[u].son[0] = self(self, vec, l, mid - 1, !o);
        t[u].son[1] = self(self, vec, mid + 1, r, !o);
        t[u].l[0] = t[u].r[0] = t[u].p[0];
        t[u].l[1] = t[u].r[1] = t[u].p[1];
        for (int j = 0; j < 2; j++) {
            if (t[u].son[j] == -1) continue;
            for (int k = 0; k < 2; k++) {
                chmin(t[u].l[k], t[t[u].son[j]].l[k]);
                chmax(t[u].r[k], t[t[u].son[j]].r[k]);
            }
        }
        return u;
    };

    f8 A, B, C; int tp;
    auto f = [&](f8 x, f8 y) { return A * x + B * y + C < -eps; };
    auto modify = [&](auto&& self, int u) -> void {
        if (u == -1) return;
        int cnt = 0;
        if (tp) cnt = f(t[u].l[0], t[u].r[1]) + f(t[u].r[0], t[u].l[1]);
        else cnt = f(t[u].l[0], t[u].l[1]) + f(t[u].r[0], t[u].r[1]);
        if (cnt == 0) return;
        if (cnt == 2) { t[u].t1++; return; }
        t[u].mt1 += f(t[u].p[0], t[u].p[1]);
        t[u].vis = 1;

        self(self, t[u].son[0]);
        self(self, t[u].son[1]);
    };

    auto pushall = [&](auto &&self, int u) -> void {
        if (u == -1) return;
        if (!t[u].vis) {
            t[u].t2 += t[u].t1 * t[u].t1;
            t[u].t1 = 0;
            return;
        }

        t[u].vis = 0;
        if (~t[u].son[0]) t[t[u].son[0]].t1 += t[u].t1;
        if (~t[u].son[1]) t[t[u].son[1]].t1 += t[u].t1;
        t[u].mt1 += t[u].t1;
        t[u].t1 = 0;
        t[u].mt2 += t[u].mt1 * t[u].mt1;
        t[u].mt1 = 0;
        self(self, t[u].son[0]);
        self(self, t[u].son[1]);
    };

    vector<unsigned> ans(q);
    auto answer = [&](auto &&self, int u, unsigned s) -> void {
        if (u == -1) return;
        s += t[u].t2;
        ans[t[u].id] = s + t[u].mt2;
        self(self, t[u].son[0], s);
        self(self, t[u].son[1], s);
    };

    for (int o = 0; o < 3; o++) {
        const int lim = 7;
        vector<vector<Query>> now;
        now.reserve(1 << lim);
        auto divide = [&](auto &&self, int l, int r, int tp, int dep) -> void {
            if (dep == 0) {
                now.emplace_back();
                for (int j = l; j <= r; j++)
                    now.back().push_back(qry[o][j]);
                return;
            }

            const int mid = (l + r) >> 1;
            nth_element(qry[o].begin() + l, qry[o].begin() + mid, qry[o].begin() + r + 1, tp == 0 ? cmpx : cmpy);
            self(self, l, mid, !tp, dep - 1);
            self(self, mid + 1, r, !tp, dep - 1);
        };
        divide(divide, 0, int(qry[o].size()) - 1, 0, lim);

        for (int k = 0; k < now.size(); k++) {
            t.clear();
            int rt = build(build, now[k], 0, int(now[k].size() - 1), 1);
            for (int i = 0; i < n; i++) {
                for (auto j : pts[i]) {
                    if (o == 0) A = j.y, B = 1, C = j.x;
                    else if (o == 1) A = -j.y, B = -1, C = -j.x;
                    else A = j.y, B = 1, C = 0;
                    tp = A * B < 0;
                    modify(modify, rt);
                }
                pushall(pushall, rt);
            }
            answer(answer, rt, 0);
        }
    }

    for (int i = 0; i < q; i++) qout << ans[i] << '\n';

    return 0;
}