题解

火球是一条从龙 $u$ 指向龙 $v$ 的射线。它能烧到道路，当且仅当：

1. 射线与线段 $D_1D_2$ 相交；
2. $v$ 在 $u$ 的前方，即 $v$ 不会在 $u$ 后面（那样射线永远也碰不到道路）。

把道路方向视为向量 $\vec{s} = D_2 - D_1$，在端点 $D_1$ 与 $D_2$ 处分别以极角顺序排序所有龙的位置。若在 $D_1$ 看过去，$v$ 的极角介于 $u$ 与另一个端点之间，并且在 $D_2$ 看过去 $v$ 的极角也介于 $u$ 与另一个端点之间，那么 $uv$ 就会与道路相交。因此我们只需要做出两组“按极角排序并支持两维偏序计数”的数据结构，每种种族建一份，然后在线回答询问。

具体做法：

• 对每条龙计算 $\vec{u_1}=P-D_1$、$\vec{u_2}=P-D_2$ 两个向量，与 $\vec{s}$ 比较方向，把龙划入 $\vec{s}$ 左侧或右侧。对于左、右两个半平面，各维护一个结构体 Calc，结构体中存的是按极角排序后的 $(\vec{u_1},\vec{u_2})$ 对。排序后用可持久化线段树维护前缀，支持查询“在第一维角度 $\le x$ 的所有点里，第二维角度 $>y$（或 $\ge y$）的数量”。这恰好对应了“在 $D_1$ 看过去排在 $x$ 前面，同时在 $D_2$ 看过去排在 $y$ 后面”的龙的数量。
• 每个种族只保存本种族的龙。一次询问 $(F,G)$ 时，枚举较小的那个种族的所有龙，按照它们位于哪一侧选择对应 Calc，把“射手看到的另一端的向量”转成查询参数，就可以在 $O(\log N)$ 时间内统计与种族 $G$ 的龙形成可行射线的个数。由于每只龙只被插入两棵 Calc，总复杂度为 $O(N \log N + Q \min(|F|,|G|)\log N)$，在本题数据范围内可接受。

最后把每次查询得到的结果累加（分别处理左右两侧），即为该次敌对关系中会烧到道路的火球数量。

