bzoj2402 陶陶的难题II 分数规划+树剖+线段树维护凸壳+二分

题目传送门

https://lydsy.com/JudgeOnline/problem.php?id=2402

题解

看上去很像分数规划的模型。于是就二分吧。令

\[\begin{align*}\frac{y_i+q_j}{x_i+p_j} &\geq mid\\y_i+q_j &\geq mid(x_i+p_j)\\(y_i - mid\cdot x_i) + (q_j - mid\cdot p_j) & \geq 0\end{align*}
\]

这样 \(x, y\) 和 \(p, q\) 两组量就毫不相关了。下面就以 \(x, y\) 这一组量为例。

现在的问题是求出树上 \(A\) 到 \(B\) 的路径上的 \(y_i - mid \cdot x_i\) 的最大值。

容易发现，如果我们令 \(y_i - mid \cdot x_i\) 是关于 \(mid\) 的一次函数，在坐标系上可以表示一条以 \(mid\) 为 \(x\) 轴的直线。如果我们可以得到从 \(A\) 到 \(B\) 的路径上的每一个点的 \(x\) 和 \(y\)，那么可以得到很多的直线。我们需要的是很多条直线在 \(mid\) 处的最大值。

考虑只保留对于任意一个 \(mid\) 时取最大值的坐标点，那么这应该是一个下凸壳。如果我们可以维护出这个下凸壳的话，对于一个已知的 \(mid\)，只需要在凸壳上二分它是在哪一条直线上就可以求出来了。

现在考虑如果得到这个下凸壳。可以使用树剖，对于线段树上每一段，维护这个区间的凸壳。

维护方法就是直接对于每一段暴力建凸壳就行了，反正总长度为 \(n\log n\) 级别。

于是总的时间复杂度为 \(O(n\log n +q \log ^4n)\)。后面的 \(\log^4n\) 分别来自分数规划的二分、树链剖分、线段树、凸壳上二分。

由于本题时限充足，以及中间的两个 \(\log n\) 都跑的不是很满，所以可以通过此题。

本题细节比较多，可能不是很好调，写的时候要注意一些细节，比如 vector 的第一位的下标为 \(0\)，小心越界、注意特判掉 \(k\) 值相同的直线等等。

#include<bits/stdc++.h>

#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)

#define dbg(...) fprintf(stderr, __VA_ARGS__)

#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)

#define fi first

#define se second

#define pb push_back

template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}

template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}

typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;

template<typename I> inline void read(I &x) {

	int f = 0, c;

	while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;

	x = c & 15;

	while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);

	f ? x = -x : 0;

}

#define lc o << 1

#define rc o << 1 | 1

const int N = 30000 + 7;

int n, m, dfc;

double maxy, maxq;

int dep[N], f[N], siz[N], son[N], dfn[N], pre[N], top[N];

struct Edge { int to, ne; } g[N << 1]; int head[N], tot;

inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }

inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }

struct Line {

	double k, b;

	inline Line() {}

	inline Line(const double &k, const double &b) : k(k), b(b) {}

	inline bool operator < (const Line &a) const { return k < a.k || (k == a.k && b > a.b); }

	inline double get_y(const double &x) { return k * x + b; }

} tmp[N], tmp2[N];

inline double get_x(const Line &a, const Line &b) { return (b.b - a.b) / (a.k - b.k); }

struct SGT {

	Line a[N];

	std::vector<Line> t[N << 2];

	inline void calc(int o, int L, int R) {

		int M = (L + R) >> 1;

		std::merge(tmp + L, tmp + M + 1, tmp + M + 1, tmp + R + 1, tmp2 + 1);

		std::copy(tmp2 + 1, tmp2 + R - L + 2, tmp + L);

		int tl = 0;

		t[o].push_back(tmp[L]);

		for (int i = L + 1; i <= R; ++i) {

			while (tl >= 1 && get_x(tmp[i], t[o][tl - 1]) <= get_x(t[o][tl], t[o][tl - 1])) --tl, t[o].pop_back();

			t[o].push_back(tmp[i]), ++tl;

		}

	}

