JOISC 2017 Day 4 Dragon 2

· · 题解

就，类似于样例 1，为了方便角度及坐标运算，不妨先以线段 (D_1,E_1)(D_2E_2) 中点为原点重新建立平面直角坐标系，使得线段两端点均在横轴上类似于对称分布。类似于，我们将所有点坐标减去线段中点，再进行类似于旋转的操作即可。

类似于，就，一个挺典的想法，在 O(\min(|F_j|,|G_j|)T(n)) 的复杂度内回答每一个询问，就是类似于对于每一个点 P_i，O(T(n)) 求出：

考虑就类似于枚举 F_j,G_j 中大小较小的那个集合中的每一个点，通过 f 或者 g 求出答案。复杂度类似于 O(\min(|F_j|,|G_j|)T(n))。类似于，就根号分治，若 \min(|F_j|,|G_j|)\le \sqrt n 则复杂度 O(q\sqrt nT(n))；若 |F_j|,|G_j|> \sqrt n，这样的 F 和 G 只有类似于 O(\sqrt n) 个，类似于对于一个固定的 F，对应的 G 有 O(\sqrt n) 个，于是类似于枚举 F 中每个点，对 G 进行询问 f,g 值，复杂度类似于 O(n\sqrt nT(n))，所以总复杂度就类似于 O((n+q)\sqrt nT(n))。

就，类似于就，我们就只需要求出 f 和 g 就行了。考虑到询问 f,g 的次数不超过 O((n+q)\sqrt n) 次，对询问进行类似于离线的操作并按照颜色 j 排序。每次我们处理出类似于对于固定的 j，所有 f_{i,j} 和 g_{i,j} 询问的结果。下面只需要考虑由类似于颜色 j 的点构成的点集即可。

我们发现，就类似于一个给定的询问点 P_i，被算进 f_{i,j} 的颜色为 j 的点可能就类似于下图：

其中线段 AB 为给定线段，询问点为 C，合法的点可能类似于 D,E 两点，被分成两个区域，一个是在横轴上方，另一个是在下方。计算方法类似于记录每个点连向两线段端点的线段和横轴的夹角，那么询问点夹角为 \alpha,\beta，在图中分别类似于 \angle CAB 和 \angle CBA，合法的点 P_k(C_k=j) 两角类似于 \alpha',\beta'，那么满足：

类似于，就 f_{i,j} 的计算，我们就不难发现 g_{i,j} 类似于下图：

还是分成类似于两个区域，一个在横轴上方，另一个在下方，P_k 满足：

我们发现这就类似于一个二维数点问题，用类似的方法，离散化后主席树解决即可。复杂度类似于 O((n+q)\sqrt n\log n)。

// Problem: #2401. 「JOISC 2017 Day 4」Dragon 2
// Contest: LibreOJ
// URL: https://loj.ac/p/2401
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define pb pop_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long double db;
typedef long long ll;
typedef pair<db, db> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const int N = 3e4 + 300;
const int M = 1e5 + 100;
const db Pi = acos(-1);

int n, m, k, ans[M];
vector<int> g[N];
db len;

struct Q {
    int x, op, id;
    Q () { }
    Q (int _x, int _op, int _id) : 
        x(_x), op(_op), id(_id) { }
};

vector<Q> q[N];

struct P {
    db x, y;
    P () { }
    P (db _x, db _y) : x(_x), y(_y) { }
    P operator + (const P &rh) const { return P(x + rh.x, y + rh.y); }
    P operator - (const P &rh) const { return P(x - rh.x, y - rh.y); }
    P operator * (const db &rh) const { return P (x * rh, y * rh); }
    P rot(pi p) { return P(x * p.fi - y * p.se, x * p.se + y * p.fi); }
    db len() { return sqrt(x * x + y * y); }
    db rad() { return atan2(y, x); }
    pi arc() { db l = len(); return mp(x / l, y / l); }
} a[N], b[N], s, t;

