abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S5390 【逗气】

发表于 更新于

Description

给你两个正整数 $n$ 和 $m$，再给你 $a_1$ ~ $a_n$、$b_1$ ~ $b_n$、$c_1$ ~ $c_m$、$d_1$ ~ $d_m$。

现在请你对于每个 $i(1 \leq i \leq m)$，求出 $\max\{b_j - |a_j - c_i| \times d_i\}(1 \leq j \leq m)$ 在对 0 取 $\max$ 后的值。

Solution

考虑把绝对值拆开。

在这里仅讨论 $c_i > a_j$ 的情况，另一种情况类似。

则 $(b_j - |a_j - c_i| \times d_i)$ 将化为 $(b_j + a_jd_i - c_id_i)$，将只与 $i$ 有关的项删去，问题转换为使 $(b_j + a_jd_i)$ 最大。

先将 $a_i$ 和 $c_i$ 丢在一个数组里排序，然后套路地假设 $j$ 比 $k$ 优，其中 $j < k$，即 $b_j + a_jd_i > b_k + a_kd_i$。

整理得到 $\dfrac{b_j - b_k}{a_j - a_k} > -d_i$，发现这个可以斜率优化，于是用一个单调队列来维护一个上凸包的左半部分即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <cstdio>
#define maxN 400010
struct Pos{ long long pos, opt, a, b; } f[maxN];
long long Ans[maxN], dl[maxN];
long long abs (long long x)
{
	return x >= 0 ? x : (-x);
}
long long max (long long x, long long y)
{
	return x > y ? x : y;
}
void px (long long l, long long r)
{
	long long x = l, y = r, mid = f[(l + r) >> 1].a;
	while(x <= y)
	{
		while(f[x].a < mid)
		{
			x++;
		}
		while(f[y].a > mid)
		{
			y--;
		}
		if(x <= y)
		{
			Pos t = f[x];
			f[x] = f[y];
			f[y] = t;
			x++;
			y--;
		}
	}
	if(l < y)
	{
		px(l, y);
	}
	if(x < r)
	{
		px(x, r);
	}
}
double S (long long x, long long y)
{
	return (f[x].b - f[y].b) * 1.0 / (f[y].a - f[x].a);
}
double SS (long long x, long long y)
{
	return (f[x].b - f[y].b) * 1.0 / (f[x].a - f[y].a);
}
int main ()
{
	long long n = 0, m = 0;
	scanf("%lld %lld", &n, &m);
	for(long long i = 1;i <= n; i++)
	{
		f[i].opt = 1;
		scanf("%lld %lld", &f[i].a, &f[i].b);
	}
	for(long long i = 1;i <= m; i++)
	{
		f[n + i].opt = 2, f[n + i].pos = i;
		scanf("%lld %lld", &f[n + i].a, &f[n + i].b);
	}
	n += m;
	px(1, n);
	long long head = 1, tail = 0;
	for(long long i = 1;i <= n; i++)
	{
		if(f[i].opt == 1)
		{
			while(head < tail && S(dl[tail], i) < S(dl[tail - 1], dl[tail]))
			{
				tail--;
			}
			dl[++tail] = i;
		}
		else
		{
			long long l = head, r = tail;
			while(l + 1 < r)
			{
				long long mid = (l + r) >> 1;
				if(S(dl[mid - 1], dl[mid]) < f[i].b)
				{
					l = mid;
				}
				else
				{
					r = mid;
				}
			}
			long long x = 0;
			if(S(dl[l], dl[r]) > f[i].b)
			{
				x = dl[l];
			}
			else
			{
				x = dl[r];
			}
			Ans[f[i].pos] = max(Ans[f[i].pos], f[x].b - abs(f[i].a - f[x].a) * f[i].b);
		}
	}
	head = 1, tail = 0;
	for(long long i = n;i >= 1; i--)
	{
		if(f[i].opt == 1)
		{
			while(head < tail && SS(dl[tail], i) < SS(dl[tail - 1], dl[tail]))
			{
				tail--;
			}
			dl[++tail] = i;
		}
		else
		{
			long long l = head, r = tail;
			while(l + 1 < r)
			{
				long long mid = (l + r) >> 1;
				if(SS(dl[mid - 1], dl[mid]) < f[i].b)
				{
					l = mid;
				}
				else
				{
					r = mid;
				}
			}
			long long x = 0;
			if(SS(dl[l], dl[r]) > f[i].b)
			{
				x = dl[l];
			}
			else
			{
				x = dl[r];
			}
			Ans[f[i].pos] = max(Ans[f[i].pos], f[x].b - abs(f[i].a - f[x].a) * f[i].b);
		}
	}
	for(long long i = 1;i <= m; i++)
	{
		printf("%lld\n", Ans[i]);
	}
	return 0;
}