	inline double get_ans(int o, double x) {

		if (t[o].size() == 1) return t[o][0].get_y(x);

		int l = 1, r = t[o].size() - 1;

		while (l < r) {

			int mid = (l + r + 1) >> 1;

			if (get_x(t[o][mid - 1], t[o][mid]) <= x) l = mid;

			else r = mid - 1;

		}

		if (get_x(t[o][l - 1], t[o][l]) <= x) return t[o][l].get_y(x);

		else return t[o][l - 1].get_y(x);

	}

	inline void build(int o, int L, int R) {

		if (L == R) return tmp[L] = a[pre[L]], t[o].pb(tmp[L]), (void)0;

		int M = (L + R) >> 1;

		build(lc, L, M), build(rc, M + 1, R);

		calc(o, L, R);

	}

	inline double qmax(int o, int L, int R, int l, int r, double x) {

		if (l <= L && R <= r) return get_ans(o, x);

		int M = (L + R) >> 1;

		if (r <= M) return qmax(lc, L, M, l, r, x);

		if (l > M) return qmax(rc, M + 1, R, l, r, x);

		return std::max(qmax(lc, L, M, l, r, x), qmax(rc, M + 1, R, l, r, x));

	}

} A, B;

inline void dfs1(int x, int fa = 0) {

	dep[x] = dep[fa] + 1, f[x] = fa, siz[x] = 1;

	for fec(i, x, y) if (y != fa) dfs1(y, x), siz[x] += siz[y], siz[y] > siz[son[x]] && (son[x] = y);

}

inline void dfs2(int x, int pa) {

	top[x] = pa, dfn[x] = ++dfc, pre[dfc] = x;

	if (!son[x]) return; dfs2(son[x], pa);

	for fec(i, x, y) if (y != f[x] && y != son[x]) dfs2(y, y);

}

inline double qmax(int x, int y, double k) {

	double ans1 = -1e9, ans2 = -1e9;

	while (top[x] != top[y]) {

		if (dep[top[x]] < dep[top[y]]) std::swap(x, y);

		smax(ans1, A.qmax(1, 1, n, dfn[top[x]], dfn[x], k));

		smax(ans2, B.qmax(1, 1, n, dfn[top[x]], dfn[x], k));

		x = f[top[x]];

	}

	if (dep[x] > dep[y]) std::swap(x, y);

	smax(ans1, A.qmax(1, 1, n, dfn[x], dfn[y], k));

	smax(ans2, B.qmax(1, 1, n, dfn[x], dfn[y], k));

	return ans1 + ans2;

}

inline double solve(int x, int y) {

	double l = 0, r = maxy + maxq;

	while (r - l > 0.001) {

		double mid = (l + r) / 2;

		if (qmax(x, y, mid) >= 0) l = mid;

		else r = mid;

	}

	return l;

}

inline void work() {

	dfs1(1), dfs2(1, 1), A.build(1, 1, n), B.build(1, 1, n);

	int m;

	read(m);

	while (m--) {

		int x, y;

		read(x), read(y);

		printf("%.4lf\n", solve(x, y));

	}

}

inline void init() {

	read(n);

	for (int i = 1; i <= n; ++i) scanf("%lf", &A.a[i].k), A.a[i].k = -A.a[i].k;

	for (int i = 1; i <= n; ++i) scanf("%lf", &A.a[i].b), smax(maxy, A.a[i].b);

	for (int i = 1; i <= n; ++i) scanf("%lf", &B.a[i].k), B.a[i].k = -B.a[i].k;

	for (int i = 1; i <= n; ++i) scanf("%lf", &B.a[i].b), smax(maxq, B.a[i].b);

	int x, y;

	for (int i = 1; i < n; ++i) read(x), read(y), adde(x, y);

}

int main() {

#ifdef hzhkk

	freopen("hkk.in", "r", stdin);

#endif

	init();

	work();

	fclose(stdin), fclose(stdout);

	return 0;

}

巴特西

bzoj2402 陶陶的难题II 分数规划+树剖+线段树维护凸壳+二分

题目传送门

题解

最新文章

热门文章