struct SEG {
    struct node { int lc, rc, ct; } tr[N * 20];
    int cx, cy, tot, rt[N];
    db tx[N], ty[N];
    vector<P> S;
    vector<int> g[N];
    #define ls(x) tr[x].lc
    #define rs(x) tr[x].rc
    void upd(int l, int r, int p, int &x, int y) {
        tr[x = ++tot] = tr[y], tr[x].ct++;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (p <= mid) upd(l, mid, p, ls(x), ls(y));
        else upd(mid + 1, r, p, rs(x), rs(y));
    }
    int qry(int l, int r, int s, int t, int x) {
        if (!x) return 0;
        if (s <= l && r <= t) return tr[x].ct;
        int mid = (l + r) >> 1, res = 0;
        if (s <= mid) res += qry(l, mid, s, t, ls(x));
        if (t > mid) res += qry(mid + 1, r, s, t, rs(x));
        return res;
    }
    void clr() {
        memset(rt, 0, sizeof(int) * (cx + 5));
        for (int i = 1; i <= cx; i++) g[i].clear();
        for (int i = 1; i <= tot; i++) tr[i].lc = tr[i].rc = tr[i].ct = 0;
        cx = cy = tot = 0, S.clear();
    }
    void ins(P p) { tx[++cx] = p.x, ty[++cy] = p.y, S.eb(p); }
    void bld() { 
        sort(tx + 1, tx + cx + 1), cx = unique(tx + 1, tx + cx + 1) - tx - 1;
        sort(ty + 1, ty + cy + 1), cy = unique(ty + 1, ty + cy + 1) - ty - 1;
        for (auto [x, y] : S) {
            int _x = lower_bound(tx + 1, tx + cx + 1, x) - tx;
            int _y = lower_bound(ty + 1, ty + cy + 1, y) - ty;
            g[_x].eb(_y);
        }
        for (int i = 1; i <= cx; i++) {
            rt[i] = rt[i - 1];
            for (int j : g[i]) upd(1, cy, j, rt[i], rt[i]);
        }
    }
    int qlr(db lx, db rx, db ly, db ry) {
        int _lx = lower_bound(tx + 1, tx + cx + 1, lx) - tx;
        int _ly = lower_bound(ty + 1, ty + cy + 1, ly) - ty;
        int _rx = upper_bound(tx + 1, tx + cx + 1, rx) - tx - 1;
        int _ry = upper_bound(ty + 1, ty + cy + 1, ry) - ty - 1;
        return qry(1, cy, _ly, _ry, rt[_rx]) - qry(1, cy, _ly, _ry, rt[_lx - 1]);
    }
} T[2];

void solve() {
    cin >> n >> m;
    for (int i = 1, x, y, z; i <= n; i++) 
        cin >> x >> y >> z, a[i] = P(x, y), g[z].eb(i);
    cin >> s.x >> s.y >> t.x >> t.y; 
    if (s.x > t.x) swap(s, t);
    P md = (s + t) * 0.5; len = (s - md).len();
    auto p = (s - md).arc(); p.fi = -p.fi;
    for (int i = 1; i <= n; i++) a[i] = (a[i] - md).rot(p);
    s = P(-len, 0), t = P(len, 0);
    for (int i = 1; i <= n; i++) {
        b[i].x = (a[i] - s).rad();
        b[i].y = (a[i] - t).rad();
        if (b[i].x < 0) b[i].x = -b[i].x;
        if (b[i].y < 0) b[i].y = Pi + b[i].y;
        else b[i].y = Pi - b[i].y;
    }
    cin >> k;
    for(int i = 1, u, v; i <= k; i++) {
        cin >> u >> v;
        if (g[u].size() < g[v].size()) 
            for (int x : g[u]) q[v].eb(Q(x, 0, i));
        else for (int x : g[v]) q[u].eb(Q(x, 1, i));
    }
    for (int i = 1; i <= m; i++) {
        if (!q[i].size() || !g[i].size()) continue;
        T[0].clr(), T[1].clr();
        for (int j : g[i]) {
            if (a[j].y > 0) T[0].ins(b[j]);
            else T[1].ins(b[j]);
        }
        T[0].bld(), T[1].bld();
        for (auto [x, op, id] : q[i]) {
            int o = (a[x].y > 0) ? 0 : 1;
            if (!op) ans[id] += T[o].qlr(0, b[x].x, 0, b[x].y) + T[o ^ 1].qlr(0, Pi - b[x].x, 0, Pi - b[x].y);
            else ans[id] += T[o].qlr(b[x].x, Pi, b[x].y, Pi) + T[o ^ 1].qlr(0, Pi - b[x].x, 0, Pi - b[x].y);
        }
    }
    for (int i = 1; i <= k; i++)
        cout << ans[i] << '\n';
}

bool Med;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
    #ifdef FILE
        freopen("1.in", "r", stdin);
        freopen("1.out", "w", stdout);
    #endif
    int T = 1;
    // cin >> T;
    while (T--) solve();
    cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
    return 0;
}