#include <bits/stdc++.h>
using namespace std;
int Qread() {
    int x = 0;
    bool f = false;
    char ch = getchar();

    while (ch < '0' || ch > '9')
        f |= (ch == '-'), ch = getchar();

    while (ch >= '0' && ch <= '9')
        x = x * 10 + (ch ^ 48), ch = getchar();

    return f ? -x : x;
}
struct Vec {
    int x, y;
};
//逆时针方向更大
Vec neg(Vec A) {
    return Vec{-A.x, -A.y};
}
bool operator<(Vec A, Vec B) {
    return 1ll * A.x * B.y - 1ll * B.x * A.y > 0;
}
struct Node {
    int lson, rson;
    int sum;
} s[1000010];
int poi_cnt;
#define ls s[pos].lson
#define rs s[pos].rson
#define mid (l+r>>1)
struct Sege {
    vector<int> rt;
    int tot, len;
    void init(int len) {
        rt.resize(1), this->len = len;
    }
    void insert(int x, int las, int &pos, int l, int r) {
        pos = ++poi_cnt;
        s[pos] = s[las], s[pos].sum++;

        if (l == r)
            return;

        if (x <= mid)
            insert(x, s[las].lson, ls, l, mid);
        else
            insert(x, s[las].rson, rs, mid + 1, r);
    }
    void Insert(int x) {
        rt.push_back(0);
        tot++;
        insert(x, rt[tot - 1], rt[tot], 1, len);
    }
    int query(int L, int R, int pos, int l, int r) {
        if (L <= l && r <= R)
            return s[pos].sum;

        if (r < L || R < l)
            return 0;

        return query(L, R, ls, l, mid) + query(L, R, rs, mid + 1, r);
    }
    int Query(int x, int L, int R) {
        return query(L, R, rt[x], 1, len);
    }
};
#undef ls
#undef rs
#undef mid
struct Calc {
    int tot;
    vector<Vec> X, Y;
    vector<pair<Vec, Vec>> P;
    Sege S;
    void insert(Vec x, Vec y) {
        tot++;
        X.push_back(x), Y.push_back(y);
        P.push_back(make_pair(x, y));
    }
    void build() {
        S.init(tot);
        sort(X.begin(), X.end()), sort(Y.begin(), Y.end());
        sort(P.begin(), P.end());

        for (int i = 0; i < tot; i++)
            S.Insert(lower_bound(Y.begin(), Y.end(), P[i].second) - Y.begin() + 1);
    }
    //typ=true a<x b>y
    //typ=false a>x b<y
    int Query(Vec x, Vec y, bool typ) {
        if (!tot)
            return 0;

        int tx = lower_bound(X.begin(), X.end(), x) - X.begin() + 1,
            ty = lower_bound(Y.begin(), Y.end(), y) - Y.begin() + 1;

        if (typ)
            return S.Query(tx - 1, ty, tot);
        else
            return S.Query(tot, 1, ty - 1) - S.Query(tx - 1, 1, ty - 1);
    }
} S[30010][2];
int siz[30010];
vector<int> dy[30010];
int N, M, Q;
int x[30010], y[30010], c[30010];
bool typ[30010];
int D1, E1, D2, E2, F, G;
Vec st, t;
long long ans;
int main() {
    N = Qread(), M = Qread();

    for (int i = 1; i <= N; i++)
        x[i] = Qread(), y[i] = Qread(), c[i] = Qread();

    D1 = Qread(), E1 = Qread(), D2 = Qread(), E2 = Qread();
    st.x = D2 - D1, st.y = E2 - E1;

    for (int i = 1; i <= N; i++) {
        siz[c[i]]++;
        dy[c[i]].push_back(i);
        t.x = x[i] - D1, t.y = y[i] - E1;

        if (t < st) //in S0
            S[c[i]][0].insert(Vec{x[i] - D1, y[i] - E1}, Vec{x[i] - D2, y[i] - E2});
        else //in S1
            S[c[i]][1].insert(Vec{x[i] - D2, y[i] - E2}, Vec{x[i] - D1, y[i] - E1}), typ[i] = true;
    }

    for (int i = 1; i <= M; i++) {
        if (S[i][0].tot)
            S[i][0].build();

        if (S[i][1].tot)
            S[i][1].build();
    }

    Q = Qread();

    for (int i = 1; i <= Q; i++) {
        F = Qread(), G = Qread();
        ans = 0;

        if (siz[F] < siz[G]) {
            for (int &g : dy[F])
                if (typ[g]) {
                    ans += S[G][0].Query(Vec{D1 - x[g], E1 - y[g]}, Vec{D2 - x[g], E2 - y[g]}, false);
                    ans += S[G][1].Query(Vec{x[g] - D2, y[g] - E2}, Vec{x[g] - D1, y[g] - E1}, false);
                } else {
                    ans += S[G][0].Query(Vec{x[g] - D1, y[g] - E1}, Vec{x[g] - D2, y[g] - E2}, false);
                    ans += S[G][1].Query(Vec{D2 - x[g], E2 - y[g]}, Vec{D1 - x[g], E1 - y[g]}, false);
                }

        } else {
            for (int &g : dy[G])
                if (typ[g]) {
                    ans += S[F][0].Query(Vec{D1 - x[g], E1 - y[g]}, Vec{D2 - x[g], E2 - y[g]}, false);
                    ans += S[F][1].Query(Vec{x[g] - D2, y[g] - E2}, Vec{x[g] - D1, y[g] - E1}, true);
                } else {
                    ans += S[F][0].Query(Vec{x[g] - D1, y[g] - E1}, Vec{x[g] - D2, y[g] - E2}, true);
                    ans += S[F][1].Query(Vec{D2 - x[g], E2 - y[g]}, Vec{D1 - x[g], E1 - y[g]}, false);
                }
        }

        printf("%lld\n", ans);
    }

    return 0;
}