【UOJ #112】【APIO 2015】Palembang Bridges

http://uoj.ac/problem/112

先扣掉在同一侧的情况。

当\(k=1\)时，桥建在所有位置的中位数。

当\(k=2\)时，对于每个居民\((S_i,T_i)\)，这个居民只会走离\(\frac{S_i+T_i}2\)最近的桥，那么对所有\(\frac{S_i+T_i}2\)排序，最优方案一定满足排序后的居民从中间分开，左边的居民走左边的桥，右边的居民走右边的桥。

从左往右扫，不断加入“左边的居民”，“左边的桥”建在当前“左边的居民”的所有\(S_i\)和\(T_i\)的中位数上，动态维护这个中位数就可以了。右边同理，最后合并答案即可。

对于动态维护中位数，考虑到每次加两个数，中位数只会在相邻的位置间左右横跳，所以维护前驱和后继就可以了。这里可以用树状数组/权值线段树维护前驱后继（前缀最大值，后缀最小值）。

时间复杂度\(O(n\log n)\)。

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 100003;

struct node {

	int x, y;

	bool operator < (const node &A) const {

		return x + y < A.x + A.y;

	}

} Q[N];

ll ans = 0;

int H[N << 1], cnt = 0, n, k, Si, Ti, tot = 0;

char pi, qi;

namespace hahaha {

	void solve() {

		cnt = 0;

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

			H[++cnt] = Q[i].x, H[++cnt] = Q[i].y;

		stable_sort(H + 1, H + cnt + 1);

		ll sum, ret = 0;

		for (int i = cnt >> 1; i >= 1; --i) ret += H[i];

		sum = ret;

		for (int i = (cnt >> 1) + 1; i <= cnt; ++i) sum += H[i];

		ans += sum - (ret << 1);

		printf("%lld\n", ans);

	}

}

template <typename T> void check_max(T &a, T b) {if (b > a) a = b;}

template <typename T> void check_min(T &a, T b) {if (b < a) a = b;}

namespace miaomiaomiao {

	ll f1[N], f2[N];

	int bitsl[N << 1], bitsr[N << 1], id[N << 1];

	bool cmp(int x, int y) {return (x > tot ? Q[x - tot].y : Q[x].x) < (y > tot ? Q[y - tot].y : Q[y].x);}

	void insl(int x) {

		for (int t = x; t <= cnt; t += t & -t)

			check_max(bitsl[t], x);

	}

	void insr(int x) {

		for (int t = x; t; t -= t & -t)

			check_min(bitsr[t], x);

	}

	int findl(int x) {

		int ret = 0;

		for (int t = x - 1; t; t -= t & -t)

			check_max(ret, bitsl[t]);

		return ret;

	}

	int findr(int x) {

		int ret = cnt + 1;

		for (int t = x + 1; t <= cnt; t += t & -t)

			check_min(ret, bitsr[t]);

		return ret;

	}

	void work(ll *f) {

		int mid = 0; ll ret = 0, sum = 0;

		for (int i = 1; i <= cnt; ++i) bitsl[i] = 0, bitsr[i] = cnt + 1;

		for (int i = 1; i <= tot; ++i) {

			int x = Q[i].x, y = Q[i].y;

			insl(x); insl(y);

			insr(x); insr(y);

			sum += H[x]; sum += H[y];

			if (x < mid && y > mid || y < mid && x > mid)

				ret += H[min(x, y)];

			else if (x < mid) {

				ret -= H[mid];

				ret += H[x]; ret += H[y];

				mid = findl(mid);

			} else {

				mid = findr(mid);

				ret += H[mid];

			}

			f[i] = sum - (ret << 1);

		}

	}

	void solve() {

		for (int i = 1; i <= (tot << 1); ++i) id[i] = i;

		stable_sort(Q + 1, Q + tot + 1);

		stable_sort(id + 1, id + (tot << 1) + 1, cmp);

		cnt = 0;

		for (int i = 1; i <= (tot << 1); ++i) {

			++cnt;

			if (id[i] > tot) H[cnt] = Q[id[i] - tot].y, Q[id[i] - tot].y = cnt;

			else H[cnt] = Q[id[i]].x, Q[id[i]].x = cnt;

		}

		work(f1);

		reverse(Q + 1, Q + tot + 1);

		work(f2);

		ll ra = f2[tot];

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

			check_min(ra, f1[i] + f2[tot - i]);

		printf("%lld\n", ans + ra);

	}

}

int main() {

	scanf("%d%d", &k, &n);

	for (int i = 1; i <= n; ++i) {

		for (pi = getchar(); pi != 'A' && pi != 'B'; pi = getchar());

		scanf("%d", &Si);

		for (qi = getchar(); qi != 'A' && qi != 'B'; qi = getchar());

		scanf("%d", &Ti);

		if (qi == pi) ans += abs(Ti - Si);

		else {

			Q[++tot] = (node) {Si, Ti};

			++ans;

		}

	}

	if (k == 1) hahaha::solve();

	else miaomiaomiao::solve();

	return 0;

}

巴特西

【UOJ #112】【APIO 2015】Palembang Bridges

最新文章

热门文章