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_{i,j}$ 表示以 $P_i$ 为起点，经过类似于颜色为 $j$ 的点 $P_k(C_k=j)$ 并且穿过给定线段的射线数。
$g_{i,j}$ 表示经过 $P_i$ ，以类似于颜色为 $j$ 的点 $P_k(C_k=j)$ 为起点并且穿过给定线段的射线数。

考虑就类似于枚举

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'

，那么满足：

类似于点 $P_k$ 在横轴上方的情况，则要求 $\alpha'<\alpha,\beta'<\beta$ 。
类似于点 $P_k$ 在横轴下方的情况，则要求 $\alpha'<\pi-\alpha,\beta'<\pi-\beta$ 。

类似于，就

f_{i,j}

的计算，我们就不难发现

g_{i,j}

类似于下图：

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

P_k

满足：

类似于 $P_k$ 在横轴上方， $\alpha'>\alpha,\beta'>\beta$ 。
类似于 $P_k$ 在横轴下方，这和刚才 $f_{i,j}$ 的第二种情况一样， $\alpha'<\pi-\alpha,\beta'<\pi-\beta$ 。

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

O((n+q)\sqrt n\log n)

。

CPP

// 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;
}

JOISC 2017 Day 4 Dragon 2

文章操作

相关推荐

评论

JOISC 2017 Day 4 Dragon 2