luogu4088 [USACO18FEB]Slingshot

这题在线得写树套树，所以我写的离线+树状数组

对于每个询问，Ans=\(\max_{j=1}^n{|a_j-x_i|+|b_j-y_i|+t_i}\)

拆成四种情况

\(x_i\le a_j,y_i\le b_j: a_j+b_j+t_i-x_i-y_i\)

\(x_i\le a_j,y_i> b_j: a_j-b_j+t_i-x_i+y_i\)

\(x_i> a_j,y_i\le b_j: -a_j+b_j+t_i+x_i-y_i\)

\(x_i> a_j,y_i> b_j: -a_j-b_j+t_i+x_i+y_i\)

第一维直接排序（不用离散化但是我智障我离散化了）

第二维分四种情况树状数组即可，由于查询的是前缀、后缀最值（而不是区间最值）所以直接树状数组维护最值即可

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

using namespace std;

struct shot { int x, y, t; } a[100010];

struct shit { int a, b, id; } q[100010];

long long upd1[100010], upd2[100010], upd3[100010], upd4[100010];

int N, M;

int disc1[200010], disc2[200010], A[100010], B[100010], x[100010], y[100010], tot1, tot2;

long long ans[100010], fenwick[200010];

template<class _T> void chkmin(_T &a, _T b) { if (b < a) a = b; }

void chenge(int x, long long k) { for (int i = x; i <= tot2; i += i & -i) chkmin(fenwick[i], k); }

long long query(int x)

{

	long long res = 0x3f3f3f3f3f3f3f3fLL;

	for (int i = x; i > 0; i &= i - 1) chkmin(res, fenwick[i]);

	return res;

}

int main()

{

	scanf("%d%d", &N, &M);

	for (int i = 1; i <= N; i++) scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].t), disc1[++tot1] = a[i].x, disc2[++tot2] = a[i].y;

	for (int i = 1; i <= M; i++) scanf("%d%d", &q[i].a, &q[i].b), disc1[++tot1] = q[i].a, disc2[++tot2] = q[i].b, q[i].id = i;

	sort(disc1 + 1, disc1 + 1 + tot1), tot1 = unique(disc1 + 1, disc1 + tot1 + 1) - disc1 - 1;

	sort(disc2 + 1, disc2 + 1 + tot2), tot2 = unique(disc2 + 1, disc2 + tot2 + 1) - disc2 - 1;

	sort(a + 1, a + 1 + N, [](const shot &a, const shot &b) { return a.x < b.x; });

	sort(q + 1, q + 1 + M, [](const shit &a, const shit &b) { return a.a < b.a; });

	for (int i = 1; i <= N; i++)

	{

		x[i] = lower_bound(disc1 + 1, disc1 + 1 + tot1, a[i].x) - disc1;

		y[i] = lower_bound(disc2 + 1, disc2 + 1 + tot2, a[i].y) - disc2;

		upd1[i] = (long long)a[i].t - a[i].x - a[i].y;

		upd2[i] = (long long)a[i].t - a[i].x + a[i].y;

		upd3[i] = (long long)a[i].t + a[i].x - a[i].y;

		upd4[i] = (long long)a[i].t + a[i].x + a[i].y;

	}

	for (int i = 1; i <= M; i++)

	{

		ans[q[i].id] = abs(q[i].a - q[i].b);

		A[i] = lower_bound(disc1 + 1, disc1 + 1 + tot1, q[i].a) - disc1;

		B[i] = lower_bound(disc2 + 1, disc2 + 1 + tot2, q[i].b) - disc2;

	}

	memset(fenwick, 0x3f, sizeof(fenwick));

	for (int i = 1, j = 1; i <= M; i++)

	{

		while (j <= N && x[j] <= A[i]) chenge(y[j], upd1[j]), j++;

		chkmin(ans[q[i].id], query(B[i]) + q[i].a + q[i].b);

	}

	memset(fenwick, 0x3f, sizeof(fenwick));

	for (int i = 1, j = 1; i <= M; i++)

	{

		while (j <= N && x[j] <= A[i]) chenge(tot2 - y[j] + 1, upd2[j]), j++;

		chkmin(ans[q[i].id], query(tot2 - B[i] + 1) + q[i].a - q[i].b);

	}

	memset(fenwick, 0x3f, sizeof(fenwick));

	for (int i = M, j = N; i >= 1; i--)

	{

		while (j >= 1 && x[j] >= A[i]) chenge(y[j], upd3[j]), j--;

		chkmin(ans[q[i].id], query(B[i]) - q[i].a + q[i].b);

	}

	memset(fenwick, 0x3f, sizeof(fenwick));

	for (int i = M, j = N; i >= 1; i--)

	{

		while (j >= 1 && x[j] >= A[i]) chenge(tot2 - y[j] + 1, upd4[j]), j--;

		chkmin(ans[q[i].id], query(tot2 - B[i] + 1) - q[i].a - q[i].b);

	}

	for (int i = 1; i <= M; i++) printf("%lld\n", ans[i]);

	return 0;

}

巴特西

luogu4088 [USACO18FEB]Slingshot

最新文章

热门文章