USACO 2014 December Contest, Gold Problem 2. Marathon

原题下载

USACO2014-DEC-G2

答案

(Analysis by Allen Chen)

Seeing that we have to update point coordinates and query the minimum travel time for a sub-route, we immediately see that this problem involves range queries and updates. A well known data structure that can be used to solve this problem is the segment tree, which allows us to handle such operations in logarithmic time.

First, let us take care of querying the minimum travel time, ignoring the fact that the cows can skip a checkpoint along the way. To do this, we treat each 2 consecutive checkpoints as one single node in a segment tree (let's call this tree "dist"). Then we just simply store the distance between each 2 consecutive points in each node.

Next, we need to handle the fact that cows can skip exactly one checkpoint along the way. Let's say we need to find the minimum travel time between checkpoints Ci and Cj and let's also say we skip a checkpoint Ck, where i<k<j. Let's also define G(a,b), as the distance between checkpoint a and b. Therefore, the time taken without skipping a checkpoint is equal to:

while the time taken by skipping a checkpoint is equal to:

If we take the difference:

Notice that if we maximize the value D1−D2, then we will obtain a minimum D2since D1 is a fixed value regardless of any checkpoint we skip. Thus we can use a second segment tree (call it Δ) and treat each 3 consecutive checkpoints as one node. In each node of Δ, we only need to store D1−D2, because we can obtain D2 by taking: D1 minus the best Δ value.

Thus, we can perform range maximum query on delta and a range sum query on dist to obtain our final answer while performing updates as necessary.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<utility>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 1 << 17;
int n, q;
pii mat[maxn];
int delta[2 * maxn];
int dist[2 * maxn];

int qa, qb;
int getd(int a, int b) {
	return abs(mat[a].first - mat[b].first) + abs(mat[a].second - mat[b].second);
}

void build(int rt, int a, int b) {
	if (a > b) return;
	if (a == b) {
		if (a < n - 1) delta[rt] = getd(a, a + 1) + getd(a + 1, a + 2) - getd(a, a + 2);
		else delta[rt] = 0;
		if (a < n) dist[rt] = getd(a, a + 1);
		else dist[rt] = 0;
		return;
	}
	int mid = (a + b) / 2;
	build(rt * 2, a, mid);
	build(rt * 2 + 1, mid + 1, b);
	delta[rt] = max(delta[rt * 2], delta[rt * 2 + 1]);
	dist[rt] = dist[rt * 2] + dist[rt * 2 + 1];
}

int query_dist(int rt, int a, int b) {
	if (a > qb || b < qa) return 0;
	if (qa <= a && b <= qb) return dist[rt];
	int mid = (a + b) / 2;
	return query_dist(rt * 2, a, mid) + query_dist(rt * 2 + 1, mid + 1, b);
}

int query_delta(int rt, int a, int b) {
	if (a > qb || b < qa) return 0;
	if (qa <= a && b <= qb) return delta[rt];
	int mid = (a + b) / 2;
	return max(query_delta(rt * 2, a, mid), query_delta(rt * 2 + 1, mid + 1, b));
}

void update_dist(int rt, int a, int b) {
	if (a > qb || b < qa) return;
	if (qa <= a && b <= qb) {
		if (a >= 1 && a < n) dist[rt] = getd(a, a + 1);
		else dist[rt] = 0;
		return;
	}
	int mid = (a + b) / 2;
	update_dist(rt * 2, a, mid);
	update_dist(rt * 2 + 1, mid + 1, b);
	dist[rt] = dist[rt * 2] + dist[rt * 2 + 1];
}

void update_delta(int rt, int a, int b) {
	if (a > qb || b < qa) return;
	if (qa <= a && b <= qb) {
		if (a >= 1 && a < n - 1) delta[rt] = getd(a, a + 1) + getd(a + 1, a + 2) - getd(a, a + 2);
		else delta[rt] = 0;
		return;
	}
	int mid = (a + b) / 2;
	update_delta(rt * 2, a, mid);
	update_delta(rt * 2 + 1, mid + 1, b);
	delta[rt] = max(delta[rt * 2], delta[rt * 2 + 1]);
}

int main() {
	freopen("marathon.in", "r", stdin);
	freopen("marathon.out", "w", stdout);
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &mat[i].first, &mat[i].second);
	}
	build(1, 1, n);
	for (int i = 0; i < q; i++) {
		char c[2];
		scanf("%s", c);
		if (c[0] == 'Q') {
			scanf("%d%d", &qa, &qb);
			qb--;
			int tot = query_dist(1, 1, n);
			qb--;
			int del = query_delta(1, 1, n);
			printf("%d\n", tot - del);
		}
		else {
			int ix, pa, pb;
			scanf("%d%d%d", &ix, &pa, &pb);
			mat[ix].first = pa;
			mat[ix].second = pb;
			for (int j = ix - 1; j <= ix; j++) {
				qa = j; qb = j;
				update_dist(1, 1, n);
			}
			for (int j = ix - 2; j <= ix; j++) {
				qa = j; qb = j;
				update_delta(1, 1, n);
			}
		}
	}
}
翰林国际教育资讯二维码